Generating Functions
Two examples
The fastest way to learn and understand the method of generating functions is to look at the following two problems. You have to read the solutions below the problems, even if you find them boring.
Problem (Combinatorics)
Find the number of ways to distribute 4 identical apples to 3 different students. All apples have to be distributed, and each student is allowed to have from 0 to 4 apples.
 
Problem (Algebra)
Find the coefficient of \( X^4 \) in the expansion of the polynomial \[ P(X)=\left(1+X+X^2+X^3+X^4+X^5+\cdots+X^{100}\right)^3.\]

Solution.
Let us give the names to our students: A, B, and C.
One distribution of apples to students is when A gets 2 apples, B gets 1, and C gets 1. We can write the ordered triple (2,1,1) to correspond to this distribution. We will list all possible ways of giving apples to students, and we will do this by considering different cases.
 
Solution.
The polynomial looks complicated and we need a systematic approach.
Let us first rewrite it in a way that is esthetically more pleasing:
\[ P(X)=\left(1+X+X^2+\cdots+X^{100}\right)\]
\[ \quad \quad \quad\cdot \left(1+X+X^2+\cdots+X^{100}\right)\] \[ \quad\quad\quad \cdot \left(1+X+X^2+\cdots+X^{100}\right).\]
The terms in the first parenthesis are black, the terms in the second are blue, and the terms in the third parenthesis are red. This will make it easier to keep track of things when we start multiplying them out.
The coefficient of \( X^4 \) is obtained when all terms of this form are added: \( X^2 \) \( \cdot \)
\( X \)\( \cdot \)\( X \),
\( X \) \( \cdot \)
\( 1 \)\( \cdot \)\( X^3 \), etc.
We again need a systematic listing of all the terms.

 \( 1^{\circ} \) The student A gets 0 apples:
 \( 1^{\circ}.1 \) The student B gets 0 apples:

Now, student C has to get all 4 apples. This completes the case \( 1^{\circ}.1 \). We will denote this distribution by (0,0,4).
 \( 1^{\circ}.2 \) B gets 1 apple:

The student C must get 3 apples. The distribution is (0,1,3).
 \( 1^{\circ}.3 \) B gets 2 apples:
 C must have 2 apples, giving the distribution (0,2,2).
 \( 1^{\circ}.4 \) B gets 3 apples:
 C must get 1, and the distribution is (0,3,1).
 \( 1^{\circ}.5 \) B gets 4 apples:
 C must get 0, and the distribution is (0,4,0).
 \( 2^{\circ} \) A gets 1 apple:
 \( 2^{\circ}.1 \) B gets 0 apples:
 The student C must get 3, and the distribution is (1,0,3).
 \( 2^{\circ}.2 \) B gets 1 apple:
 C must get 2, the distribution is (1,1,2).
 \( 2^{\circ}.3 \) B gets 2 apples:
 C must get 1, the distribution is (1,2,1).
 \( 2^{\circ}.4 \) B gets 3 apples:
 C must get 0, the distribution is (1,3,0).
 \( 3^{\circ} \) A gets 2 apples:
 \( 3^{\circ}.1 \) B gets 0 apples:
 The student C must get 2, and the distribution is (2,0,2).
 \( 3^{\circ}.2 \) B gets 1 apple:
 C must get 1, the distribution is (2,1,1).
 \( 3^{\circ}.3 \) B gets 2 apples:
 C must get 0, the distribution is (2,2,0).
 \( 4^{\circ} \) A gets 3 apples:
 \( 4^{\circ}.1 \) B gets 0 apples:
 The student C must get 1, and the distribution is (3,0,1).
 \( 4^{\circ}.2 \) B gets 1 apple:
 C must get 0, the distribution is (3,1,0).
 \( 4^{\circ} \) A gets 4 apples:
 Now both B and C have to get 0 apples each, giving the distribution (4,0,0).
Now we can count and see that we considered a total of \( 15 \) cases. Hence there are \( 15 \) ways of distributing \( 4 \) apples to \( 3 \) students.
 
 \( 1^{\circ} \) The contribution from the first parenthesis is \( 1=X^0 \):
 \( 1^{\circ}.1 \) The contribution from the second parenthesis is \( 1=X^0 \).

The contribution from the third parenthesis has to be \( X^4 \), and the summand in this case is \( 1 \) \( \cdot \) \( 1 \)\( \cdot \)\( X^4 \).
 \( 1^{\circ}.2 \)
The contribution from the second parenthesis is \( X \)

The third gives \( X^3 \), and the summand is \( 1 \) \( \cdot \) \( X \)\( \cdot \)\( X^3 \).
 \( 1^{\circ}.3 \) Second parenthesis gives \( X^2 \)

The third gives \( X^2 \), and the summand is \( 1 \) \( \cdot \) \( X^2 \)\( \cdot \)\( X^2 \).
 \( 1^{\circ}.4 \) Second parenthesis gives \( X^3 \)

The third gives \( X \), and the summand is \( 1 \) \( \cdot \) \( X^3 \)\( \cdot \)\( X \).
 \( 1^{\circ}.5 \) Second parenthesis gives \( X^4 \)

The third gives \( X^0=1 \), and the summand is \( 1 \) \( \cdot \) \( X^4 \)\( \cdot \)\( 1 \).
 \( 2^{\circ} \) The first parenthesis contributes \( X \).
 \( 2^{\circ}.1 \) The second gives \( 1 \)

The third gives \( X^3 \), and the summand is \( X \) \( \cdot \) \( 1 \)\( \cdot \)\( X^3 \).
 \( 2^{\circ}.2 \) The second gives \( X \)

The third gives \( X^2 \), and the summand is \( X \) \( \cdot \) \( X \)\( \cdot \)\( X^2 \).
 \( 2^{\circ}.3 \) The second gives \( X^2 \)

The third gives \( X \), and the summand is \( X \) \( \cdot \) \( X^2 \)\( \cdot \)\( X \).
 \( 2^{\circ}.4 \) The second gives \( X^3 \)

The third gives \( 1 \), and the summand is \( X \) \( \cdot \) \( X^3 \)\( \cdot \)\( 1 \).
 \( 3^{\circ} \) The first parenthesis contributes \( X^2 \).
 \( 3^{\circ}.1 \) The second gives \( 1 \)

The third gives \( X^2 \), and the summand is \( X^2 \) \( \cdot \) \( 1 \)\( \cdot \)\( X^2 \).
 \( 3^{\circ}.2 \) The second gives \( X \)

The third gives \( X \), and the summand is \( X^2 \) \( \cdot \) \( X \)\( \cdot \)\( X \).
 \( 3^{\circ}.3 \) The second gives \( X^2 \)

The third gives \( 1 \), and the summand is \( X^2 \) \( \cdot \) \( X^2 \)\( \cdot \)\( 1 \).
 \( 4^{\circ} \) The first parenthesis contributes \( X^3 \).
 \( 4^{\circ}.1 \) The second gives \( 1 \)

The third gives \( X \), and the summand is \( X^3 \) \( \cdot \) \( 1 \)\( \cdot \)\( X \).
 \( 4^{\circ}.2 \) The second gives \( X \)

The third gives \( 1 \), and the summand is \( X^3 \) \( \cdot \) \( X \)\( \cdot \)\( 1 \).
 \( 4^{\circ} \) The first parenthesis contributes \( X^4 \).
 Now both second and third parenthesis have to contribute \( 1 \), and the term is
\( X^4 \) \( \cdot \) \( 1 \)\( \cdot \)\( 1 \).
The sum of the previous terms is \( 15X^4 \).

Definition of the generating function
Definition
Given a sequence \( (a_n)_{n=0}^{\infty} \) the generating function corresponding to the sequence \( (a_n) \) is the function defined as
\[ F(X)=\sum_{n=0}^{\infty} a_nX^n.\]
The generating function for the sequence \( 1 \), \( 0 \), \( 0 \), \( \dots \), is the function \( F(X)=1 \), while the generating function for the sequence \( 1 \), \( 1 \), \( 1 \), \( 0 \), \( 0 \), \( 0 \), \( 0 \), \( \dots \), is \( F(X)=1+X+X^2 \).
Example
Find the generating function for the sequence \( (a_n) \) defined as \( a_n=1 \) for all \( n\geq 0 \).
We write the expansion for \( F(X) \) and \( X\cdot F(X) \) and subtract one from another. \[ F(X)=1+X+X^2+X^3+X^4+X^5+X^6+X^7+\cdots\]
\[ XF(X)=X+X^2+X^3+X^4+X^5+X^6+X^7+X^8+\cdots\]
Therefore: \( F(X)XF(X)=1 \), hence \( (1X)F(X)=1 \) and \( F(X)=\frac1{1X} \).
Remark.
Infinite series that we are dealing with do not converge for all values of \( X \). We don’t worry about that stuff in this introductory article. In the theory of generating functions we may either choose to always restrict ourselves to the interval of convergence of these series, or we may consider them as formal power series in which case they are members of infinite dimensional vector spaces for which we can properly defined the desired operations.
Example
Find the generating function for the sequence \( a_n \) defined as \( a_n=n \) for \( n\geq 0 \).
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:
\[ (1X)F(X)=X+X^2+X^3+X^4+\cdots = X\cdot \left(1+X+X^2+\cdots\right)=\frac{X}{1X},\]
where the last equality follows from the previous example. Hence \( F(X)=\frac{X}{(1X)^2} \).
It is useful to know that \begin{eqnarray*}\left(\frac1{1X}\right)^{\prime}&=&\frac1{(1X)^2}, \quad\quad\quad \mbox{ and} \\
\left(\frac1{1X}\right)^{(k)}&=&\frac{ k!}{(1X)^{k+1}}.\end{eqnarray*}
We often refer to the following general binomial theorem (which is easily proved using Taylor’s expansion from calculus). In order to state it, we first define a general binomial coefficient.
Definition
If \( a\in\mathbb R \) and \( k\in\mathbb N \) then \[ \binom{a}{k}=\frac{a(a1)\cdots(ak+1)}{k!}.\]
Here is the binomial formula:
Theorem
If \( a\in\mathbb R \) then:
\[ \left(1+X\right)^a=\sum_{k=0}^{\infty}\binom{a}kX^k.\]
Quiz
It is a good idea now to take a moment and do the following
quiz to review the definitions we just covered in the previous section.
Using generating functions in combinatorial problems
We’ll start and end with an example that explains how to use generating functions to solve a with students and apples similar to the one above.
Example
Find the number of ways of distributing \( 15 \) apples to \( 5 \) students.
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
\[ F(X)=a_0+a_1X+a_2X^2+\cdots\]
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 nonnegative integers that add up to \( n \). This 5tuple represents that the first student got \( \gamma_1 \) apples, the second \( \gamma_2 \), etc.
To each 5tuple \( (\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{1X}=\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 \).
Example
Let \( n \) be a positive integer. Assume that:
\( N_k \) is the number of pairs \( (a,b) \) of nonnegative integers such that \( ka+(k+1)b=n+1k \).
Find \( N_1+N_2+\cdots+ N_{n+1} \).
We know that \( N_k \) is the coefficient of \( X^{nk+1} \) in:
\[ G_k(X)=(1+X^k+X^{2k}+\cdots)\cdot (1+X^{k+1}+X^{k+2}+\cdots)=\frac1{1X^k}\cdot\frac1{1X^{k+1}}.\]
Notice that \( N_k \) can be seen as the coefficient of \( X^{n+1} \) in:
\[ X^kG_k(X)=\frac{X^k}{(1X^k)\cdot (1X^{k+1})}.\]
Hence \( N_1+N_2+\cdots+ N_{n+1} \) is the coefficient of \( X^{n+1} \) in the expansion
\[ F_R(X)=\frac{X}{(1X)(1X^2)}+\frac{X^2}{(1X^2)(1X^3)}+\frac{X^3}{(1X^3)(1X^4)}+\cdots+
\frac{X^R}{(1X^R)(1X^{R+1})},\]
where \( R \) is any integer that is larger than \( n+1 \).
Let us denote
\[
A_R(X)=\frac1{1X}+\frac1{1X^2}+\frac1{1X^3}+\cdots+\frac1{1X^R},\]
\[ B_R(X)=\frac1{(1X)(1X^2)}+\frac1{(1X^2)(1X^3)}+\frac1{(1X^3)(1X^4)}+\cdots +\frac1{1X^{R}}.\]
Now we can write
\[ F_R(X)=A_R(X)B_{R+1}(X)+\frac1{1X}\]
\[ XF_R(X)=A_R(X)B_R(X).\]
Subtracting the second inequality from the first yields:
\( (1X)F_R(X)=\frac1{1X}\frac1{1X^{R+1}} \) hence
\[ F_R(X)=\frac1{(1X)^2}\frac1{(1X)(1X^{R+1})}=
\sum_{k=0}^{R}(1)^k\binom{2}{k}X^k(1+X+\cdots)(1+X^{R+1}+\cdots).\]
Hence the coefficient of \( X^{n+1} \) in \( F_R(X) \) is \( (1)^{n+1}\binom{2}{n+1}1=n+1 \).
The following example illustrates how to use multivariable calculus in solving combinatorial problems with generating functions.
Example
By a partition of an integer \( n\geq1 \), we mean a representation of \( n \) as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if \( n=4 \), then the partitions are: \( (1,1,1,1) \), \( (1,1,2) \), \( (1,3) \), \( (2,2) \), and \( 4 \).)
For any partition \( \pi \), define \( A(\pi) \) to be the number of \( 1 \)’s which appear in \( \pi \), and define \( B(\pi) \) to be the number of distinct integers which appear in \( \pi \). (E.g., if \( n=13 \) and \( \pi \) is the partition \( (1,1,2,2,2,5) \) then \( A(\pi)=2 \) and \( B(\pi)=3 \).)
Prove that for any fixed \( n \), the sum of \( A(\pi) \) over all partitions \( \pi \) of \( n \) is equal to the sum of \( B(\pi) \) over all partitions \( \pi \) of \( n \).
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\\
&=& 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\\
&&+ \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\\
&&+ \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\\&=& \left(x+x^2+x^3+\cdots\right)\cdot P(x)P(x^2)P(x^3)\cdots \\
&=& 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{1x} \).
Exponential generating function
Definition
The exponential generating function corresponding to the sequence \( (a_n)_{n=0}^{\infty} \) is the function defined as \[ H(X)=\sum_{n=0}^{\infty} \frac{a_n}{n!}X^n.\]
Example
Suppose that there are \( p \) different kinds of objects, each in infinite supply. Let \( a_k \) be the number of different ways to arrange \( k \) of these objects in a line. Find \( a_k \) explicitly by using exponential generating functions.
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 nonnegative 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
\[ \frac{a_k}{k!}=\sum_{d_1+ \cdots+ d_p=k} \frac1{d_1!\cdot d_2!\cdots d_p!}.\]
The last
summation is over all sequences \( (d_1, \dots, d_p) \) of nonnegative 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 \).
Example
Let \( n \) and \( k \) be positive integers with \( k\geq n \) and \( kn \) an even number.
Let \( 2n \) lamps labelled \( 1 \), \( 2 \), \( \dots \), \( 2n \) be given, each of which can be either
on or
off. Initially all the lamps are off. We consider the sequence of steps: at each step one of the lamps is switched (from on to off or from off to on). Let \( N \) be the number of such sequences consisting of exactly \( k \) steps and resulting in the state where lamps \( 1 \) through \( n \) are all on, and lamps \( n+1 \) through \( 2n \) are all off. Let \( M \) be the number of such sequences consisting of \( k \) steps and resulting in the state where lamps \( 1 \) through \( n \) are all on, and lamps \( n+1 \) through \( 2n \) are all off, but where none of the lamps \( n+1 \) through \( 2n \) is ever switched on. Determine the ratio \( \frac NM \).
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
\[ f(X) = \left(\frac{X}{1!}+\frac{X^3}{3!}+\cdots \right)^n\cdot\left(
1+\frac{X^2}{2!}+\frac{X^4}{4!}+\cdots\right)^n\]
\[ g(X)=\left(\frac{X}{1!}+\frac{X^3}{3!}+\cdots \right)^n.
\]
Notice that \[ \frac X{1!}+\frac{X^3}{3!}+\cdots=\frac{e^Xe^{X}}2\]
\[ 1+\frac{X^2}{2!}+\frac{X^4}{4!}+\cdots=\frac{e^X+e^{X}}2\] \[
\left(\frac{X}{1!}+\frac{X^3}{3!}+\cdots \right)\cdot\left(
1+\frac{X^2}{2!}+\frac{X^4}{4!}+\cdots\right)=
\frac{e^{2X}e^{2X}}{4}.
\]
Let \( \phi(X)=\frac12(e^Xe^{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^{kn} \).
Homeworks/Quizzes
Quiz 1 (Introduction to generating functions: Definitions)
Quiz 2 (Using generating functions in combinatorics)