Mathematical Database
GENERATING FUNCTIONS
1. Introduction
The concept of generating functions is a powerful tool for solving counting problems.
Intuitively put, its general idea is as follows. In counting problems, we are often interested in
counting the number of objects of ‘size n’, which we denote by an . By varying n, we get different
values of an . In this way we get a sequence of real numbers
a0 , a1 , a2 , …
from which we can define a power series (which in some sense can be regarded as an ‘infinite-
degree polynomial’)
G ( x) = a0 + a1 x + a2 x 2 + .
The above G ( x) is the generating function for the sequence a0 , a1 , a2 , ….
In this set of notes we will look at some elementary applications of generating functions.
Before formally introducing the tool, let us look at the following example.
Example 1.1.
(IMO 2001 HK Preliminary Selection Contest) Find the coefficient of x17 in the expansion of
(1 + x 5 + x 7 ) 20 .
Solution.
The only way to form an x17 term is to gather two x5 and one x 7 . Since there are C220 = 190 ways
to choose two x 5 from the 20 multiplicands and 18 ways to choose one x 7 from the remaining 18
multiplicands, the answer is 190 × 18 = 3420 .
To gain a preliminary insight into how generating functions is related to counting, let us
describe the above problem in another way. Suppose there are 20 bags, each containing a $5 coin
and a $7 coin. If we can use at most one coin from each bag, in how many different ways can we
pay $17, assuming that all coins are distinguishable (i.e. the $5 coin from the first bag is considered
to be different from that in the second bag, and so on)? It should be quite clear that the answer is
again 3420 — to pay $17, one must use two $5 coins and one $7 coin. There are C220 = 190 ways to
choose two $5 coins from the 20 bags, and 18 ways to choose a $7 coin from the remaining 18 bags.
Using the notations we introduced at the very beginning, we could say that a17 = 3420 .
Page 1 of 17
, Mathematical Database
2. Techniques of Computation
Let us once again give the definition of a generating function before we proceed.
Definition. Given a sequence a0 , a1 , a2 , …, we define the generating function of the
sequence {an } to be the power series
G ( x) = a0 + a1 x + a2 x 2 + .
Let us look at a few examples.
Example 2.1.
Find the generating functions for the following sequences. In each case, try to simplify the answer.
(a) 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, …
(b) 1, 1, 1, 1, 1, …
(c) 1, 3, 3, 1, 0, 0, 0, 0, …
(d) C02005 , C12005 , C22005 , …, C2005
2005
, 0, 0, 0, 0, …
Solution.
(a) The generating function is
G ( x) = 1 + 1x + 1x 2 + 1x 3 + 1x 4 + 1x 5 + 0 x 6 + 0 x 7 +
= 1 + x + x 2 + x3 + x 4 + x5
1 − x6
We can apply the formula for the sum of a geometric series to rewrite G ( x) as G ( x) = .
1− x
(b) The generating function is
G ( x) = 1 + x + x 2 + x3 + x 4 + .
When | x | < 1 , we can apply the formula for the sum to infinity of a geometric series to rewrite
1
G ( x) as G ( x) = . In working with generating functions, we shall ignore the question of
1− x
1
convergence and simply say G ( x) = .
1− x
(c) The generating function is G ( x) = 1 + 3x + 3x 2 + 1 , and of course, the binomial theorem enables
us to simplify the answer as G ( x) = (1 + x)3 .
Page 2 of 17
, Mathematical Database
(d) The generating function is
G ( x) = C02005 + C12005 x + C22005 x 2 + + C2004 x + C2005
2005 2004 2005 2005
x ,
and the binomial theorem once again enables us to simplify the answer as G ( x) = (1 + x) 2005 .
When dealing with computations of generating functions, we are particularly interested with
two things, namely, whether the generating function can be written in closed form and whether we
can find the coefficient of a certain power of x easily.
To write a generating function in ‘closed form’ means, in general, writing it in a ‘direct’ form
without summation sign nor ‘ ’. For instance, in Example 2.1 (b), G ( x) = 1 + x + x 2 + x3 + x 4 +
1
is not in closed form while G ( x) = is. The reason for trying to put a generating function in
1− x
closed form is as follows. In the more advanced theory of generating functions (beyond the level of
this set of notes), we will find that certain combinations of problems correspond to certain
operations (e.g. addition, multiplication or more complicated operations) on generating functions. If
we can find a generating function in closed form, the computations can be greatly simplified and
easily carried out.
On the other hand, we are interested in knowing the coefficient of a certain power of x because,
as we have remarked at the very beginning, it often refers to the number of objects of size n, which
is usually the thing we wish to find in counting problems.
Clearly, if a generating function is given in ‘explicit form’, such as
∞
n −1 n
G ( x) = x + 2 x 2 + 3 x3 + 4 x 4 + or G ( x) = ∑ x ,
n = 0 2n + 1
then finding a specific coefficient will be easy. However, if a generating function is given in closed
form, ingenious tricks are sometimes required in determining certain coefficients. The following
example illustrates some common tricks.
Example 2.2.
In each of the following, find the coefficient of x 2005 in the generating function G ( x) .
(a) G ( x) = (1 − 2 x)5000
1
(b) G ( x) =
1 + 3x
1
(c) G ( x) =
(1 + 5 x) 2
Solution.
Page 3 of 17