Generating Functions

We use the same trick as in the previous problem. We start from \[F(X)=X+2X^2+3X^3+4X^4+5X^5\cdots,\] then find \[XF(X)=X^2+2X^3+3X^4+4X^5+5X^6+\cdots\] and subtract the two: \[(1-X)F(X)=X+X^2+X^3+X^4+\cdots = X\cdot \left(1+X+X^2+\cdots\right)=\frac{X}{1-X},\] where the last equality follows from the previous example. Hence \(F(X)=\frac{X}{(1-X)^2}\).

Let us denote by \(a_n\) the number of ways to distribute \(n\) apples to \(5\) students. We will find the generating function for the sequence \((a_n)_{n=0}^{\infty}\), i.e. we will find the function \(F\) such that

We start from defining \(a_0=1\), and notice that \(a_1=1\). To each distribution of \(n\) apples to students we may correspond an ordered \(5\)-tuple \((\gamma_1,\gamma_2,\gamma_3,\gamma_4,\gamma_5)\) of non-negative integers that add up to \(n\). This 5-tuple represents that the first student got \(\gamma_1\) apples, the second \(\gamma_2\), etc.

To each 5-tuple \((\gamma_1,\dots, \gamma_5)\) such that \(\gamma_1+\cdots+\gamma_5=n\) we correspond a term \(X^{\gamma_1}\cdot X^{\gamma_2}\cdots X^{\gamma_5}\), and notice that this correspondence is a bijection. Then we notice that \(X^{\gamma_1}\cdots X^{\gamma_5}= X^{\gamma_1+\gamma_2+\cdots+ \gamma_5}\), hence \[F(X)=\left(1+X+X^2+\cdots\right)\cdot \left(1+X+X^2+\cdots\right)\cdot \left(1+X+X^2+\cdots\right)\cdot \left(1+X+X^2+\cdots\right)\cdot \left(1+X+X^2+\cdots\right).\] Thus, \[F(X)=\left(1+X+X^2+\cdots\right)^5=\frac1{4!}\cdot \frac{d^4}{dX^4}\frac1{1-X}=\frac1{24}\cdot \frac{d^4}{dX^4}\left(1+X+X^2+X^3+\cdots\right).\] Now we can find the coefficient of \(X^{15}\) as \(\frac{19\cdot 18\cdot 17\cdot 16}{4!}=\binom {19}4\).

We know that \(N_k\) is the coefficient of \(X^{n-k+1}\) in:

Notice that \(N_k\) can be seen as the coefficient of \(X^{n+1}\) in:

Hence \(N_1+N_2+\cdots+ N_{n+1}\) is the coefficient of \(X^{n+1}\) in the expansion

where \(R\) is any integer that is larger than \(n+1\). Let us denote

Now we can write

Subtracting the second inequality from the first yields: \((1-X)F_R(X)=\frac1{1-X}-\frac1{1-X^{R+1}}\) hence

Hence the coefficient of \(X^{n+1}\) in \(F_R(X)\) is \((-1)^{n+1}\binom{-2}{n+1}-1=n+1\).

Let us denote by \(a_n\) the sum of \(A(\pi)\) over all partitions \(\pi\) of \(n\). Let \(b_n\) be the sum of \(B(\pi)\) taken over all partitions \(\pi\) of \(n\).

Let \(A(x)=a_0+a_1x+a_2x^2+\cdots\) and \(B(x)=b_0+b_1x+b_2x^2+\cdots\) be the generating functions of the sequences \((a_n)_{n=0}^{\infty}\) and \((b_n)_{n=0}^{\infty}\). We will prove that \(A(x)=B(x)\).

Notice that \begin{eqnarray*}A(x)&=&\left(x+2x^2+3x^3+\cdots \right)\cdot \left(1+x^2+x^4+\cdots\right)\cdot \left(1+x^3+x^6+x^9+\cdots\right)\cdots\newline &=& xP’(x)\cdot P(x^2)\cdot P(x^3)\cdot P(x^4)\cdots\end{eqnarray*} where \(P(x)=1+x+x^2+\cdots\).

In order to find \(B(x)\) we start by forming \[G(x,y)=\left(1+yx+yx^2+yx^3+\cdots\right)\cdot\left(1+yx^2+yx^4+yx^6+\cdots\right)\cdot \left(1+yx^3+yx^6+yx^9+\cdots\right)\cdots\] and noticing that for \(H(x,y)=\frac{\partial}{\partial y}G(x,y)\) we have \(B(x)=H(x,1)\).

The partial derivative of \(G\) with respect to \(y\) can be found using the product rule: \begin{eqnarray*} \frac{\partial }{\partial y}G(x,y)&=&\left(x+x^2+x^3+\cdots\right)\cdot\left(1+yx^2+yx^4+yx^6+\cdots\right)\cdot \left(1+yx^3+yx^6+yx^9+\cdots\right)\cdots\newline &&+ \left(1+yx+yx^2+yx^3+\cdots\right)\cdot\left(x^2+x^4+x^6+\cdots\right)\cdot \left(1+yx^3+yx^6+yx^9+\cdots\right)\cdots\newline &&+ \left(1+yx+yx^2+yx^3+\cdots\right)\cdot\left(1+yx^2+yx^4+yx^6+\cdots\right)\cdot \left(x^3+x^6+x^9+\cdots\right)\cdots +\cdots. \end{eqnarray*} Hence \begin{eqnarray*}B(x)&=&H(x,1)=xP(x)P(x^2)P(x^3)\cdots+ x^2P(x)P(x^2)P(x^3)\cdots+\cdots\newline&=& \left(x+x^2+x^3+\cdots\right)\cdot P(x)P(x^2)P(x^3)\cdots \newline &=& xP(x)\cdot P(x)\cdot P(x^2)P(x^3)\cdots\end{eqnarray*} It remains to verify that \(P^{\prime}(x)=P(x)^2\) which is obvious from \(P(x)=\frac1{1-x}\).

Consider the function \(H(X)=\sum_{k=0}^{\infty}\frac{a_k}{k!}X^k\). This is the exponential generating function of the sequence \((a_k)_{k=0}^{\infty}\).

Assume that the objects are chosen from the set \(\{1,2,\dots, p\}\). Let \(a_k(d_1, d_2,\dots, d_p)\) be the number of ways to arrange in a line \(k\) objects such that \(d_1\) of them are \(1\), \(d_2\) of them are \(2\), \(\dots\), \(d_p\) of them are \(p\). Then \(a_k=\sum a_k(d_1, d_2, \dots, d_p)\) where the summation is over all sequences \((d_1, \dots, d_p)\) of non-negative integers such that \(d_1+\cdots+ d_p=k\). We know that \(a_k(d_1, \dots, d_p)=\frac{k!}{d_1!\cdot d_2!\cdots d_p!}\), and

The last summation is over all sequences \((d_1, \dots, d_p)\) of non-negative integers such that \(d_1+\cdots+ d_p=k\). Therefore \(\frac{a_k}{k!}\) is the coefficient of \(X^k\) in the expansion \(\left(1+\frac1{1!}X+\frac1{2!}X^2+\cdots\right)^p\) hence \(H(X)=e^{pX}=1+\frac{pX}{1!}+\frac{p^2X^2}{2!}+\cdots\) and \(a_k=p^k\).

Let \(\alpha_l\) be the number of sequences of steps of size \(l\) after which lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are all off. Then \(N=\alpha_k\). Let \(\beta_l\) be the number of sequences of steps of size \(l\) after which lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are never switched on. We get \(M=\beta_k\).

Then we look at the functions \(f(X)=\sum_{k=0}^{\infty} \frac{\alpha_k}{k!}X^k\) and \(g(X)=\sum_{k=0}^{\infty}\frac{\beta_k}{k!}X^k\). Then we have

Let \(\phi(X)=\frac12(e^X-e^{-X})\) (by the way this is hyperbolic sine, denoted by \(\sinh\), but you are allowed to forget this, it’s not really needed). Then \(f(X)=\frac1{2^n}\phi(2X)^n\) and \(g(X)=\phi(X)^n\). The coefficient of \(X^k\) in \(f\) is equal to \(\frac{\alpha_k}{k!}\) and on the right it is \(\frac1{k!}\beta_k\). Hence we have \(\frac{\alpha_k}{k!}=\frac1{2^n}\cdot 2^k\cdot \frac{\beta_k}{k!}\). Hence \(\frac{N}{M}=\frac{\alpha_k}{\beta_k}=2^{k-n}\).