Generating Functions
Generating function models
A Somasundaram
Generating function models 1 / 20
Definition
The expression
∞
X
n
A(x) = a0 + a1 x + · · · + an x + · · · = ar x r
r =0
is called a formal power series.
Generating function models 2 / 20
Definition
Let each nonzero coefficient of each formal power series
Ai (x) be 1.
Then the coefficient of x r in the product
A1 (x)A2 (x) · · · An (x) can be interpreted as the number of
non-negative integral solutions to an equation
e1 + e2 + · · · + en = r
where constraints on each ei are determined by the
exponents of the ith factor Ai (x).
Generating function models 3 / 20
Exercises
Build a generating function for ar = the number of
integral solutions to the equation e1 + e2 + e3 = r if:
(a) 0 ≤ ei ≤ 3 for each i.
(b) 2 ≤ ei ≤ 5 for each i.
(c) 0 < ei for each i.
(d) 0 ≤ ei ≤ 6 and e1 is even;
2 < e2 ≤ 7 and e2 is odd; 5 ≤ e3 ≤ 7.
Generating function models 4 / 20
Exercises
Write a generating function for ar when ar is
(a) the number of ways of selecting r balls from 3 red
balls, 5 blue balls, 7 white balls.
(b) the number of ways of selecting r coins from an
unlimited supply of 25 fills, 50 fills and 1 dirham.
(c) the number of ways of obtaining a total of r upon
tossing 50 distinguishable dice.
Generating function models 5 / 20
Result
Theorem
Enumerating r-combinations with unlimited repetitions.
V (n, r ) = the number of r-combinations of n distinct
objects with unlimited repetitions
= the number of non-negative integral solutions
to x1 + x2 + · · · + xn = r
= the number of ways of distributing r similar
balls into n numbered boxes
= C (n − 1 + r , n − 1) = C (n − 1 + r , r )
Generating function models 6 / 20
Geometric Series
∞
1
xr = 1 + x + x2 + · · ·
P
1
1−x =
r =0
∞
1
ar x r = 1 + ax + (ax)2 + · · ·
P
2
1−ax =
r =0
∞
1
(−1)r x r = 1 − x + x 2 − · · ·
P
3
1+x =
r =0
∞
1
(−1)r ar x r = 1 − ax + (ax)2 − · · ·
P
4
1+ax =
r =0
Generating function models 7 / 20
Geometric Series
∞ ∞
1 n
x r )n = C (n − 1 + r , r )x r
P P
1 ( 1−x ) =(
r =0 r =0
∞ ∞
1 n
(−1)r x r )n = C (n − 1 + r , r )(−1)r x r
P P
2 ( 1+x ) =(
r =0 r =0
∞
1
)n C (n − 1 + r , r )ar x r
P
3 ( 1−ax =
r =0
∞
1
)n = C (n − 1 + r , r )(−a)r x r
P
4 ( 1+ax
r =0
Generating function models 8 / 20
Other identities
If n is a positive integer,
1−x n+1
1 1 + x + x2 + · · · + xn = 1−x
2 (1 + x)n = 1 + C (n, 1)x + C (n, 2)x 2 + · · · + C (n, n)x n
3 (1 − x)n =
1 − C (n, 1)x + C (n, 2)x 2 + · · · + (−1)n C (n, n)x n
Generating function models 9 / 20
Exercises
Find the coefficient of x 10 in
(a) (1 + x + x 2 + · · · )2
(b) (x 3 + x 4 + · · · )2
(c) x 4 (1 + x + x 2 + x 3 )(1 + x + · · · + x 4 )(1 + x + · · · + x 12 )
Generating function models 10 / 20
Exercises
Let ar be the number of non-negative integral solution to
x1 + x2 + x3 = r
(a) Find a10 if 0 ≤ xi ≤ 4 for each i.
(b) Find a50 where
2 ≤ x1 ≤ 50, 0 ≤ x2 ≤ 50, 5 ≤ x3 ≤ 25.
Generating function models 11 / 20
Exercises
Find the coefficient of x n in the following:
1
1
1 − 7x + 12x 2
2
7x 2 + 3x + 2
(x − 2)(x + 1)2
Generating function models 12 / 20
Exercises
1 Let ar be the number of ways the sum r can be
obtained by tossing 50 distinguishable dice. Write a
generating function and find the number of ways to
find the sum of 100.
2 Write a generating function for ar , the number of
ways of selecting r letters from {5.a, 6.b, 8.c} if each
selection must include at least one a, at least one b
and at least 2c’s. Find a8
Generating function models 13 / 20
Solving Recurrence relations
Solve the following recurrence relations by substitution.
1 an = an−1 + n where a0 = 2.
2 an = an−1 + n2 where a0 = 7.
3 an = an−1 + n(n − 1) where a0 = 1.
1
4 an = an−1 + where a0 = 1.
n(n + 1)
Generating function models 14 / 20
Solving Recurrence relations
Problem
The Towers of Hanoi problem.
There are 3 pegs and n circular disks of increasing
diameter on one peg, with the largest disk on the bottom.
These disks are to be transferred one at a time onto
another peg with the provision that at no time one is
allowed to put a larger disk on one with smaller diameter.
Determine the number of moves required for the transfer.
Generating function models 15 / 20
Solving Recurrence relations
Solve the following recurrence relations using generating
functions.
1 an − an−1 − 9an−2 + 9an−3 = 0 for n ≥ 3 and
a0 = 0, a1 = 1, a2 = 2.
2 an − an−1 = n for n ≥ 1 and a0 = 0.
3 an − an−1 = 2(n − 1) for n ≥ 1 and a0 = 2.
4 an − 2an−1 = 4n−1 for n ≥ 1 and a0 = 1, a1 = 3.
Generating function models 16 / 20
The method of characteristic roots
For the recurrence relation
an + c1 an−1 + · · · + ck an−k = 0
for n ≥ k, where ck 6= 0,
the characteristic polynomial is given by
C (t) = t k + c1 t k−1 + · · · + ck = 0
Generating function models 17 / 20
The method of characteristic roots
If the characteristic polynomial has distinct roots
α1 , · · · , αn then the general solution is
an = c1 α1n + · · · + ck αkn
If the characteristic polynomial has the root αi is of
multiplicity mi then the general solution is
an = (ci0 + ci1 n + ci2 n2 + · · · + cimi −1 nmi −1 )αin
Generating function models 18 / 20
The method of characteristic roots
Solve the following recurrence relations using the
characteristic roots.
1 an − 3an−1 − 4an−2 = 0 for n ≥ 2 and a0 = 0, a1 = 1.
2 an − 4an−1 − 12an−2 = 0 for n ≥ 2 and
a0 = 4, a1 = 16/3.
3 an − 4an−1 + 4an−2 = 0 for n ≥ 2 and
a0 = 5/2, a1 = 8.
4 6an − 19an−1 + 15an−2 = 0 for n ≥ 2 and
1
a0 = 0, a1 = − .
6
Generating function models 19 / 20
The method of Undetermined Coefficients
Solve the following recurrence relations using the method
of undetermined coefficients.
1 an − 3an−1 + 2an−2 = 3n
2 an − 7an−1 + 12an−2 = 3n
3 an − 7an−1 + 12an−2 = n4n
4 an + 3an−1 − 10an−2 = n2 + n + 1
Generating function models 20 / 20
THANK YOU
Generating function models 21 / 20