#9 Generating Functions I

In the product \((1+x)^9\), each of the nine factors gives a choice: take \(1\) or take \(x\). Degree \(4\) occurs exactly when \(x\) is chosen from four factors. Therefore the coefficient is \(\binom{9}{4}=126\). It counts the four-element subsets of a nine-element set.

The desired number is the coefficient of \(x^{14}\) in \(\frac{1}{(1-x)^3}\). Since \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\), the answer is \(\binom{16}{2}=120\).

Without the upper bound, there are \(\binom{11}{2}=55\) solutions. If \(a\ge 5\), then \(a'=a-5\) gives \(a'+b+c=4\), so there are \(\binom{6}{2}=15\) solutions. There are three possible variables, and two variables cannot both be at least \(5\), because the sum would be at least \(10\). The answer is \(55-3\cdot 15=10\).

We need the coefficient of \(x^8\) in \(\prod_{i=1}^7(1+x^i)\). The sum \(8\) is obtained as \(1+7\), \(2+6\), \(3+5\), \(1+2+5\), and \(1+3+4\). There are no other possibilities: for instance, if \(4\) is chosen with \(2\), the remaining \(2\) cannot be repeated; if \(6\) is chosen, only \(2\) remains, and so on. The answer is \(5\).

On one hand, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), so the coefficient of \(x^n\) is \(\binom{r+s}{n}\). On the other hand, to obtain \(x^n\), we may take \(x^k\) from the first factor and \(x^{n-k}\) from the second. This gives \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). The coefficients of the same polynomial are equal, so the identity is proved.

The generating function is \(\frac{1}{(1-x^2)^4}\). We need the coefficient of \(x^{18}\), equivalently the coefficient of \(y^9\) in \(\frac{1}{(1-y)^4}\). This is \(\binom{9+3}{3}=\binom{12}{3}=220\).

The number of strings with \(k\) ones is \(\binom{n}{k}\). Thus we need the sum of coefficients of even powers in \((1+x)^n\). It equals \(\frac{(1+1)^n+(1-1)^n}{2}\). For \(n\ge 1\), this is \(\frac{2^n+0}{2}=2^{n-1}\).

The empty composition of \(0\) gives \(c_0=1\). For \(n\ge 2\), the first part is \(1\) or \(2\), so \(c_n=c_{n-1}+c_{n-2}\), with \(c_1=1\). For the series, \(C(x)=1+xC(x)+x^2C(x)\), hence \(C(x)=\frac{1}{1-x-x^2}\). If \(F_0=0\), \(F_1=1\), then \(c_n=F_{n+1}\).

Without restrictions, there are \(\binom{24}{4}=10626\) solutions. If one box contains at least \(7\), subtracting \(7\) leaves sum \(13\), giving \(\binom{17}{4}=2380\) solutions; there are \(5\) boxes. If two boxes contain at least \(7\), the remaining sum is \(6\), giving \(\binom{10}{4}=210\) solutions; there are \(\binom{5}{2}=10\) pairs. Three such boxes are impossible. The answer is \(10626-5\cdot 2380+10\cdot 210=826\).

The expansion \(\frac{1}{(1-x)^2(1-x^3)}=(1+x+x^2+\cdots)^2(1+x^3+x^6+\cdots)\) shows that the coefficient equals the number of triples \((a,b,c)\) such that \(a+b+3c=10\). For \(c=0,1,2,3\), the numbers of solutions for \(a+b\) are \(11,8,5,2\), respectively. The sum is \(11+8+5+2=26\).

Each part \(i\) can be taken either once or not at all, so the generating function is \(\prod_{i=1}^{11}(1+x^i)\). The partitions are \(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\). There are \(12\) of them.

The coefficient \(c_k\) equals the number of tuples \((a_1,\ldots,a_n)\) such that \(0\le a_i\le m\) and \(a_1+\cdots+a_n=k\). Map such a tuple to \((m-a_1,\ldots,m-a_n)\). The new numbers still lie between \(0\) and \(m\), and their sum is \(mn-k\). This correspondence is reversible, so \(c_k=c_{mn-k}\).

Let \(b_i=a_i-1\). Then \(b_1+\cdots+b_6=18\) and \(0\le b_i\le 6\). Without the upper bound, there are \(\binom{23}{5}=33649\) solutions. If one \(b_i\ge 7\), the remaining sum is \(11\), giving \(\binom{16}{5}=4368\) solutions; there are \(6\) choices of the variable. If two \(b_i\ge 7\), the remaining sum is \(4\), giving \(\binom{9}{5}=126\) solutions; there are \(\binom{6}{2}=15\) pairs. Three variables cannot be at least \(7\), because the remaining sum would be negative. The answer is \(33649-6\cdot 4368+15\cdot 126=9331\).

Without the upper bound, there are \(\binom{19}{7}=50388\) solutions. If a chosen variable is at least \(4\), subtracting \(4\) leaves sum \(8\), giving \(\binom{15}{7}=6435\) solutions; there are \(8\) choices of the variable. For two variables, the remaining sum is \(4\), giving \(\binom{11}{7}=330\) solutions; there are \(\binom{8}{2}=28\) pairs. For three variables, the remaining sum is \(0\), giving \(1\) solution; there are \(\binom{8}{3}=56\) triples. Four variables are impossible. The desired coefficient is

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

Let the chosen numbers be \(i_1<\cdots

If a tiling has exactly \(k\) dominoes, then the number of single squares is \(n-2k\). Compress each domino into one block. Then there are \(k+(n-2k)=n-k\) blocks in total, and we only need to choose which \(k\) of them are dominoes. This can be done in \(\binom{n-k}{k}\) ways. The reconstruction is unique: chosen blocks expand into dominoes, and the others remain single squares.

Partitions into distinct parts are encoded by \(\prod_{i\ge 1}(1+x^i)\), because each part \(i\) may be taken at most once. Use \(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)}.\]

The denominator contains factors for all positive \(i\), while the numerator cancels all even factors. What remains is \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\), the generating function for partitions into odd parts. Therefore the coefficients of \(x^n\) are equal.

Set \(y_i=5-x_i\). Then \(0\le y_i\le 5\) and \(y_1+\cdots+y_8=10\). The condition that \(x_1+x_2+x_3\) is even is equivalent to \(15-(y_1+y_2+y_3)\) being even, so \(y_1+y_2+y_3\) is odd.

Let \(A_3(t)\) be the number of triples from \(0\) to \(5\) with sum \(t\), and let \(A_5(u)\) be the number of 5-tuples from \(0\) to \(5\) with sum \(u\). We need to sum \(A_3(t)A_5(10-t)\) over odd \(t\). Coefficients of \((1+x+\cdots+x^5)^3\) and \((1+x+\cdots+x^5)^5\) give:

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

The answer is \(8386\).

Let \(\omega\ne 1\) be a cube root of unity, so \(1+\omega+\omega^2=0\). If \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), then the number of coefficients whose degree is divisible by \(3\) is

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

We have \(F(1)=2^{3m}\). Among the numbers \(1,\ldots,3m\), each residue \(0,1,2\) modulo \(3\) appears \(m\) times. Hence

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

But \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), so \(F(\omega)=2^m\). Similarly \(F(\omega^2)=2^m\). Thus the answer is \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).

Let \(a_i\in\{0,1,2,3\}\) be the number of weights \(2^i\) taken. We need to solve \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), whose binary form consists of \(m\) ones.

Process the digits from low to high. Before each digit, the carry is \(0\) or \(1\). If the carry is \(0\), then to obtain a one in this digit we may take \(a_i=1\) and keep carry \(0\), or take \(a_i=3\) and create carry \(1\). If the carry is \(1\), then we may take \(a_i=0\) and get carry \(0\), or take \(a_i=2\) and keep carry \(1\). Thus after each of the \(m\) digits, the number of ways to reach carry \(0\) equals the number of ways to reach carry \(1\), and both are the sum of the two previous states.

After the first digit, there is \(1\) way in each state. After \(m\) digits, each state has \(2^{m-1}\) ways. At the end, the carry must be \(0\); otherwise the sum exceeds \(2^m-1\). Therefore the answer is \(2^{m-1}\).