Простой вопрос про число разбиений

[kthxbye]

Пусть $p(n)$ это A000041 (т.е. число разбиений $n$).

Пусть $a(n,m)$ это семейство целочисленных последовательностей с производящими функциями $A_m(x)$, такими, что

$$ A_m(x) = \left(-1 + \prod\limits_{j\geqslant1}(1-x^j)\right)^m. $$

После множества численных экспериментов, я заметил, что, по всей видимости

$$ \sum\limits_{i=0}^{n}a(n,i)(-1)^i = p(n). $$

Вот код на PARI/GP для проверки:

test1(n) = my(x = 'x, A = -1 + prod(j=1, n, (1 - x^j)) + x*O(x^n)); sum(i=0, n, (-1)^i*polcoeff(A^i, n, x)) == numbpart(n)

Если гипотеза верна, то как можно ее доказать? Насколько это вообще очевидно исходя из известных свойств числа разбиений?

[dgwuqtj]

А вы можете получить комбинаторную формулу для $a(n, i)$, без производящих функций?

[kthxbye]

dgwuqtj в сообщении #1653503 писал(а):

А вы можете получить комбинаторную формулу для $a(n, i)$, без производящих функций?

Это намек на то, что вопрос сводится к тривиальному или наоборот?

Для случая $m=2$ в OEIS есть похожая A047654, которую отличает от нашей лишь знакочередование. На ее странице приведена программа на языке Maple, где видно, что можно совершить какие-то манипуляции с делителями, чтобы рекурсивно задавать $a(n,m)$.

Я тоже сначала думал, что есть что-нибудь попроще, но так и не нашел. Так что тут нужны эксперты по Maple.

[dgwuqtj]

Это намёк на то, что надо вам попробовать это дело как-то поупрощать. Вдруг докажется. Моя интуиция подсказывает, что получится.

[kthxbye]

На странице A047654 есть еще ссылка H. Gupta, On the coefficients of the powers of Dedekind's modular form (annotated and scanned copy). Там много интересного. Пока разбираюсь. Увы, моего результата там, по всей видимости, нет.

[dgwuqtj]

Модулярные формы — это замечательно, конечно, но тут просто комбинаторика с производящими функциями.

[kthxbye]

Там почти все то же самое. У меня

$$A_m(x) = \left(-1 + \prod\limits_{j\geqslant1}(1-x^j)\right)^m.$$

а там рассматривается

$$\left(\prod\limits_{j\geqslant1}(1-x^j)\right)^r = \sum\limits_{n=0}^{\infty}p_r(n)x^n.$$

Базовые условия это $p_r(0)=1$ при любом $r$, а также $p_0(n)=0$ при $n \geqslant 1$.

Дальше он указывает, что

$$p_r(n) = -\frac{r}{n}\sum\limits_{j=1}^{n}\sigma(j)p_r(n-j).$$

Здесь

$$\sigma(n) = \sum\limits_{d|n}d.$$

Судя по дальнейшему и просто моим наблюдениям

$$p_r(n) = \sum\limits_{i=0}^{r}\binom{r}{i}a(n,i).$$

Введем

$$q_r(n) = \frac{r}{n}\sum\limits_{j=1}^{n}\sigma(j)q_r(n-j).$$

с базовым условиями $q_r(0)=1$ при любом $r$, а также $q_0(n)=0$ при $n \geqslant 1$.

И вот теперь вся хитрость заключается в том, чтобы показать, что

$$q_r(n) = \sum\limits_{i=0}^{n}\binom{i+r-1}{r-1}a(n,i)(-1)^i.$$

Это уже обобщенная гипотеза.

[dgwuqtj]

Ну, давайте попробуем.
\begin{align*} \sum_{i = 0}^n (-1)^i a(n, i) &= [x^n] \sum_{i = 0}^n (-1)^i (-1 + \prod_{j = 1}^\infty (1 - x^j))^i \\&= [x^n] \frac{1 + (-1 + \prod_{j = 1}^\infty (1 - x^j))^{n + 1}}{1 + (-1 + \prod_{j = 1}^\infty (1 - x^j))} \\&= [x^n] \prod_{j = 1}^\infty (1 - x^j)^{-1} + [x^n] \sum_{k = 0}^{n + 1} \binom{n + 1}k (-1)^k \prod_{j = 1}^\infty (1 - x^j)^{n - k}. \end{align*}
Первое слагаемое как раз будет числом разбиений. Как подсказывает проверка вольфрамальфой при $n = 4, 5$, сумма во втором слагаемом вообще должна быть $O(x^{n + 1})$. Так что дальше можно возиться с проверкой того, что

$$\sum_{k = 0}^{n + 1} \binom{n + 1}k (-1)^k \prod_{j = 1}^\infty (1 - x^j)^{n + 1 - k} = \bigl(\prod_{j = 1}^\infty (1 - x^j) - 1\bigr)^{n + 1}$$

есть $O(x^{n + 1})$. Это лично мне очевидно, а вам?