Generating Functions

Xiangtao (Eddy) Liu

1 Introduction
Combinatorial problems will often ask to determine a certain sequence of numbers a0 , a1 , a2 , . . .. A common
technique to solve this type of problems is to encode this sequence as a (possibly infinite) polynomial,
∞
X
f (x) = ak xk
k=0

These polynomial are called generating functions. The goal of this session is to develop the basic tools of
generating functions and provide some standard techniques for application.

2 Sicherman Dice
Find all possible combinations of dice, A and B, that bear only positive integers and have the same probability
distribution as the sum as normal dice.
Solution. (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6) and (1, 2, 2, 3, 3, 4), (1, 3, 4, 5, 6, 8)
Consider a regular fair die with numbers (1, 2, 3, 4, 5, 6). This can be encoded through generating functions
1 1 1 1 1 1
x + x2 + x3 + x4 + x5 + x6
6 6 6 6 6 6
The sum of two dice rolls can be expressed as
1
2
x + x2 + x3 + x4 + x5 + x6
36
Therefore, the goal is the determine all polynomials f (x) and g(x) such that

2
(i) f (x)g(x) = x + x2 + x3 + x4 + x5 + x6
(ii) The coefficients of f (x) and g(x) are non-negative
(iii) The sum of the coefficients of each of f (x) and g(x) is 6, f (1) = g(1) = 6
(iv) f (x) and g(x) does not have a constant term
First, factor the original polynomial into irreducible functions

2
2
2
x + x2 + x3 + x4 + x5 + x6 = x2 1 + x + x2 (1 + x)2 1 − x + x2
To satisfy (iv), x2 must be split into both f and g. Next, evaluating the three polynomials
1 + x + x2 , 1 + x, 1 − x + x2

2
at x = 1 yields 3, 2, 1, respectively. Thus, to satisfy (iii), both the polynomials 1 + x + x2 and (1 + x)2

2
must be split into both f and g. Finally, there are two ways to handing 1 − x + x2 . The first ways is
to split them into both f and g, but this will result in die A and B having the same set of numbers. The
second way is to give both terms to f (x). Combining these factors,

2
f (x) = x 1 + x + x2 (1 + x) 1 − x + x2 = x + x3 + x4 + x5 + x6 + x8

g(x) = x 1 + x + x2 (1 + x) = x + 2x2 + 2x3 + x4

Note that they both satisfy (ii). Therefore, there is only one possible combination of dice, A and B, such
that the set of numbers on die A is different from the set of numbers on die B.

1
3 Partial Fraction Review
Let f (x) be a rational function then there exist real polynomials p(x) and q(x) with q(x) 6= 0 such that
p(x)
f (x) =
q(x)
It suffice to assume that q(x) is monic as it is easy to just factor out the leading coefficients. By Fundamental
Theorem of Algebra, it is possible to factor the denominator as
j j
k 1
kn
q(x) = (x − a1 ) 1 · · · (x − am ) m x2 + b1 x + c1 · · · x 2 + bn x + c n
where a1 , . . . am , b1 , . . . , bn , c1 , . . . , cn are real numbers with b2i −4ci < 0, and j1 , . . . , jm , k1 , . . . , kn are positive
integers. Then the partial fraction decomposition of f (x) is
j1
m X n
i k
X Air XX Bir x + Cir
f (x) = P (x) + r + 2 + b x + c )r
i=1 r=1
(x − ai ) i=1 r=1
(x i i

where P (x) is a polynomial and Air , Bir , Cir are real constants. There are numerous way to find the
constants. The most common technique is to use coefficient matching.
Remark. Although q(x) can always be written in that form, it is not always easy to do so.
Example 1. Apply partial fraction decomposition to
1
(x + 1)(x + 2)2
Solution. The given expression will decompose into something of the form
A B C
+ +
x + 1 x + 2 (x + 2)2
Recombining this expression and equating to 1 yields A = 1, B = −1, C = −1.

4 Some Useful Series

The following are a list of common finite and infinite series. Many more series can be derived from these
through operations on functions. (Add, subtract, multiply, divide, composition, derivative, etc.)
Finite Series:
1−xN +1
PN k
1. k=0 x = 1−x
PN N
k N
2. k=0 k x = (1 + x)
Infinite Series:
These series are called formal power series. It differs from an actual power series in that the variables cannot
always be replaced by a number. Therefore, convergence is not an issue.
P∞ k 1
1. k=0 x = 1−x (Infinite geometric series)
P∞ k−1 1
2. k=1 kx = (1−x) 2

P∞ n+k
k 1
3. k=0 k x = (1+x)n+1 (Negative binomial)
P∞ 1 k x
4. k=0 k! x = e
P∞ 2k
k
√ 1
5. k=0 k x = 1−4x
P∞ √
1 2k 1− 1−4x


6. k=0 k+1 k xk = 2x
P∞ (−1)k 2k+1
7. k=0 (2k+1)! x = sin(x)
P∞ (−1)k 2k
8. k=0 (2k)! x = cos(x)

2
5 Solving Recurrence Relations
The easiest application of generating functions is solving recurrence relations.
Fibonacci sequence. Let F0 = 0 and F1 = 1 and for n ≥ 1, Fn+1 = Fn + Fn−1 . Find the general term of the
sequence.
Solution. Define f (x) to be the generating function of Fn and consider the following manipulations
∞
X
f (x) = Fk xk
k=0
∞
X
= F0 + F1 x + Fk xk
k=2
∞
X
=0+x+ (Fk−1 + Fk−2 ) xk
k=2
∞
X ∞
X
=x+x Fk−1 xk−1 + x2 Fk−2 xk−2
k=2 k=2
X∞ ∞
X
=x+x Fk xk + x2 Fk x k
k=1 k=0
X∞ X∞
=x+x Fk xk + x2 Fk x k
k=0 k=0
= x + xf (x) + x2 f (x)
x
(∗) =
1 − x − x2
x
= √  √ 
1 − 2 x 1 − 1−2 5 x
1+ 5

!
1 1 1
=√ √ − √
1+ 5
5 1− 2 x 1 − 1−2 5 x
∞  √  k ∞  √ k !
1 X 1+ 5 k
X 1− 5
=√ x − xk
5 2 2
k=0 k=0
∞  √ k  √ k ! !
1 X 1+ 5 1− 5
=√ − xk
5 2 2
k=0
k
The coefficient of x is √ k  √ k !

1 1+ 5 1− 5
Fk = √ −
5 2 2
which is exactly the well known closed form formula for the Fibonacci Sequence.
Note. Observe that the denominator at (∗) is similar to the characteristic polynomial of the recurrence
relation!

6 The Snake Oil Method

The snake oil method is a simple yet powerful way to force a combinatorial summation into a generating
function double summation. Here is an overview for the steps of the snake oil method
1. Identify the free variable, say n, that the sum depends on and call the sum f (n).
2. Let F (x) be the ordinary generating function for the sequence f (0), f (1), . . . Note that F (x) is now a
double sum.

3
3. Move everything inside the inner summation and exchange the order of the summation.
4. Manipulation the exponent of x in order to applied a well known series.
5. Identify the coefficient of the resulting generating function.
Example. Let m, n ≥ 0. Evaluate
∞ 
2k (−1)k
 
X n+k
m + 2k k k+1
k=0

Solution. Let m be the free variable and define the generating function
∞ ∞ 
2k (−1)k
 
X
m
X n+k
F (x) = x
m=−∞
m + 2k k k+1
k=0
∞
X 2k (−1)k X
  ∞  
n+k
= xm
k k + 1 m=−∞ m + 2k
k=0
∞  ∞
2k (−1)k −2k X
  
X n+k
= x xm+2k
k k+1 m=−∞
m + 2k
k=0
∞   k n+k  
X 2k (−1) −2k X n + k r
= x x
k k+1 r=0
r
k=0
∞ 
2k (−1)k −2k
X 
= x (1 + x)n+k
k k+1
k=0
∞    k
X 2k 1 −(1 + x)
= (1 + x)n
k k+1 x2
k=0
s  !
n 1 1+x
= (1 + x)
1− 1−4 − 2
2 − 1+x
x2
x
= x(1 + x)n+1
n−1 n−1



This is the generating function for m−1 . Therefore, the original summation is m−1 .
Remark. The same technique works if n is chosen as the free variable except the algebra will be slightly
more messy.

7 Generating Functions in Olympiad Questions

[China 1996] Let n be a positive integer. Find the number of polynomials P (x) with coefficients in {0, 1, 2, 3}
such that P (2) = n.
Solution. Let an be the answer to the problem. Define
∞
X
f (t) = an tn
n=0

Pk i
to be the generating function for an . Let P (x) = i=0 ci x where ci ∈ {0, 1, 2, 3}. Observe that P (2) = n if

4
Pk Qk i
i
and only if i=0 ci 2 = n. Since tn = i=0 t2 ci
and 2i ci ∈ {0, 2i , 2 · 2i , 3 · 2i } then f (t) can be factored as
∞  
Y i i i
f (t) = 1 + t2 + t2·2 + t3·2
i=0
∞ i
!
Y 1 − t4·2
=
i=0
1 − t 2i
1 1
= ·
1 − t 1 − t2
 
1 1 1
= +
2 (1 − t)2 1 − t2
∞ ∞
!
1 X k−1 X 2k
= kx + x
2
k=0 k=0
∞ j k
X n 
= + 1 xn
n=0
2

Therefore, the number of such polynomials is n2 + 1.

 

[IMO 1995 P6 by Nikolay Nikolov] Let p be an odd prime number. How many p-element subsets A of
{1, 2, . . . , 2p} are there, the sum of whose elements is divisible by p?
Solution. Let ω be a primitive p-th root of unit then
2p
Y 2
x − ω k = (xp − 1) = x2p − 2xp + 1

k=1

Comparing the coefficient of xp ,

X p−1
X
2= ω k1 +k2 +···+kp = nj ω j
j=0

where the first summation is over all subsets {k1 , k2 , . . . , kp } of {1, 2, . . . , 2p} and nj in the second summation
is the number of such subsets such that

k1 + k2 + · · · + kp ≡ j (mod p)

Thus, ω is a root of
p−1
X
G(x) = (n0 − 2) + nj xj
j=1

which is a polynomial of degree p − 1. Recall that the minimal polynomial of ω in Q[x] is

p−1
X
F (x) = xj
j=0

which is also of degree p − 1. Since minimal polynomials are unique up to a scalar multiple then G(x) is a
scalar multiple of F (x). This implies that

n0 − 2 = n1 = n2 = · · · = np−1
Pp 2p


Since j=0 nj = p then
  
1 2p
n0 = −2 +2
p p

5
8 String Generating Functions
A binary string of length n is a n−tuple (a1 , . . . , an ) where ai ∈ {0, 1}. An empty string is denoted with .
Let A and B be two sets of strings then
AB = {ab : a ∈ A, b ∈ B}
The set of binary strings of length 7 can be written as {0, 1}7 . The set of all binary strings can be written as
∞
[ ∞
[
{0, 1}∗ = {} ∪ {0, 1}k = {0, 1}k
k=1 k=0

An expression is unambiguous if there exists a unique way of writing every string according to the expres-
sion. For example: {0, 00}{, 0} is ambiguous.
Remark. {1}∗ {{0}{0}∗ {1}{1}∗ }∗ {0}∗ is unambiguous and is equivalent to {0, 1}∗ . The longer version is
actually much more useful.

Theorem. If S = A ∪ B unambiguously then ΦS (x) = ΦA (x) + ΦB (x).

If S = AB unambiguously then ΦS (x) = ΦA (x)ΦB (x).
If S = A∗ unambiguously then ΦS (x) = 1−Φ1A (x) .

Example. Prove that {1}∗ {{0}{0}∗ {1}{1}∗ }∗ {0}∗ = {0, 1}∗ .

Solution. The generating function for {0, 1}∗ is
∞
1 X
Φ{0,1}∗ (x) = = 2n xn
1 − 2x n=0

Therefore, there are 2n number of binary strings of length n.

The generating function for A = {1}∗ {{0}{0}∗ {1}{1}∗ }∗ {0}∗ is
∞
1 1 1 1 X
ΦA (x) = x x = = 2n xn
1 − x 1 − 1−x 1−x 1 − x 1 − 2x n=0

Therefore, there are 2n number of such binary strings of the form A. Since this is the maximum number of
such binary strings, A = {0, 1}∗ .

Example. Determine the number of binary strings such that all blocks has length at least 2.
Solution. The unambiguous expression is
S = ( ∪ {00}0∗ )({11}1∗ {00}0∗ )∗ ( ∪ {11}1∗ )
The generating function is
!
x2 x2 1 − x + x2
  
1
ΦS (x) = 1+ x2 x2
1+ =
1−x 1− 1−x 1−x
1−x 1 − x − x2

The number of such binary strings is given by the coefficient of xn , 1 when n = 0 and when n ≥ 1,
(
1 if n = 0
1
√
 1+√5 n 1
√
 1−√5 n
1− 5 5 2 + 1+ 5 5 2 if n ≥ 1

Remark. The set of binary strings can also be defined recursively as {0, 1}∗ = {} ∪ {0, 1}∗ {0, 1}.
Example. Determine the generating function that models the number of of strings without 111.
Solution. Let S be the set of such strings. The unambiguous expression is S = {, 1, 11} ∪ S{0, 01, 011}. The
corresponding generating function is
1 + x + x2
ΦS (x) = (1 + x + x2 ) + ΦS (x)(x + x2 + x3 ) =
1 − x − x2 − x3

6
9 Problem Set
1. Let a0 = 1, a1 = 1, and an = 4an−1 − 4an−2 for n ≥ 3. Use generating functions to find the closed
form formula for an .
P∞ k


2. Evaluate k=0 n−k .
3. Let a1 = 1, a2 = 4, and an = 2an−1 − an−2 + 2 for n ≥ 3. Use generating functions to find the closed
form formula for an .

4. A binary string α is called self-avoiding provided that whenever αβ = γα then |α| ≤ |β|. (The
absolute values represent the length). For example, 01001 is not self avoiding because (01001)(001) =
(010)(01001). Determine the generating functio that models the number of self-avoiding strings of
length n.
P∞
5. Evaluate k=0 b nk c xk .


2

6. Find the number of ways n dollars can be changed into 1 or 2 dollar coins (regardless of order).
P∞
7. Let Fn be the nth term in the Fibonacci sequence. Determine the value of n=0 F4nn .

8. Determine the generating function that models the number of of strings without 11101.
P∞
9. Evaluate k=0 nk b n−k


k
m−k
2 c (−2) .
10. Let x0 = 1 and x1 = 3 and for n ≥ 2, let xn = 6xn−1 − 10xn−2 . Find the closed formula, which only
involves real numbers.
11. Find the number of binary strings of length n in which each block of 0s has odd length and each block
of 1s has length one or two.
Pn
12. Prove that k=0 2n

2k
2n−2k
= 4n


2k k 2 2n .
P∞ 2n+1

p+k

13. For given n and p evaluate k=0 2p+2k+1 k .

14. Find the number of binary strings of length n with exactly m blocks of 01.
15. Prove that the sequence defined by a1 = 1, a2n+2 = an + an+1 , and a2n+1 = an counts the number of
representations of n as a sum of powers of two using each power at most twice.
Pk
16. [Putnam 1992] Show that the coefficient of xk in the expansion of (1 + x + x2 + x3 )n is j=0 nj k−2j

n

.

17. [HMMT 2007] Let S be the set of triplets (i, j, k) of positive integers which satisfy i + j + k = 17.
Compute X
ijk
(i,j,k)∈S

18. [AIME 2001] A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The
carrier notices that no two adjacent houses ever get mail on the same day, but that there are never
more than two houses in a row that get no mail on the same day. How many different patterns of mail
delivery are possible?
19. [Putnam 1991] Let p be an odd prime . Prove that
p   
X p p+n
≡ 2p + 1 modp2


n=0
n n

7
20. Let A1 , A2 , . . . and B1 , B2 , . . . be sets such that A1 = ∅ and B1 = {0}, and
An+1 = {x + 1 : x ∈ Bn }
Bn+1 = (An ∪ Bn ) \ (An ∩ Bn )
for all positive integers n. Determine all positive integers n such that Bn = {0}.
21. Determine if the set of positive integers can be partitioned into more than one but finite number of
arithmetic progressions with no two having the same common difference?
22. [Leningrad Mathematical Olympiad 1991] A finite sequence a1 , a2 , . . . , an is called p-balanced if any
sum of the form ak + ak+p + · · · is the same for any k = 1, 2, . . . , p. For instance the sequence a1 = 1,
a2 = 2, a3 = 3, a4 = 4, a5 = 3, a6 = 2 is 3-balanced. Prove that if a sequence with 50 members is
p-balanced for p = 3, 5, 7, 11, 13, 17 then all its members are equal to zero.
23. [China 1999] For a set A, let s(A) denote the sum of the elements of A. If A = ∅ then s(A) = 0. Let
S = {1, 2, . . . , 1999}. For r = 0, 1, 2, . . . , 6, define
Tr = {T |T ⊆ S, s(T ) ≡ r (mod 7)}
For each r, find the number of elements in Tr .
24. [Vietnam TST 1994] Evaluate
X 1
n1 !n2 ! · · · n1994 ! (n2 + 2n3 + 3n4 + · · · + 1993n1994 )!
where the sum is taken over all 1994−tuples of nonnegative integers (n1 , n2 , . . . , n1994 ) such that
P1994
k=1 kak = 1994.

25. [IMO 1998 SL] Let a0 , a1 , . . . be an increasing sequence of nonnegative integers such that every non-
negative integer can be expressed uniquely in the form ai + 2aj + 4ak where i, j, k are not necessarily
distinct. Determine a1998 .
26. [IMO 2008] Let n and k be positive integers with k ≥ n and k − n an even number. Let 2n lamps
labeled 1, 2, . . . , 2n be given, each of which can be either on or off. Initially all lamps are off. We
consider a 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 k steps and resulting in the state where lamps 1
through nare all on, and lamps n + 1 through 2n are all off.
Let M be the number of such sequences consisting of k steps, 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.
N
Determine the ratio M .
27. An a × b rectangle can be tiled by a number p × 1 and 1 × q tiles of rectangles, where a, b, p, q are fixed
positive integers. Prove that a is divisible by p or b is divisible by q. Note that k × 1 and 1 × k are
considered to be different tiles.

10 Reference/Further Reading
1. H.S. Wilf, 1994, Generatingfunctionology, University of Pennsylvania, Philadelphia, USA.
2. T. Andreescu and Z. Feng, A Path to Combinatorics for Undergraduates, Birkhauser, Boston,
2004.
3. M. Novakovic, Generating Functions, The IMO Compendium Group, 2007.
4. T. Andreescu and Z. Feng, 102 Combinatorial Problems From The Training Of The USA
IMO Team, Birkhauser, Boston, 2003.