MIT 18.

211: COMBINATORIAL ANALYSIS

FELIX GOTTI

Lecture 16: Generating Functions II: Products and Catalan Numbers

In this lecture we continue with ordinary generating functions. We will see that
if we have certain combinatorial interpretation for the coefficients of two generating
functions, then there is a natural way to interpret the coefficients of the product of
such functions. We will also see some applications of this interpretation.

Proposition 1. Let F (x) and G(x) be the generating functions of the sequences (an )n≥0
and (bn )≥0 , respectively. Then the following statements hold.
(1) F 0 (x) = ∞ n−1
P
n=0 nan x .
P∞
(2) F (x) + G(x) = n=0 (an + bn )xn .
(3) F (x)G(x) = ∞
P n
Pn
n=0 cn x , where cn = k=0 ak bn−k .

Proof. (1) Integrating the formal power series ∞ n

P
n=0 an x term by term, we obtain
X∞ 0 X ∞
0 n
F (x) = an x = an nxn−1 .
n=0 n=0

P∞ P∞ P∞
(2) Adding the forF (x) + G(x) = n=0 an x n + n=0 bn x
n
= n=0 (an + bn )xn .
(3) Observe that the coefficient of xn in the product F (x)G(x) are the sum of the
terms (ak xk )(b` x` ) such that k + ` = n. Therefore
n
X
cn = a0 bn + a1 bn−1 + · · · + an−1 b1 + an b0 = ak bn−k .
k=0

Example 2. Let Cn be the number of strings of balanced parentheses of length 2n,

where C0 = 1. Let us find a explicit formula for Cn by using generating functions.
First, observe that every string of balanced parentheses of length 2n has the form
(Pk )P(n−1)−k for some k ∈ J0, n − 1K, where Pk is a string of balanced parentheses of
length 2k, the closing parenthesis ”)”, which is in 2(k + 1)-th position, is the match of
1
2 F. GOTTI

the first opening parenthesis, and P(n−1)−k is a string of balanced parenthesis of length
2((n − 1) − k). Therefore
n−1
X
(0.1) Cn = C0 Cn−1 + · · · + Cn−1 C0 = Ck C(n−1)−k .
k=0

Now
P∞ let C(x) be the generating function of the sequence (Cn )n≥0 , that is, C(x) =
n
n=0 Cn x . Using the recurrence (0.1), we see that
∞
X ∞ X
X n−1  ∞ X
X n 
C(x) − 1 = C n xn = Ck C(n−1)−k xn = x Ck Cn−k xn = xC(x)2 .
n=1 n=1 k=0 n=0 k=0
2
Then we see that xC(x) − C(x) + √ 1 = 0,
and solving this quadratic equation for
1
C(x) we obtain the solutions 2x 1 ± 1 − 4x . The equality C(0) = C0 = 1 allows to
conclude that √
1 − 1 − 4x
C(x) = .
2x
By virtue of the Generalized Binomial Theorem,
∞  ∞ 1 −1 −3 ∞
· · · −(2n−3) 2n (2n − 3)!! n

1/2
X 1/2 n
X
2 2 2 2 n
X
(1−4x) = (−4x) = x = 1−2x− x ,
n=0
n n=0
n! n=2
n!
where (2n + 1)!! := 1 · 3 · · · (2n + 1) for every n ∈ N0 . Thus,
√ ∞ ∞ ∞
2n−1 (2n − 3)!! n−1 2n (2n − 1)!! n
 
1 − 1 − 4x X X X 1 2n n
= 1+ x = 1+ x = 1+ x .
2x n=2
n! n=1
(n + 1)! n=1
n+1 n
1 2n


Hence we conclude that Cn = n+1 n
for every n ∈ N.

Practice Exercises
Exercise 1. If F (x), G(x), and H(x) are the generating functions of the sequences
(an )n≥0 , (bn )≥0 , and (cn )≥0 , respectively. Argue that
∞  X
X 
F (x)G(x)H(x) = aj b k c ` x n .
n=0 j+k+`=n

Generalize the previous statement for the product of m generating functions F1 (x), . . . , Fm (x).

Exercise 2. Let an be the number of ways to provide change for n cents out of pennies,
nickels, dimes, and quarters.
(1) Find the generating function of the sequence (an )n≥0 .
(2) Find a211 .
 COMBINATORIAL ANALYSIS 3
Department of Mathematics, MIT, Cambridge, MA 02139
Email address: fgotti@[Link]