Enumerative Combinatorics - Creative Counting

Combinatorics problems often ask you to find the number of elements in a possi-
bly large, but finite set. For example, how many functions f : {1, 2, 3} → {1, 2, 3, 4}
are strictly increasing?
In all of these our main strategy is to divide and conquer. That can be done by
writing the set as a union or a Cartesian product of other sets and in that case you
can use the principle of inclusion-exclusion to get a sum of products. In these notes
we will look at another powerful way of breaking up a problem: by recursion.

Recurrence Relations
Let (ai ) for i ∈ N be a sequence indexed by the natural numbers. A recurrence
relation for this sequence is given by a function f such that
an = f (an−1 , an−2 , . . . , an−p , n)
for some constant p (independent of n). It is easy to see that for any set of the
initial values a1 , a2 , . . . , ap this relation determines any other value an . This is also
true for any other collection of values ai1 , . . . , aip , but it is much harder to find the
other values in that case, and some of the methods described in these notes may
help.
Here is a set of counting problems that can be modeled using a recurrence rela-
tion.
(1) Let S be a set containing n elements. A partition of S into k subsets is
a collection A1 , A2 , . . . , Ak of non-empty disjoint subsets of S such that
Sk
S
 =  i=1 Ai . The number of ways in which you can do this is called
n
, the Stirling numbers of the second kind. Find a recurrence relation
k 
n
for . (Note that this is a function in two variables - there will be
k
more about this type of recurrence relations in the section on generating
functions.)
(2) Let Bn be the total number of partitions of a set of n elements. (These
numbers are called the Bell numbers, after Eric Temple Bell (1883-1960).)
Find a recurrence relation for Bn .
(3) A mail carrier has one piece of mail for each house in a street with n houses
and wants to deliver the mail in such a way that each mailbox receives one
piece of mail, but no mail gets delivered to the correct address. Let Dn
be the number of ways in which he can do this. (The Dn are called the
derangement numbers.) Find a recurrence relation for the Dn .
(4) The Tower of Hanoi. There are three diamond needles and n gold disks of
different sizes are placed on the first needle in order so that the largest disk
is on the bottom and each disk is only above disks of a larger size. Tn is the
number of moves required to move the disks to the third needle (with the
use of the second one) such that in no stage of the process a disk is placed
on a needle with a disk of smaller size below it. Find a recurrence relation
for Tn .
(5) A sequence in which every term is one of m symbols is called an m-ary
sequence. Find a recurrence relation for the number an of binary sequences
of length n that have no consecutive zeros.
1
2

(6) Find a recurrence relation for the number bn of ternary sequences of length
n containing a 2 such that there are no zeros after it in the sequence.
(7) Find a recurrence relation for the number cn of ternary sequences of length
n with no consecutive zeros.
(8) Cars are parked in line as they come off 3 different assembly lines, ready for
later road testing. Today’s production produces 3 models, each of a single
colour. Each red car takes 2 spaces, each blue car takes 2 spaces, and each
green car takes only 1 space. Find a recurrence relation for the number qn
of ways of filling the first n parking spaces.
(9) Find a recurrence relation for the number en of comparisons that must be
made between pairs of numbers in order to determine the maximum and
the minimum of a set of 2n distinct real numbers.
(10) Let ar,n be the number of ways to distribute r balls into n distinguishable
boxes with 2, 3, or 4 balls in each box if there are at least 4n red balls, 4n
white balls, and 4n blue balls available.
Homogeneous Linear Recurrence Relations. A recurrence relation is homo-
geneous and linear if it is of the form
(1) an = c1 an−1 + c2 an−2 + · · · + cp−1 an−p+1 + cp an−p
for n ≥ p, and constants ci . Suppose that cp 6= 0. To solve a relation of this kind,
we first look for solutions of the form ak = λk . Substituting this into our equation
(1) we get a polynomial equation
λp = c1 λp−1 + c2 λp−2 + · · · + cp−1 λ + cp ,
which we call the characteristic equation of (1).
It is easy to see that any linear combination of solutions to (1) is again a solution.
So if λ1 , λ2 , . . . , λp are roots of the characteristic equation, any linear combination
ak = r1 λk1 + r2 λk2 + · · · + rp λkp is a solution of the equation (1). If all the roots
λ1 , . . . , λr are distinct, all solutions of (1) are of this form. (However, even though
we are working with sequences of integer numbers, don’t be surprised if you obtain
roots that are not integers, and may even be complex numbers.)
If there are repeated roots, say root λi has multiplicity mi (this means that mi
is the highest power of (λ − λi ) that divides the characteristic equation), then kλki ,
k 2 λki , . . . , k mi −1 λki are also solutions of (1).
Example 1. Consider an = 3an−1 − 4an−3 for n ≥ 3 with a0 = 0, a1 = 2, and
a2 = −1. Find a closed formula for an .
Nonhomogeneous Linear Recurrence Relations. Sometimes you may need
to consider recurrence relations of the form
an = c1 an−1 + c2 an−2 + · · · + cp−1 an−p+1 + cp an−p + g(n).
Note that if we have two different solutions of this equation, their difference will be
a solution of the corresponding homogeneous system:
an = c1 an−1 + c2 an−2 + · · · + cp−1 an−p+1 + cp an−p .
So if we have the general solution of the homogeneous system, and a special solution
of the nonhomogeneous system, their sum will give us the general solution for the
nonhomogeneous system. So the question is how to find a special solution for the
nonhomogeneous equation.
 3

If g(n) is a polynomial of degree m, you can find a special solution of degree m,

i.e. an = dm nm + · · · d1 n + d0 . However, if the equation is an = an−1 + g(n), you
need to take a polynomial of degree m + 1 for your special solution.
If g(n) = x·y n , a special solution of the form an = k ·y n usually works. It doesn’t
work if y is a root of the characteristic equation of the corresponding homogeneous
system. If y is a root of multiplicity r, a special solution of the form knr y n exists.
If g(n) is a sum of a polynomial and an exponential function in n, you can use
both techniques separately, and add the two special functions. For more compli-
cated g(n) and non-linear recurrence relations, we may not always be able to find
a closed formula, but the technique of generating functions can be very helpful.
Exercises 2. (1) Give a closed formula for each of the following recurrence
relations with their initial conditions.
(a) an = an−1 + 6an−2 + 3n when a0 = a1 = 0.
(b) an = an−1 + 6an−2 + 2n when a0 = a1 = 0.
(c) an = 4an−1 − 4an−2 + 2n when a0 = a1 = 1.
(2) Show that the total number of triangles in an equilateral triangle of side n
tiled by equilateral triangles of side 1 is given by the formula
4n3 + 10n2 + 4n − 1 + (−1)n
.
16

Generating Functions
A different way to reason about a sequence (an ) for n ≥ 0, is by considering its
generating function
∞
X
G(an ) (x) = an xn .
n=0
This type of function is a formal power series. You may be worried that G(x) may
not be defined for all values of x, but for our purposes that generally won’t matter.
We view formal power series only as algebraic gadgets, they are just clotheslines to
hang our sequences on. We will perform various algebraic operations on the formal
power series and will generally just be interested in their effect on the coefficients
(the clothes on the clothesline). So we introduce the notation [xn ]F (x) for the
coefficient of xn in the formal power series F (x). In particular, an = [xn ]G(an ) (x).
To get an idea about how generating functions may help us, let us consider a
simple example of a linear recurrence relation, an+1 = 2an + 1 for n ≥ 0 with
a0 = 0. Take a moment to see whether you can quickly guess the solution for the
closed form formula of this sequence.
Now let’s see what the generating function can tell us. We do this by multiplying
the recurrence relation by xn and summing over all values of n for which it is valid,
and then we try to relate both sides to the generating function G(x). So we obtain
X X X
an+1 xn = 2an xn + xn .
n≥0 n≥0 n≥0

G(x)−a0 G(x)
The left-hand side is n≥0 an+1 xn =
P
= x ,
since a0 = 0 in this problem.
Px
The right hand side is n≥0 2an xn + n≥0 xn = 2G(x) + n≥0 xn . So we have
P P

that G(x) = 2G(x) + n≥0 xn , and therefore: (1−2x)G(x) = n≥0 xn and G(x) =
P P
x x
x n
P
1−2x n≥0 x .
4

At this point it is convenient to know that

X 1
(2) xn = .
1−x
n≥0
x
This gives us that G(x) = (1−2x)(1−x) .The geometric series equation (2) implies
n n 1
P
that n≥0 2 x = 1−2x , and it is easier to add two formal power series than
to multiply them, so we use partial fractions
 to turn our product into a sum of
x 2 1
fractions: (1−2x)(1−x) = x 1−2x − 1−x . So
 
X X
G(x) = x 2 2n xn − xn 
n≥0 n≥0

= (2x + 2 x + 2 x + · · · ) − (x + x2 + x3 + · · · )
2 2 3 3

= (2 − 1)x + (22 − 1)x2 + (23 − 1)x3 + · · ·

and it is clear that an = 2n − 1 for each n ≥ 0.
Some Useful Power Series. As we saw in our first problem already, it is con-
venient to be able to recognize the power series expansions of certain functions.
First,
1 X
= xn
1−x
n≥0
which implies that
1 X
= an xn
1 − ax
n≥0
for any non-zero constant a. Using derivatives (or Taylor series), we can derive that
1 X n + k 
= xn
(1 − x)k+1 n
n
Also, using Taylor series we can show for any positive real number α that
X α
(1 + x)α = xk
k
k
α

α(α−1)···(α−k+1)
where k = k! . Four more Taylor series results:
1 X xn
ln =
1−x n
n≥1
X xn
ex =
n!
n≥0
X x2n+1
sin(x) = (−1)n
(2n + 1)!
n≥0
X x2n
cos(x) = (−1)n
(2n)!
n≥0

1 2k k
P

Exercises 3. (1) Show that √1−4x = k k x .
1
√ P 1 2n n


(2) Show that 2x (1 − 1 − 4x) = n n+1 n x .
 5

The Algebra of Formal Power Series. As we have seen already, a linear com-
bination of two formal power series can be calculated as
X X X
u an xn + v bn x n = (uan + vbn )xn .
n n n

Power series can be multiplied using the Cauchy convolution product rule:
!
X X X X
n n
an x · bn x = ak bn−k xn .
n n n k
2 3
For example, (1 − x)(1 + x + x + x + · · · ) = 1. This says that 1 − x and 1 + x +
x2 + x3 + · · · are reciprocal power series. In general, we have the following result:
Proposition 4. A formal power series f = n≥0 an xn has a reciprocal if and only
P
if a0 6= 0 and the reciprocal is
X
bn xn
n≥0

with b0 = 1/a0 , and

1 X
bn = − ak bn−k for n ≥ 1.
a0
k≥1

1
Application to Counting Problems. Note that we have seen that (1−x) k =
P n+k−1
n
n n x . By the Cauchy formula for the multiplication of formal power series
this implies that the number of different ways of writing
n = a1 + a2 + . . . + ak
where the ai are non-negative integers is equal to n+k−1n (which we can of course
1
also see directly). In other words, (1−x)k is the generating function for the number

of different ways of writing n as a sum of k non-negative integers.

Following this line of reasoning, we obtain that the generating function for the
number of ways to write n as a sum of 5 odd integers is (x + x3 + x5 + · · · )5 =
 5
x
1−x2 .

Exercises 5. (1) Determine the generating function for the number of ways
to distribute n identical candies (for a large number n) to four children so
that the first two children receive each an odd number of candies, the third
child receives at least three candies and the fourth child receives at most
two candies.
(2) (Challenge) Show that the number of ways to make 10m cents change using
only pennies, nickels, and dimes is (m + 1)2 .
(3) Use generating functions to find bn , the number of ways that n ≥ 0 identical
candies can be distributed among 4 children and 1 adult in such a way that
each child receives an odd number of candies and the adult receives 0, 1,
or 2 candies.
(4) In a certain game it is possible to score 1, 2, or 4 points at each turn. Find
the generating function for the number of ways to score n points in a game
in which there are at least two turns where 4 points are scored.
The Calculus of Formal Power Series. When we use formal power series to
solve recurrence relations, a useful operation is the following collection of shifts:
6

If f (x) is the nerating function for (an )∞ 0 , then the generating function for
f (x)−a0 f (x)−a0 −a1 x
(an+1 )∞
0 is x ; the generating function for (an+2 )∞
0 is x2 ; and in
general,
Rule 6 (Shift). If f (x) is the generating function for (an )∞ 0 , then for any integer
∞ f (x)−a0 −a1 x−a2 x2 −···−ah−1 xh−1
h > 0, the generating functioni for (an+h )0 is xh
.
Another question you may want to ask is: if f (x) is the generating function
∞
for (a
Pn )0 , then what is P the generating function for (nan )∞
0 ? First note that if
0
f = n an x , then f = n nan xn−1 . We will write D for the operation of taking
n

a derivative (so Df = f 0 ). Then we see that xDf (x) is the power series for (nan )∞
0
and in general (xD)k f is the power series for (nk an )∞ 0 . This generalizes to the
following rule:
Rule 7 (P (n)-Rule). If f (x) is the generating function for (an )∞ 0 and P is a
polynomial, then P (xD)f is the generating function for (P (n)an )∞
0 .
From the Cauchy product rule for formal power series we can derive:
f (x)
Rule 8 (Partial Sums). If f (x) is the formal power series for (an )∞ , then is
P 0∞ 1−x
n
the formal power series for the sequence of partial sums j=0 aj .
0

Two Independent Variables.

  Consider again the recursion for the Stirling num-
n
bers of the second kind, :
k
     
n n−1 n−1
= +k
k k−1 k
 
0
where = 1. If we want to use generating functions to study this sequence,
0
we have three options:
X n 
An (y) = yk
k
k
X n 
Bk (x) = xn
k
n
X n 
C(x, y) = xn y k .
k
n,k

Because of the occurrence of the factor k in the recurrence, the Bk -approach is

the easiest. This translates the recurrence relation into
Bk (x) = xBk−1 (x) + kxBk (x) (k ≥ 1; B0 (x) = 1).
This leads to
x
Bk (x) = Bk−1 (x) (k ≥ 1; B0 (x) = 1).
1 − kx
Unwinding this gives us
X n  xk
Bk (x) = xn = (k ≥ 0).
k (1 − x)(1 − 2x)(1 − 3x) · · · (1 − kx)
n
 7

So our last task is to find the partial fractions expansion

k
1 X αj
= .
(1 − x)(1 − 2x)(1 − 3x) · · · (1 − kx) j=1 1 − jx
Show that
1
αr =
(1 − 1/r)(1 − 2/r) · · · (1 − (r − 1)/r)(1 − (r + 1)/r) · · · (1 − k/r)
rk−1
= (−1)k−r
(r − 1)!(k − r)!
for 1 ≤ r ≤ k. So we get that
xk
   
n
= [xn ]
k (1 − x)(1 − 2x)(1 − 3x) · · · (1 − kx)
 
1
= [xn−k ]
(1 − x)(1 − 2x)(1 − 3x) · · · (1 − kx)
k
X αr
= [xn−k ]
r=1
1 − rx
k
X 1
= αr [xn−k ]
r=1
1 − rx
k
X
= αr rn−k
r=1
k
X rk−1
= (−1)k−r rn−k
r=1
(r − 1)!(k − r)!
k
X rn
= (−1)k−r
r=1
r!(k − r)!
Recall how the Bell numbers are related to the Stirling numbers of the second
kind (as sums). So we can get a closed formula for them from the closed formula
of the Stirling numbers. However, we could also use generating functions to find
a new recurrence relation for the Bell numbers. This would take the exponential
generating functions introduced in the next subsection.
The Exponential Generating Functions. In this section we introduce a new
clothesline with new algebraic properties. The exponential generating function for
a sequence (an )∞
0 is the formal power series
X an
xn .
n!
n≥0

Lets see how the operations for generating functions translate in this situation.
For example, what is the generating function for the shifted sequence (an+1 )∞0 ? It
turns out that this is f 0 , i.e., Df . So our first new rule is
Rule 9 (Exponential Shift). If f is the exponential generating function for (an )∞
0 ,
and h a non-negative integer, then Dh f is the exponential generating function for
(an+h )∞
0 .
8

Multiplying by a polynomial in n works the same way as before:

Rule 10 (Exponential P (n)-Rule). If f is the exponential generating function for

(an )∞
0 , and P a given polynomial, then P (xD)f is the generating function for
(P (n)an )∞
0 .

Products work differently than before. Recall that for ordinary generating func-
tions, the product of two functions had coefficients given by Cauchy convolutions
of the terms of the orginal sequences. The new rule is

Rule 11 (Exponential Product Rule). Let f be the exponential generating function

of (an )∞ ∞
0 and g the exponential generating function of (bn )0 . Then f g is the
exponential generating function of
!∞
X n
ar bn−r .
r
r
0

Ordinary versus Exponential Generating Functions. The main difference

between the two types of generating functions discussed so far is the sequence
represented by the product of two generating functions.
For example, ordinary generating functions can be used to find the number of
ways we can make change when we have coins of certain values, but exponential
generating functions can be used when we want to make words out of certain letters
(and the order is important).
We will now consider two examples of situations where the recursion formula
indicates which type of generating function will be most appropriate.

Example 12. We want to count the number f (n) of ways of arranging n pairs of
left and right parentheses into a legal string. To find a recurrence relation, we attach
to each legal string a positive integer k which is the smallest positive integer k such
that the first 2k characters of the string also form a legal string of parentheses. For
example, the string ()(()) has k = 1, but (())() has k = 2 and (()())() has k = 3. A
legal string of length 2n is called primitive if k = n.
Note that the number of legal strings of length 2n with integer k is equal to
f (k − 1)f (n − k), since the matching right parenthesis for the first left parenthesis
is at position 2k and in between those two positions we may place any legal string
of length 2k − 2; furthermore, this primitive string must be followed by any legal
string of lenth 2n − 2k. So we find that
X
f (n) f (k − 1)f (n − k) (n 6= 0; f (0) = 1)
k

where we assume that f of a negative argument is zero.

Note that this sum suggests that we may want to consider the ordinary power
series for f (n), since theP
formula on the right looks like the convolution product.
To be precise, if F (x) = n f (n)xn , then the n
P sum above kis the coefficient of x in
the product of the series F and the series k f (k − 1)x = xF (x). So we derive
that F (x) − 1 = xF (x)2 . To solve this, we need to solve a quadratic. A priori, we
obtain two solutions:
√
1 ± 1 − 4x
F (x) =
2x
 9

However, for x = 0, we know√that our generating function takes the value 1. This is
only the case for F (x) = 1− 2x
1−4x
. The coefficients of this sequence are [xn ]F (x) =
1 2n


n+1 n , the famous Catalan numbers.

Example 13. For our second example, we will look more closely at the number of
derangements of n letters (permutations without any fixed points). Note that the
total number of permutations
P n
of n letters is n!. Also the number of permutations
with k fixed points is k Dn−k . This leads us to the equation
X n
n! = Dn−k (n ≥ 0).
k
k

Taking the exponential generating function on both sides gives

1
= ex D(x),
1−x
where D(x) is the exponential generating function for the derangement numbers.
So we see that D(x) = e−x /(1 − x), and the coefficient for xn gives
Dn 1 1 1
= 1 − 1 + − + · · · + (−1)n .
n! 2! 3! n!
The Snake Oil Method
First a couple of reminders of conventions: we will assume that nk = 0 whenever

k < 0 or when 0 ≤ n < k, and we will assume that all sums for which the limits
are not explicitly stated are summed from −∞ to ∞. So we have for example,
X n
= 2n ,
k
k

and we can write

X n  X n  X n
xk = x−r xr+k = x−r xs = x−r (1 + x)n ,
r+k r+k s
s
k k

without needing to worry about the boundaries of the sums. Finally, the basic
power series we will use most are
X r  xk
xr = (k ≥ 0)
k (1 − x)k+1
r≥0
X n
xr = (1 + x)n
r
r
X 1 2n 1 √
xn = (1 − 1 − 4x).
n
n + 1 n 2x
The snake oil method works for sums with an additional free variable, such as
X k 
(n = 0, 1, 2, · · · )
n−k
k≥0
k
P

The variable n is free in this expression, so we could write f (n) = k≥0 n−k and
we would like to obtain a simpler description for this function. A lot of traditional
methods would work internally: manipulate the expression inside the summation.
10

Instead, snake oil works externally: it takes the generating function F (x) for the
f (n). So,
X X k 
F (x) = xn .
n
n−k
k≥0
n
Note that we can bring x inside the second sum and then we can interchange the
two sum symbols, so
XX k 
F (x) = xn .
n
n−k
k≥0

To view the new internal sum as an instance of the binomial sum, we need to adjust
the power of x,
X X k 
F (x) = xk xn−k .
n
n − k
k≥0

Taking r as the new dummy variable for the internal sum gives
X X k  X X 1
F (x) = xk xr = xk (1 + x)k = (x + x2 )k = .
r
r 1 − x − x2
k≥0 k≥0 k≥0

We recognize this as the generating function for the Fibonacci numbers, so f (n) =
Fn+1 .
Here is an overview for the steps of the snake oil method to sweep all combina-
torial sums under the rug:
(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 (n))∞ 0 .
(3) Note that F (x) is now a double sum. Move the exponent of x inside and
interchange the order of the summation.
(4) Manipulate the exponent of x so that you can evaluate the inside sum in
simple closed form using one of the standard power series given above.
(5) Try to identify the coefficients of the resulting generating function.
Here are some examples to practice on. Evaluate the following combinatorial
sums:
X  n + k 2k  (−1)k
(1) with n, m ≥ 0. (Hint: choose n as the free
m + 2k k k+1
k
variable.)  
X n − k n−2k
(2) (−1)k y for n ≥ 0.
k
k≤ n
2
X n + k 
(3) 2n−k for n ≥ 0.
2k
k

Example 14. Snake oil can also be used to show that two combinatorial sums are
equal without evaluating either one of them. Try it to prove the following identity:
X mn + k  X mn
= 2k
k m k k
k k
 11

Inversion Formulas. Snake oil can also be used to find inversion formulas. But
you need to choose the type of generating function you want to use carefully. Sup-
pose that two sequences (ar )∞ ∞
0 and (bs )0 are related by the formula
X r
ar = bs
s
s
An inversion of this formula would give bs as function of ar . Because of the multipli-
cation rule for exponential generating functions, and the fact that the exponential
generating function for (1)∞ x
0 is e , we see that if we compare the exponential gen-
erating function A(x) for (ar ) with the exponential generating function B(x) for
(bs ), we get A(x) = ex B(x). So we see that B(x) = e−x A(x), and this translates
into
Xn
bn = (−1)n−m am (n ≥ 0).
m
m

Exercises
(1) Let A1 , A2 , . . . and B1 , B2 , . . . be sets such that A1 = ∅, B1 = {0}, and
An+1 = {x + 1| x ∈ Bn } and Bn+1 = An ∪ Bn − An ∩ Bn ,
for all positive integers n. Determine all positive integers n such that Bn =
{0}.
(2) [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.
(3) [China 2000, Yuming Huang] The sequence (an )n≥1 satisfies the conditions
a1 = 0, a2 = 1,
1 1  n
an = nan−1 + n(n − 1)an−2 + (−1)n 1 − ,
2 2 2
n ≥ 3. Determine the explicit form of
       
n n n n
fn = an + 2 an−1 + 3 an−2 + · · · + (n − 1) a2 + n a1 .
1 2 n−2 n−1
(4) [Highschool Mathematics, 1994/1, Qihong Xie] Find the number of subsets
of {1, 2, . . . , 2000}, the sum of whose elements is divisible by 5.
(5) [AIME 2001] A mail carrier delivers mail to nineteen houses on the east
side of Elm Street. The carrier notes 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?
(6) A function f is defined for all n ≥ 1 by the relations (a) f (1) = 1; (b)
f (2n) = f (n); and (c) f (2n + 1) = f (n) + f (n + 1). Find its generating
function.
(7) Find the number f (n, k) of k-subsets of [n] = {1, 2, 3, . . . , n}.
(8) Let f (n, m, k) be the number of strings of n 0’s and 1’s that contain exactly
m 1’s, no k of which are consecutive.
(a) Find a recurrence formula for f .
(b) Find, in simple closed form, the generating functions
X
Fk (x, y) = f (n, m, k)xn y m (k = 1, 2, . . .)
n,m≥0
12

(c) Find an explicit formula for f (n, m, k) from the generating function.
(9) Let D(n) be the number of derangements of n letters.
(a) Find in simple explicit form the exponential generating function of
(D(n))∞
0 .
(b) Prove by any method that
D(n + 1) = (n + 1)D(n) + (−1)n+1 (n ≥ 0; D(0) = 1)
(c) Prove by any method that
D(n + 1) = n(D(n) + D(n − 1)) (n ≥ 1; D(0) = 1; D(1) = 0)
(d) Show that the number of permutations of n letters that have exactly
1 fixed point differs from the number with no fixed point by ±1.
(e) Let Dk (n) be the number of permutations of n letters that have exactly
k fixed points. Show that
X xn y k e−x(1−y)
Dk (n) = .
n! 1−x
k,n≥0

(f) Show that

X n 
r xr = (1 + x)(1 + x2 )n .
r
b 2 c
Then use Snake Oil to evaluate
X n n − k 
r yk
k b n−k c
k
explicitly, when y = ±2 (due to D.E. Knuth).
(g) Find the generating function of these sums, whatever the value of y.
(10) (a) Find an explicit formula, not involving sums, for the polynomial
X k 
tk .
n−k
k≥0

(b) Evaluate
X 2n + 1

p+k

.
2p + 2k + 1 k
k
(c) Show that
X  r  s  r + s
= .
m
m t−m t
Then evaluate
X n2
.
k
k
(d) Show that (Graham and Riordan)
X 2n + 1m + k  2m + 1
= .
2k 2n 2n
(e) Show that for all n ≥ 0,
X nk   
n j
k
x = x (1 + x)n−j .
k j j
k
 13

(f) Show that for all n ≥ 0,

X n + k   x2 − 1 n−k  x − 1 2n+1  x + 1 2n+1
x = +
2k 4 2 2
k
(g) Show that for all n ≥ 1,
X n + k − 1 (x − 1)2k xn−k (xn − 1)2
= .
2k − 1 k n
k≥1

(11) Prove that

 2  
X 2n 2n
(−1)n−k =
k n
k
(12) To evaluate a sum that is of the form
X
S(n) = f (k)g(n − k),
k
the natural method is to recognize S(n) as [xn ]{F (x)G(x)}, where F and
G are the ordinary generating functions of (fn ) and (gn ). Use this method
to evaluate
X 1 2k  1

2n − 2k

S(n) = .
k+1 k n−k+1 n−k
k
(13) [Vietnam 1998, Category A] Let (an )∞
0 be a sequence of positive integers
defined recursively by
a0 = 20, a1 = 100, an+2 = 4an+1 + 5an + 20.
Determine the smallest positive integer h for which an+h − an is divisible
by 1998 for every non-negative integer n.
(14) [Vietnam 1998, Category B] Let a, b be integers. Define a sequence (an )∞
0
of integers defined by
a0 = a, a1 = b, a2 = 2b − a + 2, an+3 = 3an+2 − 3an+1 + an
for n ≥ 0.
(a) Find the general term of the sequence.
(b) Determine all integers a and b for which an is a perfect square for all
n ≥ 1998.

Further Reading
These notes are largely based on the book Generatingfunctionology by Herbert S.
Wilf, which may be downloaded from http://www.math.upenn.edu/ wilf/DownldGF.html
Other useful books on combinatorics that discuss generating functions are:
• John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff, Combinatorics and
Graph Theory, Springer Verlag, New York 2000
• Daniel A. Marcus, Combinatorics A Problem Oriented Approach, The MAA,
1998
• George E. Martin, Counting: The Art of Enumerative Combinatorics, Springer
Verlag, New York 2001