#9 Производящие функции I

В произведении \((1+x)^9\) каждый из девяти множителей дает выбор: взять \(1\) или \(x\). Степень \(4\) получается тогда и только тогда, когда \(x\) выбран ровно из четырех множителей. Поэтому коэффициент равен \(\binom{9}{4}=126\). Он считает число четырехэлементных подмножеств девятиэлементного множества.

Искомое число равно коэффициенту при \(x^{14}\) в \(\frac{1}{(1-x)^3}\). Так как \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\), получаем \(\binom{16}{2}=120\).

Без верхней границы решений \(\binom{11}{2}=55\). Если \(a\ge 5\), то \(a'=a-5\) дает \(a'+b+c=4\), откуда \(\binom{6}{2}=15\) решений. Таких переменных три, а две переменные не могут одновременно быть не меньше \(5\), потому что сумма была бы хотя бы \(10\). Ответ: \(55-3\cdot 15=10\).

Нужен коэффициент при \(x^8\) в \(\prod_{i=1}^7(1+x^i)\). Сумма \(8\) получается так: \(1+7\), \(2+6\), \(3+5\), \(1+2+5\), \(1+3+4\). Других вариантов нет: если \(4\) выбран с \(2\), то остается \(2\), но повторять \(2\) нельзя; если выбран \(6\), то остается только \(2\), и так далее. Ответ: \(5\).

С одной стороны, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), поэтому коэффициент при \(x^n\) равен \(\binom{r+s}{n}\). С другой стороны, чтобы получить \(x^n\), можно взять \(x^k\) из первого множителя и \(x^{n-k}\) из второго. Это дает сумму \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). Коэффициенты одного и того же многочлена равны, значит, тождество доказано.

Производящая функция равна \(\frac{1}{(1-x^2)^4}\). Нужно найти коэффициент при \(x^{18}\), то есть коэффициент при \(y^9\) в \(\frac{1}{(1-y)^4}\). Он равен \(\binom{9+3}{3}=\binom{12}{3}=220\).

Число строк с \(k\) единицами равно \(\binom{n}{k}\). Поэтому нужно найти сумму коэффициентов при четных степенях в \((1+x)^n\). Она равна \(\frac{(1+1)^n+(1-1)^n}{2}\). При \(n\ge 1\) получаем \(\frac{2^n+0}{2}=2^{n-1}\).

Пустая композиция для \(0\) дает \(c_0=1\). Для \(n\ge 2\) первая часть равна \(1\) или \(2\), значит, \(c_n=c_{n-1}+c_{n-2}\), причем \(c_1=1\). Для ряда получаем \(C(x)=1+xC(x)+x^2C(x)\), откуда \(C(x)=\frac{1}{1-x-x^2}\). Если \(F_0=0\), \(F_1=1\), то \(c_n=F_{n+1}\).

Без ограничений решений \(\binom{24}{4}=10626\). Если одна коробка содержит хотя бы \(7\), после вычитания \(7\) остается сумма \(13\), что дает \(\binom{17}{4}=2380\) решений; таких коробок \(5\). Если две коробки содержат хотя бы \(7\), остается сумма \(6\), что дает \(\binom{10}{4}=210\) решений; пар коробок \(\binom{5}{2}=10\). Три коробки уже невозможны. Ответ: \(10626-5\cdot 2380+10\cdot 210=826\).

Разложение \(\frac{1}{(1-x)^2(1-x^3)}=(1+x+x^2+\cdots)^2(1+x^3+x^6+\cdots)\) показывает, что коэффициент равен числу троек \((a,b,c)\) таких, что \(a+b+3c=10\). При \(c=0,1,2,3\) получаем соответственно \(11,8,5,2\) решений для \(a+b\). Сумма равна \(11+8+5+2=26\).

Каждое слагаемое \(i\) можно взять либо один раз, либо не брать, поэтому производящая функция равна \(\prod_{i=1}^{11}(1+x^i)\). Перечислим разбиения: \(11\), \(10+1\), \(9+2\), \(8+3\), \(8+2+1\), \(7+4\), \(7+3+1\), \(6+5\), \(6+4+1\), \(6+3+2\), \(5+4+2\), \(5+3+2+1\). Их \(12\).

Коэффициент \(c_k\) равен числу наборов \((a_1,\ldots,a_n)\) таких, что \(0\le a_i\le m\) и \(a_1+\cdots+a_n=k\). Каждому такому набору сопоставим \((m-a_1,\ldots,m-a_n)\). Все новые числа также лежат от \(0\) до \(m\), а их сумма равна \(mn-k\). Это обратимое соответствие, значит, \(c_k=c_{mn-k}\).

Пусть \(b_i=a_i-1\). Тогда \(b_1+\cdots+b_6=18\) и \(0\le b_i\le 6\). Без верхней границы решений \(\binom{23}{5}=33649\). Если один \(b_i\ge 7\), остается сумма \(11\), значит, \(\binom{16}{5}=4368\) решений; таких переменных \(6\). Если два \(b_i\ge 7\), остается сумма \(4\), значит, \(\binom{9}{5}=126\) решений; пар \(\binom{6}{2}=15\). Три переменные не могут быть не меньше \(7\), потому что сумма стала бы отрицательной после вычитания. Ответ: \(33649-6\cdot 4368+15\cdot 126=9331\).

Без верхней границы решений \(\binom{19}{7}=50388\). Если выбранная переменная не меньше \(4\), после вычитания \(4\) остается сумма \(8\), что дает \(\binom{15}{7}=6435\) решений; таких переменных \(8\). Для двух переменных остается сумма \(4\), что дает \(\binom{11}{7}=330\) решений; пар \(\binom{8}{2}=28\). Для трех переменных остается сумма \(0\), что дает \(1\) решение; троек \(\binom{8}{3}=56\). Четыре переменные невозможны. Искомый коэффициент равен

\[50388-8\cdot 6435+28\cdot 330-56=8092.\]

Пусть выбраны \(i_1<\cdots

Если в покрытии ровно \(k\) домино, то оставшихся одиночных клеток \(n-2k\). Сожмем каждое домино в один блок. Тогда всего блоков \(k+(n-2k)=n-k\), и нужно выбрать, какие \(k\) из них являются домино. Это можно сделать \(\binom{n-k}{k}\) способами. Обратное восстановление однозначно: выбранные блоки разворачиваются в домино, остальные остаются одиночными клетками.

Разбиения на различные части кодируются произведением \(\prod_{i\ge 1}(1+x^i)\), потому что каждую часть \(i\) можно взять не больше одного раза. Используем тождество \(1+x^i=\frac{1-x^{2i}}{1-x^i}\):

\[\prod_{i\ge 1}(1+x^i)=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}.\]

В знаменателе есть множители для всех положительных \(i\), а в числителе сокращаются все четные множители. Остается \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\), то есть производящая функция разбиений на нечетные части. Коэффициенты при \(x^n\) равны.

Положим \(y_i=5-x_i\). Тогда \(0\le y_i\le 5\), \(y_1+\cdots+y_8=10\). Условие \(x_1+x_2+x_3\) четно эквивалентно тому, что \(15-(y_1+y_2+y_3)\) четно, то есть \(y_1+y_2+y_3\) нечетно.

Пусть \(A_3(t)\) - число троек от \(0\) до \(5\) с суммой \(t\), а \(A_5(u)\) - число пятерок от \(0\) до \(5\) с суммой \(u\). Нужно сложить \(A_3(t)A_5(10-t)\) по нечетным \(t\). Коэффициенты из \((1+x+\cdots+x^5)^3\) и \((1+x+\cdots+x^5)^5\) дают:

\[3\cdot 540+10\cdot 305+21\cdot 126+27\cdot 35+25\cdot 5=8386.\]

Ответ: \(8386\).

Пусть \(\omega\ne 1\) - кубический корень из единицы, так что \(1+\omega+\omega^2=0\). Если \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), то число коэффициентов со степенью, делящейся на \(3\), равно

\[\frac{F(1)+F(\omega)+F(\omega^2)}{3}.\]

Имеем \(F(1)=2^{3m}\). Среди чисел \(1,\ldots,3m\) по \(m\) чисел каждого остатка \(0,1,2\) по модулю \(3\). Поэтому

\[F(\omega)=(1+1)^m(1+\omega)^m(1+\omega^2)^m=2^m((1+\omega)(1+\omega^2))^m.\]

Но \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), значит, \(F(\omega)=2^m\). Аналогично \(F(\omega^2)=2^m\). Получаем \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).

Пусть \(a_i\in\{0,1,2,3\}\) - сколько грузов веса \(2^i\) взято. Нужно решить \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), то есть получить двоичную запись из \(m\) единиц.

Считаем слева направо по разрядам снизу вверх. Пусть перед очередным разрядом перенос равен \(0\) или \(1\). Если перенос \(0\), чтобы получить единицу в разряде, нужно взять \(a_i=1\) и оставить перенос \(0\), либо \(a_i=3\) и создать перенос \(1\). Если перенос \(1\), нужно взять \(a_i=0\) и получить перенос \(0\), либо \(a_i=2\) и оставить перенос \(1\). Поэтому после каждого из \(m\) разрядов число способов прийти в состояние переноса \(0\) равно числу способов прийти в состояние переноса \(1\), и оба равны сумме двух предыдущих состояний.

После первого разряда получаем по \(1\) способу в состояниях \(0\) и \(1\). После \(m\) разрядов в каждом состоянии \(2^{m-1}\) способов. В конце перенос должен быть \(0\), иначе сумма превысит \(2^m-1\). Значит, ответ \(2^{m-1}\).