Generating Functions: Problems and Solutions

According to the Theorem 7 the generating function of the sum of first \(n\) terms of the sequence (i.e. the left-hand side) is equal to \(F/(1-x)\), where \(F=x/(1-x-x^2)\) (such \(F\) is the generating function of the Fibonacci sequence). On the right-hand side we have \[\frac {F-x}x-\frac 1{1-x},\] and after some obvious calculation we arrive to the required identity.

We will first prove that the generating function of the number of odd partitions is equal to \[(1+x+x^2+\cdots)\cdot(1+x^3+x^6+\cdots) \cdot(1+x^5+x^{10}+\cdots)\cdots= \prod_{k\geq1}\frac 1{1-x^{2k+1}}.\] Indeed, to each partition in which \(i\) occurs \(a_i\) times corresponds exactly one term with coefficient \(1\) in the product. That term is equal to \(x^{1\cdot a_1+3\cdot a_3+5\cdot a_5+\cdots}\).

The generating function to the number of partitions in different summands is equal to \[(1+x)\cdot(1+x^2)\cdot(1+x^3)\cdots = \prod_{k\geq1}(1+x^k),\] because from each factor we may or may not take a power of \(x\), which exactly correpsonds to taking or not taking the corresponding summand of a partition. By some elementary transformations we get \[\prod_{k\geq1} (1+x^k) = \prod_{k\geq1}\frac{1-x^{2k}}{1-x^k}= \frac {(1-x^2)(1-x^4)\cdots} {(1-x)(1-x^2)(1-x^3)(1-x^4)\cdots}= \prod_{k\geq1}\frac 1{1-x^{2k+1}}\] which proves the statement.

This example illustrates the usefulness of the exponential generating functions. This problem is known as derangement problem posed by Pierre R. de Montmort (1678-1719).

Assume that the required number is \(D_n\) and let \(D(x)\genfrac{}{}{0pt}{}{es}{\leftrightarrow} D_n\). The number of permutations having exactly \(k\) given fixed points is equal to \(D_{n-k}\), hence the total number of permutations with exactly \(k\) fixed points is equal to \(\binom nk D_{n-k}\), because we can choose \(k\) fixed points in \(\binom nk\) ways. Since the total number of permutations is equal to \(n!\), then \[n!=\sum_k \binom{n}{k} D_{n-k}\] and the Theorem 10 gives \[\frac 1{1-x}=e^xD(x)\] implying \(D(x)=e^{-x}/(1-x)\). Since \(e^{-x}\) is the generating function of the sequence \(\dfrac {(-1)^n}{n!}\), we get \[\frac {D_n}{n!} = 1-1+\frac1{2!}-\frac1{3!}+ \cdots+(-1)^n\frac1{n!},\] \[D_n = n!\cdot \left(\frac1{2!}-\frac1{3!}+ \cdots+(-1)^n\frac1{n!} \right).\]

The idea here is to consider the generating function \[F(x)=\sum_k\binom{n}{3k}x^{3k}.\] The required sum is equal to \(f(-1)\). The question now is how to make binomial formula to skip all terms except those of order \(3k\). We will use the following identy for the sum of roots of unity in the complex plane \[ \sum_{\varepsilon^r=1}\varepsilon^n= \left\{\begin{array}{rl} r, & r|n\newline 0, & \mbox{otherwise.} \end{array} \right.\] Let \(C(x)=(1+x)^n\) and let \(1\), \(\varepsilon\), and \(\varepsilon^2\) be the cube roots of 1. Then we have \[F(x)=\frac {C(x)+C(\varepsilon x)+C(\varepsilon^2 x)}3\] which for \(x=-1\) gives \[F(-1)=\frac 13\left\{\left(\frac {3-i\sqrt{3}}2\right)^n+\left(\frac {3+i\sqrt{3}}2\right)^n\right\}\] and after simplification \[\sum_k (-1)^k \binom{n}{3k}=2\cdot3^{n/2-1}\cos\left(\frac {n\pi}6\right).\]

The number of solutions of \(x+2y=n\) in \({\mathbb N_0^2}\) is the coefficient near \(t^n\) in \[(1+t+t^2+\cdots)\cdot(1+t^2+t^4+\cdots)= \frac 1{1-t}\frac 1{1-t^2}\] The reason is that each pair \((x,y)\) that satisfies the condition of the problem increases the coefficient near \(t^n\) by \(1\) because it appears as a summand of the form \(t^xt^{2y}=t^{x+2y}\). More generally, the number of solutions of \(kx+(k+1)y=n+1-k\) is the coefficient near \(t^{n+1-k}\) in \(\dfrac 1{1-t^k}\dfrac 1{1-t^{k+1}}\), i.e. the coefficient near \(t^n\) in \(\dfrac {x^{k-1}}{(1-t^k)(1-t^{k+1})}\). Hence, \( \sum_{k=1}^n R_k\) is the coefficient near \(t^n\) in \( \sum_k \frac {t^{k-1}}{(1-t^k)(1-t^{k+1})} = \sum_k \frac 1{t-t^2} \left(\frac 1{1-t^{k+2}}-\frac 1{1-t^{k+1}}\right)=\frac 1{(1-t)^2}\). Now it is easy to see that \( \sum_k R_k=n+1\).

The generating function of the symmetric polynomials \(\sigma_k(x_1,\dots, x_n)\) is \[\Sigma(t)=\sum_{k=0}^{\infty} \sigma_kt^k=\prod_{i=1}^n(1+tx_i).\] The generating function of the polynomials \(p_k(x_1,\dots, x_n)\) is: \[P(t)=\sum_{k=0}^{\infty} p_kt^k=\prod \frac1{1-tx_i},\] and the generating function of the polynomials \(s_k\) is: \[S(t)=\sum_{k=0}^{\infty} s_kt^{k-1}=\sum_{i=1}^n \frac{x_i}{1-tx_i}.\] The functions \(\Sigma(t)\) and \(P(t)\) satisfy the following condition \(\Sigma(t)p(-t)=1\). If we calculate the coefficient of this product near \(t^n\), \(n\geq1\) we get the relation \[\sum_{r=0}^n (-1)^r\sigma_rp_{n-r}=0.\] Notice that \[\log P(t)=\sum_{i=1}^n \log \frac 1{1-tx_i} \qquad \mbox{and} \qquad \log \Sigma(t)=\sum_{i=1}^n \log (1+tx_i).\] Now we can express \(S(t)\) in terms of \(P(t)\) and \(\Sigma(t)\) by: \[S(t)=\frac d{dt}\log P(t)=\frac{P^{\prime}(t)}{P(t)}\] and \[S(-t)=-\frac d{dt}\log\Sigma(t)=-\frac{\Sigma ^{\prime}(t)}{\Sigma(t)}.\] From the first formula we get \(S(t)P(t)=P^{\prime}(t)\), and from the second \(S(-t)\Sigma(t)=-\Sigma^{\prime}(t)\). Comparing the coefficients near \(t^{n+1}\) we get \[np_n=\sum_{r=1}^n s_rp_{n-r} \qquad \mbox{and} \qquad n\sigma_n=\sum_{r=1}^n (-1)^{r-1}s_r\sigma_{n-r}.\]

Let \(F\) and \(G\) be polynomials generated by the given sequence: \(F(x)=x^{a_1}+x^{a_2}+\dots+x^{a_n}\) and \(G(x)=x^{b_1}+x^{b_2}+\dots+x^{b_n}\). Then \[ F^2(x)-G^2(x)=\left( \sum_{i=1}^nx^{2a_i}+ 2\sum_{1\leqslant i\leqslant j \leqslant n}x^{a_i+a_j}\right)- \left( \sum_{i=1}^nx^{2b_i}+2\sum_{1\leqslant i\leqslant j \leqslant n}x^{b_i+b_j}\right)\] \[ =F(x^2)-G(x^2).\] Since \(F(1)=G(1)=n\), we have that 1 is zero of the order \(k, (k\geq 1)\) of the polynomial \(F(x)-G(x)\). Then we have \(F(x)-G(x)=(x-1)^kH(x)\), hence \[F(x)+G(x)=\frac{F^2(x)-G^2(x)}{F(x)-G(x)}= \frac{F(x^2)-G(x^2)}{F(x)-G(x)}= \frac{(x^2-1)^kH(x^2)}{(x-1)^kH(x)}= (x+1)^k\frac{H(x^2)}{H(x)}\] Now for \(x=1\) we have: \[2n=F(1)+G(1)=(1+1)^k\frac{H(x^2)}{H(x)}=2^k,\] implying that \(n=2^{k-1}\).

Consider the polynomials generated by the numbers from different sets: \[A(x)=\sum_{a\in A}x^a,\quad B(x)=\sum_{b\in B}x^b.\] The condition that \(A\) and \(B\) partition the whole \(\mathbb N\) without intersection is equivalent to \[A(x)+B(x)=\frac1{1-x}.\] The number of ways in which some number can be represented as \(a_1+a_2, \enspace a_1,a_2\in A,\enspace a_1\neq a_2\) has the generating function: \[\sum_{a_i,a_j\in A, a_i\neq a_j}x^{a_i+a_j}=\frac12\left(A^2(x)-A(x^2)\right).\] Now the second condition can be expressed as \[\left(A^2(x)-A(x^2)\right)=\left(B^2(x)-B(x^2)\right).\] We further have \[(A(x)-B(x))\frac1{1-x}=A(x^2)-B(x^2)\] or equivalently \[(A(x)-B(x))=(1-x)(A(x^2)-B(x^2)).\] Changing \(x\) by \(x^2,x^4,\dots,x^{2^{n-1}}\) we get \[A(x)-B(x)=(A(x^{2^n})-B(x^{2^n}))\prod_{i=0}^{n-1} (1-x^{2^i}),\] implying \[A(x)-B(x)=\prod_{i=0}^{\infty}(1-x^{2^i}).\] The last product is series whose coefficients are \(\pm 1\) hence \(A\) and \(B\) are uniquely determined (since their coefficients are \(1\)). It is not difficult to notice that positive coefficients (i.e. coefficients originating from \(A\)) are precisely those corresponding to the terms \(x^n\) for which \(n\) can be represented as a sum of even numbers of \(2\)s. This means that the binary partition of \(n\) has an even number of \(1\)s. The other numbers form \(B\).

Remark: The sequence representing the parity of the number of ones in the binary representation of \(n\) is called Morse sequence.

This problem is posed by Erdos (in slightly different form), and was solved by Mirsky and Newman after many years. This is their original proof: Assume that \(k\) arithmetic progressions \(\{a_i+nb_i\} \enspace (i=1,2,\dots,k)\) cover the entire set of positive integers. Then \( \frac{z^a}{1-z^b}=\sum_{i=0}^{\infty}z^{a+ib}\), hence \[\frac{z}{1-z}=\frac{z^{a_1}}{1-z^{b_1}}+ \frac{z^{a_2}}{1-z^{b_2}}+ \dots+\frac{z^{a_k}}{1-z^{b_k}}.\] Let \(|z|\leqslant 1\). We will prove that the biggest number among \(b_i\) can’t be unique. Assume the contrary, that \(b_1\) is the greatest among the numbers \(b_1,b_2,\dots,b_n\) and set \(\varepsilon =e^{2i\pi /b_1}\). Assume that \(z\) approaches \(\varepsilon\) in such a way that \(|z|\leqslant 1\). Here we can choose \(\varepsilon\) such that \(\varepsilon^{b_1}=1\), \(\varepsilon \neq 1\), and \(\varepsilon^{b_i}\neq 1,\enspace 1 < i\leqslant k\). All terms except the first one converge to certain number while the first converges to \(\infty\), which is impossible.

Friday the 13th corresponds to Sunday the 1st. Denote the days by numbers \(1,2,3,\dots\) and let \(t^i\) corresponds to the day \(i\). Hence, \(Jan. 1st 2001\) is denoted by \(1\) (or \(t\)), \(Jan. 4th 2001\) by \(t^4\) etc. Let \(A\) be the set of all days (i.e. corresponding numbers) which happen to be the first in a month. For instance, \(1\in A\), \(2\in A\), etc. \(A=\{1,32,60,\dots\}\). Let \(f_A(t)=\sum_{n\in A}t^n\). If we replace \(t^{7k}\) by \(1\), \(t^{7k+1}\) by \(t\), \(t^{7k+2}\) by \(t^2\) etc. in the polynomial \(f_A\) we get another polynomial -- denote it by \(g_A(t)=\sum_{i=0}^6a_it^i\). Now the number \(a_i\) represents how many times the day (of a week) denoted by \(i\) has appeared as the first in a month. Since \(Jan 1, 2001\) was Monday, \(a_1\) is the number of Mondays, \(a_2\)- the number of Tuesdays, \(\dots\), \(a_0\)- the number of Sundays. We will consider now \(f_A\) modulus \(t^7-1\). The polynoimal \(f_A(t)-g_A(t)\) is divisible by \(t^7-1\). Since we only want to find which of the numbers \(a_0,a_1, \dots, a_6\) is the biggest, it is enough to consider the polynomial modulus \(q(t)=1+t+t^2+\cdots + t^6\) which is a factor of \(t^7-1\). Let \(f_1(t)\) be the polynomial that represents the first days of months in \(2001\). Since the first day of January is Monday, Thursday-- the first day of February, ..., Saturday the first day of December, we get \[f_1(t)= t+t^4+t^4+1+t^2+t^5+1+t^3+t^6+t+t^4+t^6=\] \[=2+2t+t^2+t^3+3t^4+t^5+2t^6\equiv 1+t+2t^4+t^6 \mbox{ (mod }q(t)).\] Since the common year has \(365\equiv 1 \) (mod 7) days, polynomials \(f_2(t)\) and \(f_3(t)\) corresponding to 2002.\ and 2003., satisfy \[f_2(t)\equiv tf_1(t)\equiv tg_1(t)\] and \[f_3(t)\equiv tf_2(t)\equiv t^2g_1(t),\] where the congruences are modulus \(q(t)\). Using plain counting we easily verify that \(f_4(t)\) for leap 2004 is \[f_4(t)=2+2t+t^2+2t^3+3t^4+t^5+ t^6\equiv 1+t+t^3+2t^4=g_4(t).\] We will introduce a new polynomial that will count the first days for the period \(2001-2004\) \(h_1(t)=g_1(t)(1+t+t^2)+g_4(t)\). Also, after each common year the days are shifted by one place, and after each leap year by \(2\) places, hence after the period of \(4\) years all days are shifted by \(5\) places. In such a way we get a polynomial that counts the numbers of first days of months between \(2001\) and \(2100\). It is: \[p_1(t)=h_1(t)(1+t^5+t^{10}+\cdots+t^{115})+ t^{120}g_1(t)(1+t+t^2+t^3).\] Here we had to write the last for years in the form \(g_1(t)(1+t+t^2+t^3)\) because 2100 is not leap, and we can’t replace it by \(h_1(t)\). The period of 100 years shifts the calendar for \(100\) days (common years) and additional 24 days (leap) which is congruent to \(5\) modulus 7. Now we get \[g_A(t)\equiv p_1(t)(1+t^5+t^{10})+t^{15}h_1(t)(1+t^5+\cdots+ t^{120}).\] Similarly as before the last \(100\) are counted by last summands because \(2400\) is leap. Now we will use that \(t^{5a}+t^{5(a+1)}+\cdots+t^{5(a+6)}\equiv 0\). Thus \(1+t^5+\cdots+t^{23\cdot5}\equiv 1+t^5+t^{2\cdot5}\equiv 1+t^3+t^5\) and \(1+t^5+\cdots+t^{25\cdot5}\equiv 1+t^5+t^{2\cdot5}+t^{4\cdot5}\equiv 1+t+t^3+t^5\). We further have that \[p_1(t)\equiv h_1(t)(1+t^3+t^5)+ tg_1(t)(1+t+t^2+t^3)\equiv\] \[g_1(t)[(1+t+t^2)(1+t^3+t^5)+t(1+t+t^2+t^3)]+g_4(t)(1+t^3+t^5)\equiv\] \[g_1(t)(2+2t+2t^2+2t^3+2t^4+2t^5+t^6)+g_4(t)(1+t^3+t^5)\equiv -g_1(t)t^6+g_4(t)(1+t^3+t^5).\] If we now put this into formula for \(g_A(t)\) we get \[ g_A(t)\equiv p_1(t)(1+t^3+t^5)+th_1(t)(1+t+t^3+t^5) \] \[ \equiv -g_1(t)t^6(1+t^3+t^5)+g_4(t)(1+t^3+t^5)^2\] \[ +tg_1(t) (1+t+t^2)(1+t+t^3+t^5) +tg_4(t)(1+t+t^3+t^5)\] \[ \equiv g_1(t)(t+t^3)+g_4(t)(2t+2t^3+t^5+t^6)\] \[\equiv (1+t+2t^4+t^6)(t+t^3)+(1+t+t^3+2t^4)(2t+2t^3+t^5+t^6)\] \[\equiv 8+4t+7t^2+5t^3+5t^4+7t^5+4t^6\equiv 4+3t^2+t^3+t^4+3t^5. \] This means that the most probable day for the first in a month is Sunday (because \(a_0\) is the biggest).

We can precisely determine the probability. If we use the fact that there are \(4800\) months in a period of \(400\), we can easily get the Sunday is the first exactly 688 times, Monday -- 684, Tuesday -- 687, Wednesday -- 685, Thursday -- 685, Friday -- 687, and Saturday -- 684.