Число двоек в таких разбиениях n, которые не содержат "1"?

[maximkarimov]

Сколько всего двоек в таких разбиениях n, которые не содержат единиц?

[gris]

для уяснения:
$2=2$ Или это не считается?
$4=2+2$
$5=2+3$
$6=2+2+2=2+4$
$7=2+2+3=2+5$
$8=2+2+2+2=2+2+4=2+6=2+3+3$
То есть вырисовывается такая последовательность:
$0,1(0),0,2,1,4,3...$

[maximkarimov]

Совершенно верно. Двойка для n=2 считается.

[Dendr]

Пусть $p_n$ - количество разбиений числа n. (это последовательность A000041.)

Количество разбиений числа $n$, обязательно содержащих единицу, определяется так: выпишем отдельно единицу, и далее - любые разбиения числа $n-1$.
Таким образом, всего интересующих нас разбиений $q_n=p_n-p_{n-1}$.

Пусть $t_n$ - искомая последовательность. Тогда рекуррентная формула для ее членов определяется так: для данного числа $n$ выписываем строки, начинающиеся с одной двойки, и к ним дописываем поочередно все разбиения без единицы числа $n-2$. Всего будет $q_{n-2}$ строк, в которых, помимо "начальных" двоек, будет еще $t_{n-2}$ двоек.
Таким образом, $t_n=t_{n-2}+q_{n-2}=p_{n-2}-p_{n-3}+t_{n-2}$.

Очевидно, $t_1=0, t_2=1, t_3=0$, все остальные значения восстанавливаются по этим.
Полная формула, как легко видеть:
для четных: $t_n=p_{n-2}-p_{n-3}+p_{n-4}-p_{n-5}+...+p_2-p_1+1$
для нечетных: $t_n=p_{n-2}-p_{n-3}+p_{n-4}-p_{n-5}+...+p_3-p_2$

Если принять $p_0=1$ и к последнему выражению добавить для симметрии $p_1-p_0=0$, получаем единую формулу:
$t_n=\sum\limits_{k=2}^{n}(-1)^k p_{n-k}$
Дальше пока непонятно, можно ли упрощать.

[maximkarimov]

Ответ правильный.
Мы имеем дело с последовательностью A182712.
Хотя для нее и существует более простая формула, но скорость с которой Вы нашли решение задачи, впечатляет.
Великолепно!
Спасибо.

[svv]

Как показал Dendr, $t_{n}=p_{n-2}-p_{n-3}+t_{n-2}$.
Используя обозначение $u_{n}=t_{n}+t_{n-1}-p_{n-2}$, это можно записать в виде $u_n=u_{n-1}$.
Легко проверить, что, например, $u_{3}=0$, откуда вообще все $u_n=0$, и $t_{n}=p_{n-2}-t_{n-1}$.

[maximkarimov]

Итак, пусть A - множество таких разбиений n, которые содержат "двойку" и не содержат "единицу".
Сколько в A наборов, которые содержат "двойку" ровно k-раз?

[svv]

Введём обозначения:
$p_n$ — число разбиений числа $n$;
$p_n(1)$ — число разбиений $n$, в которых есть хотя бы одна единица;
$p_n(2)$ — число разбиений $n$, в которых есть хотя бы одна двойка;
$p_n(1,2)$ — число разбиений $n$, в которых есть и единица, и двойка;
$p_n(\bar 1,\bar 2)$ — число разбиений $n$, в которых нет ни единиц, ни двоек;
$p_n^{k}$ — число разбиений $n$ без единиц и с ровно $k$ двойками.

Существует биекция между множеством разбиений $n$ с хотя бы одной единицей и множеством всех разбиений числа $n-1$ (вычеркнем единицу — допишем единицу). Поэтому $p_n(1)=p_{n-1}$. Аналогично $p_n(2)=p_{n-2}$ и $p_n(1,2)=p_{n-3}$.

По формуле включений-исключений находим:
$p_n(\bar 1,\bar 2)=p_n-p_n(1)-p_n(2)+p_n(1,2)=p_n-p_{n-1}-p_{n-2}+p_{n-3}$

Существует биекция между
$\bullet$ множеством разбиений $n$ без единиц и ровно с $k$ двойками, и
$\bullet$ множеством разбиений $n-2k$ без единиц и без двоек.
Поэтому
$p_n^k=p_{n-2k}(\bar 1,\bar 2)=p_{n-2k}-p_{n-2k-1}-p_{n-2k-2}+p_{n-2k-3}$

Пример. Для $n=10$ получаем

$$\begin{array}{llll} p_{10}^0=p_{10}-p_9-p_8+p_7&=42-30-22+15&=5 & (10,5+5,6+4,7+3,4+3+3)\\ p_{10}^1=p_8-p_7-p_6+p_5&=22-15-11+7&=3 & (8+2,4+4+2,5+3+2)\\ p_{10}^2=p_6-p_5-p_4+p_3&=11-7-5+3&=2 & (6+2+2,3+3+2+2)\\ p_{10}^3=p_4-p_3-p_2+p_1&=5-3-2+1&=1 & (4+2+2+2)\\ p_{10}^4=p_2-p_1-p_0+p_{-1}&=2-1-1+0 &=0& \\ p_{10}^5=p_0-p_{-1}-p_{-2}+p_{-3}&=1-0-0+0&=1 & (2+2+2+2+2)\end{array}$$

[maximkarimov]

svv в сообщении #1476909 писал(а):

$p_n^k=p_{n-2k}(\bar 1,\bar 2)=p_{n-2k}-p_{n-2k-1}-p_{n-2k-2}+p_{n-2k-3}$

Ответ верный, поздравляю!

-- 02.08.2020, 02:44 --

Итак, пусть $A_n^k$ - множество разбиений n, которые не содержат "единиц" и содержат ровно k "двоек".
Сколько в нем разбиений, которые содержат ровно m других чисел?

[maximkarimov]

Последнюю задачу (сколько в $A_n^k$ разбиений, которые содержат ровно m других чисел?) снимаю, так как при проверке своего решения обнаружил ошибку.