6.042/18.062J Mathematics for Computer Science April 7,2005
Srini Devadas and Eric Lehman Lecture Notes
Generating Functions
Generating functions are one of the most surprising,useful,and clever inventions in
discrete math,Roughly speaking,generating functions transform problems about se-
quences into problems about functions,This is great because we’ve got piles of mathe-
matical machinery for manipulating functions,Thanks to generating functions,we can
apply all that machinery to problems about sequences,In this way,we can use generating
functions to solve all sorts of counting problems,There is a huge chunk of mathematics
concerning generating functions,so we will only get a taste of the subject,
In this lecture,we’ll put sequences in angle brackets to more clearly distinguish them
from the many other mathemtical expressions?oating around,
1 Generating Functions
The ordinary generating function for the in?nite sequence?g
0
,g
1
,g
2
,g
3
...? is the formal
power series,
3
G(x) = g
0
+ g
1
x + g
2
x
2
+ g
3
x +···
A generating function is a,formal” power series in the sense that we usually regard x
as a placeholder rather than a number,Only in rare cases will we let x be a real number
and actually evaluate a generating function,so we can largely forget about questions of
convergence,Not all generating functions are ordinary,but those are the only kind we’ll
consider here,
Throughout the lecture,we’ll indicate the correspondence between a sequence and its
generating function with a double-sided arrow as follows,
2 3
+ g
3
x?g
0
,g
1
,g
2
,g
3
,...? ←→ g
0
+ g
1
x + g
2
x +···
For example,here are some sequences and their generating functions,
3
0,0,0,0,...? ←→ 0 + 0x + 0x
2
+ 0x = 0 +···
3
1,0,0,0,...? ←→ 1 + 0x + 0x
2
+ 0x = 1 +···
3
3,2,1,0,...? ←→ 3 + 2x + 1x
2
+ 0x = 3 + 2x + x
2
+···
The pattern here is simple,the i-th term in the sequence (indexing from 0) is the coef?cient
of x
i
in the generating function,
Recall that the sum of an in?nite geometric series is,
1
3
1 + z + z
2
+ z =+···
1?z
2 Generating Functions
This equation does not hold when z ≥ 1,but once again we won’t worry about conver-||
gence issues,This formula gives closed-form generating functions for a whole range of
sequences,For example,
1
,1,1,1,...? 1 + x + x
2
+ x =?1 ←→
3
+···
1?x
1
4
=?1,?1,1,?1,...x
3
+ x←→ 1?x + x
2
···
1 + x
1
3 3
1,a,a
2
,a,...? 1 + ax + a
2
x
2
+ a x =
1?ax
←→
3
+···
1
4
+ x
6
1,0,1,0,1,0,...? 1 + x
2
+ x =
1?x
2
←→ +···
2 Operations on Generating Functions
The magic of generating functions is that we can carry out all sorts of manipulations on
sequences by performing mathematical operations on their associated generating func-
tions,Let’s experiment with various operations and characterize their effects in terms of
sequences,
2.1 Scaling
Multiplying a generating function by a constant scales every term in the associated se-
quence by the same constant,For example,we noted above that,
1
4 6
1,0,1,0,1,0,...? ←→ 1 + x
2
+ x + x =
1?x
2
+···
Multiplying the generating function by 2 gives
2
= 2 + 2x
2
+ 2x
4
+ 2x
6
1?x
2
+···
which generates the sequence,
,0,2,0,2,0,...2
Rule 1 (Scaling Rule),If
x),?f
0
,f
1
,f
2
,...? ←→ F(
then
cf
0
,cf
1
,cf
2
,F(x)....? ←→ c·
Generating Functions 3
Proof,
cf
0
,cf
1
,cf
2
,...? cf
0
+ cf
1
x + cf
2
x
2
←→ +· · ·
= c· (f
0
+ f
1
x + f
2
x
2
+· · · )
= cF(x)
2.2 Addition
Adding generating functions corresponds to adding the two sequences term by term,For
example,adding two of our earlier examples gives,
1
1,1,1,1,1,1,..,? ←→
1? x
1
+? 1,? 1,1,? 1,1,? 1,..,? ←→
1 + x
1 1
2,0,2,0,2,0,..,+ ←→
1? x 1 + x
We’ve now derived two different expressions that both generate the sequence? 2,0,2,0,...?,
Not surprisingly,they turn out to be equal,
1 1 (1 + x) + (1? x) 2
+ = =
1? x 1 + x (1? x)(1 + x) 1? x
2
Rule 2 (Addition Rule),If
f
0
,f
1
,f
2
,...? ←→ F(x),and
g
0
,g
1
,g
2
,...? ←→ G(x),
then
f
0
+ g
0
,f
1
+ g
1
,f
2
+ g
2
,...? ←→ F(x) + G(x),
Proof,
∞
f
0
+ g
0
,f
1
+ g
1
,f
2
+ g
2
,...? ←→ (f
n
+ g
n
)x
n
n=0
∞
∞
= f
n
x
n
+ g
n
x
n
n=0 n=0
= F(x) + G(x)
4 Generating Functions
2.3 Right Shifting
Let’s start over again with a simple sequence and its generating function,
1
,1,1,1,...? ←→?1
1?x
Now let’s right-shift the sequence by adding k leading zeros,
k+1 k+2 k+3
0,0,...,0,1,1,1,...? x
k
+ x + x + x
←→ +···
k zeroes
k 3
= x ·(1 + x + x
2
+ x +···)
k
x
=
1?x
Evidently,adding k leading zeros to the sequence corresponds to multiplying the gener-
ating function by x
k
,This holds true in general,
Rule 3 (Right-Shift Rule),If?f
0
,f
1
,f
2
,...? ←→ F(x),then,
0,0,...,0,f
0
,f
1
,f
2
,...? ←→ x
k
F(x)
·
k zeroes
Proof,
k zeroes
f
0
x
k
+ f
1
x
k+1
+ f
2
x
k+2
0,0,...,0,f
0
,f
1
,f
2
,... ←→ +···
3
= x
k
·(f
0
+ f
1
x + f
2
x
2
+ f
3
x +···)
k
= x F(x)·
2.4 Differentiation
What happens if we take the derivative of a generating function? As an example,let’s
differentiate the now-familiar generating function for an in?nite sequence of 1’s,
d 1d
(1 + x + x
2
+ x
3
+ x
4
=
dx
+···)
dx 1?x
1
3
1 + 2x + 3x
2
+ 4x =
2
+···
(1?x)
1
1,2,3,4,...? ←→
(1?x)
2
We found a generating function for the sequence?1,2,3,4,...?!
In general,differentiating a generating function has two effects on the corresponding
sequence,each term is multiplied by its index and the entire sequence is shifted left one
place,
5 Generating Functions
Rule 4 (Derivative Rule),If
f
0
,f
1
,f
2
,f
3
,...? ←→ F(x),
then
(x).?f
1
,2f
2
,3f
3
,...? ←→ F
Proof,
f
1
,2f
2
,3f
3
,...? = f
1
+ 2f
2
x + 3f
3
x
2
+ ···
d
(f
0
+ f
1
x + f
2
x
2
+ f
3
x
3
+=
dx
···)
d
= F(x)
dx
The Derivative Rule is very useful,In fact,there is frequent,independent need for
each of differentiation’s two effects,multiplying terms by their index and left-shifting one
place,Typically,we want just one effect and must somehow cancel out the other,For ex-
ample,let’s try to?nd the generating function for the sequence of squares,?0,1,4,9,16,...?,
If we could start with the sequence?1,1,1,1,...?and multiply each term by its index two
times,then we’d have the desired result,
0,1 1,2 2,3 3,...? =?0,1,4,9,...0 · · · ·
A challenge is that differentiation not only multiplies each term by its index,but also
shifts the whole sequence left one place,However,the Right-Shift Rule 3 tells how to
cancel out this unwanted left-shift,multiply the generating function by x,
Our procedure,therefore,is to begin with the generating function for?1,1,1,1,...?,
differentiate,multiply by x,and then differentiate and multiply by x once more,
1
1,1,1,1,...? ←→
1?x
d 1 1
=?1,2,3,4,...? ←→
dx 1?x (1?x)
2
1 x
=?0,1,2,3,...? ←→ x·
(1?x)
2
(1?x)
2
d x 1 + x
=?1,4,9,16,...? ←→
dx (1?x)
2
(1?x)
3
1 + x x(1 + x)
=?0,1,4,9,...? ←→ x·
(1?x)
3
(1?x)
3
Thus,the generating function for squares is,
x(1 + x)
(1?x)
3
6 Generating Functions
3 The Fibonacci Sequence
Sometimes we can?nd nice generating functions for more complicated sequences,For
example,here is a generating function for the Fibonacci numbers,
x
0,1,1,2,3,5,8,13,21,...? ←→
1?x?x
2
The Fibonacci numbers are a fairly nasty bunch,but the generating function is simple!
We’re going to derive this generating function and then use it to?nd a closed form for
the n-Fibonacci number,Of course,we already have a closed form for Fibonacci numbers,
obtained from the cookbook procedure for solving linear recurrences,But there are a
couple reasons to cover the same ground again,First,we’ll gain some insight into why
the cookbook method for linear recurrences works,And,second,the techniques we’ll use
are applicable to a large class of recurrence equations,including some that we have no
other way to tackle,
3.1 Finding a Generating Function
Let’s begin by recalling the de?nition of the Fibonacci numbers,
f
0
= 0
f
1
= 1
f
n
= f
n?1
+ f
n?2
(for n≥ 2)
We can expand the?nal clause into an in?nite sequence of equations,Thus,the Fibonacci
numbers are de?ned by,
f
0
=0
f
1
=1
f
2
=f
1
+ f
0
f
3
=f
2
+ f
1
f
4
=f
3
+ f
2
,
,
,
Now the overall plan is to de?ne a function F(x) that generates the sequence on the left
side of the equality symbols,which are the Fibonacci numbers,Then we derive a function
that generates the sequence on the right side,Finally,we equate the two and solve for
F(x),Let’s try this,First,we de?ne,
3
+ f
4
x
4
F(x) = f
0
+ f
1
x + f
2
x
2
+ f
3
x + ···
7 Generating Functions
Now we need to derive a generating function for the sequence,
,1,f
1
+ f
0
,f
2
+ f
1
,f
3
+ f
2
,... 0
One approach is to break this into a sum of three sequences for which we know generating
functions and then apply the Addition Rule,
0, 1,0,0,0,x? ,.,? ←→
0,f
0
,f
1
,f
2
,f
3
, xF(x)? ,.,? ←→
+ ? 0,0,f
0
,f
1
,f
2
,..,? ←→ x
2
F(x)
0,1 + f
0
,f
1
+ f
0
,f
2
+ f
1
,f
3
+ f
2
,..,? ←→ x + xF(x) + x
2
F(x)
This sequence is almost identical to the right sides of the Fibonacci equations,The one
blemish is that the second term is 1 + f
0
instead of simply 1,However,this amounts to
nothing,since f
0
= 0 anyway,
Now if we equate F(x) with the new function x+xF(x)+x
2
F(x),then we’re implicitly
writing down all of the equations that de?ne the Fibonacci numbers in one fell swoop,
F(x) = f
0
+ f
1
x + f
2
x
2
+ f
3
x
3
+ f
4
x
4
+,.,
x + xF(x) + x
2
F(x) = 0 + (1 + f
0
) x + (f
1
+ f
0
) x
2
+ (f
2
+ f
1
) x
3
+ (f
3
+ f
2
) x
4
+· · ·
Solving for F(x) gives the generating function for the Fibonacci sequence,
F(x) = x + xF(x) + x
2
F(x)
x
F(x) =
1? x? x
2
Sure enough,this is the simple generating function we claimed at the outset!
3.2 Finding a Closed Form
Why should one care about the generating function for a sequence? There are several
answers,but here is one,if we can?nd a generating function for a sequence,then we can
often?nd a closed form for the n-th coef?cient— which can be pretty useful! For example,
a closed form for the coef?cient of x
n
in the power series for x/(1? x? x
2
) would be an
explicit formula for the n-th Fibonacci number,
So our next task is to extract coef?cients from a generating function,There are sev-
eral approaches,For a generating function that is a ratio of polynomials,we can use the
method of partial fractions,which you learned in calculus,Just as the terms in a par-
tial fractions expansion are easier to integrate,the coef?cients of those terms are easy to
compute,
Let’s try this approach with the generating function for Fibonacci numbers,First,we
factor the denominator,
1? x? x
2
= (1? α
1
x)(1? α
2
x)
8 Generating Functions
1 1
where α
1
=
2
(1 +
√
5) and α
2
=
2
(1?
√
5),Next,we?nd A
1
and A
2
which satisfy,
x A
1
A
2
= +
1?x?x
2
1?α
1
x 1?α
2
x
We do this by plugging in various values of x to generate linear equations in A
1
and A
2
,
We can then?nd A
1
and A
2
by solving a linear system,This gives,
1 1
A
1
= =
α
1
α
2
√
5
1?1
A
2
= =
α
1
α
2
√
5
Substituting into the equation above gives the partial fractions expansion of F(x),
x 1 1 1
=
1?x?x
2
√
5
1?α
1
x
1?α
2
x
Each term in the partial fractions expansion has a simple power series given by the geo-
metric sum formula,
1
2
= 1 + α
1
x + α
2
1
x
1?α
1
x
+···
1
2
= 1 + α
2
x + α
2
2
x
1?α
2
x
+···
Substituting in these series gives a power series for the generating function,
1 1 1
F(x) = √
5
1?α
1
x
1?α
2
x
1
2
2
= √
5
(1 + α
1
x + α
2
2
x
1
x +···)?(1 + α
2
x + α
2
+···)
α
n
1
α
n
f
n
= √
5
2
1?
√
5
n n
1 1 +
√
5
= √
5
2
2
This is the same scary formula for the n-th Fibonacci number that we found using the
method for solving linear recurrences,And this alternate approach sheds some light on
that method,In particular,the strange rules involving repeated roots of the characteristic
equation are re?ections of the rules for?nding a partial fractions expansion!
4 Counting with Generating Functions
Generating functions are particularly useful for solving counting problems,In particular,
problems involving choosing items from a set often lead to nice generating functions,
When generating functions are used in this way,the coef?cient of x
n
is the number of
ways to choose n items,
Generating Functions 9
4.1 Choosing Distinct Items from a Set
The generating function for binomial coef?cients follows directly from the Binomial The-
orem,
k k k k k k k
2
k
k
,,,...,,0,0,0,..,+ x + x + x
0 1 2 k
←→
0 1 2
+···
k
= (1 + x)
k
Thus,the coef?cient of x
n
in (1 + x)
k
is the number of ways to choose n distinct items
k
from a k-element set,For example,the coef?cient of x
2
is,the number of ways to
2
choose 2 items from a k-element set,Similarly,the coef?cient of x
k+1
is the number of
ways to choose k + 1 items from a k-element set,which is zero,
4.2 Building Generating Functions that Count
Often we can translate the description of a counting problem directly into a generating
function for the solution,For example,we could?gure out that (1 + x)
k
generates the
number of ways to select n distinct items from a k-element subset without resorting to
the Binomial Theorem or even fussing with binomial coef?cients!
Here is how,First,consider a single-element set {a
1
},The generating function for the
number of ways to choose n elements from this set is simply 1 + x,we have 1 way to
choose zero elements,1 way to choose one element,and 0 ways to choose more than one
element,Similarly,the number of ways to choose n elements from the set {a
2
} is also
given by the generating function 1 + x,The fact that the elements differ in the two cases
is irrelevant,
Now here is the the main trick,the generating function for choosing elements from a union of
disjoint sets is the product of the generating functions for choosing from each set,We’ll justify this
in a moment,but let’s?rst look at an example,According to this principle,the generating
function for the number of ways to choose n elements from the {a
1
,a
2
}is,
(1 + x) (1 + x) = (1 + x)
2
= 1 + 2x + x
2
·
OGF for OGF for OGF for
{a
1
,a
2
}{a
1
} {a
2
}
Sure enough,for the set {a
1
,a
2
},we have 1 way to choose zero elements,2 ways to choose
one element,1 way to choose two elements,and 0 ways to choose more than two ele-
ments,
Repeated application of this rule gives the generating function for choosing n items
from a k-element set {a
1
,a
2
,...,a
k
},
(1 + x) (1 + x) (1 + x) = (1 + x)
k
·
···
OGF for OGF for OGF for OGF for
{a
1
,a
2
,...,a
k
}{a
1
} {a
2
} {a
k
}
10 Generating Functions
This is the same generating function that we obtained by using the Binomial Theorem,
But this time around we translated directly from the counting problem to the generating
function,
We can extend these ideas to a general principle,
Rule 5 (Convolution Rule),Let A(x) be the generating function for selecting items from set A,
and let B(x) be the generating function for selecting items from set B,If A and B are disjoint,
then the generating function for selecting items from the union A∪Bis the product A(x)·B(x),
This rule is rather ambiguous,what exactly are the rules governing the selection of
items from a set? Remarkably,the Convolution Rule remains valid under many inter-
pretations of selection,For example,we could insist that distinct items be selected or
we might allow the same item to be picked a limited number of times or any number of
times,Informally,the only restrictions are that (1) the order in which items are selected
is disregarded and (2) restrictions on the selection of items from sets Aand Balso apply
in selecting items from A∪B,(Formally,there must be a bijection between n-element
selections from A∪Band ordered pairs of selections from Aand B containing a total of
n elements.)
Proof,De?ne,
∞ ∞ ∞
A(x) = a
n
x
n
,B(x) = b
n
x
n
,C(x) = A( B(x) = c
n
x
n
.x)·
n=0 n=0 n=0
Let’s?rst evaluate the product A(x) B(x) and express the coef?cient c
n
in terms of the ·
a and b coef?cients,We can tabulate all of the terms in this product in a table,
b
0
x
0
b
1
x
1
b
2
x
2
b
3
x
3
..,
a
0
x
0
a
0
b
0
x
0
a
0
b
1
x
1
a
0
b
2
x
2
a
0
b
3
x
3
..,
a
1
x
1
a
1
b
0
x
1
a
1
b
1
x
2
a
1
b
2
x
3
..,
a
2
x
2
a
2
b
0
x
2
a
2
b
1
x
3
..,
a
3
x
3
a
3
b
0
x
3
..,
,
,
.,.,
Notice that all terms involving the same power of x lie on a /-sloped diagonal,Collecting
these terms together,we?nd that the coef?cient of x
n
in the product is,
c
n
= a
0
b
n
+ a
1
b
n?1
+ a
2
b + a
n
b
0n?2
+···
Generating Functions 11
Now we must show that this is also the number of ways to select n items from A∪B,
In general,we can select a total of n items from A ∪ B by choosing j items from A and
n?j items from B,where j is any number from 0 to n,This can be done in a
j
b
n?j
ways,
Summing over all the possible values of j gives a total of
a
0
b
n
+ a
1
b
n?1
+ a
2
b
n?2
+ + a
n
b
0
···
ways to select n items from A∪B,This is precisely the value of c
n
computed above,
The expression c
n
= a
0
b
n
+a
1
b
n?1
+a
2
b +a
n
b
0
may be familiar from a signal pro-
n?2
+···
cessing course; the sequence?c
0
,c
1
,c
2
,...?is the convolution of sequences?a
0
,a
1
,a
2
,...?
and?b
0
,b
1
,b
2
,...?,
4.3 Choosing Items with Repetition
The?rst counting problem we considered asked for the number of ways to select a dozen
doughnuts when there were?ve varieties available,We can generalize this question as
follows,in how many ways can we select k items from an n-element set if we’re allowed
to pick the same item multiples times? In these terms,the doughnut problem asks in how
many ways we can select a dozen doughnuts from the set,
{chocolate,lemon-?lled,sugar,glazed,plain}
if we’re allowed to pick several doughnuts of the same variety,Let’s approach this ques-
tion from a generating functions perspective,
Suppose we choose n items (with repetition allowed) from a set containing a single
item,Then there is one way to choose zero items,one way to choose one item,one way
to choose two items,etc,Thus,the generating function for choosing n elements with
repetition from a 1-element set is,
3
1,1,1,1,...? 1 + x + x
2
+ x +←→ ···
1
=
1?x
The Convolution Rule says that the generating function for selecting items from a
union of disjoint sets is the product of the generating functions for selecting items from
each set,
1 1 1 1
=
1?x
·
1?x
···
1?x (1?x)
n
OGF for OGF for OGF for
OGF for
{a
1
} {a
2
} {a
n
}
{a
1
,a
2
,...,a
n
}
Therefore,the generating function for selecting items from a n-element set with repetition
allowed is 1/(1?x)
n
,
12 Generating Functions
Now we need to?nd the coef?cients of this generating function,We could try to use
partial fractions,but (1? x)
n
has a nasty repeated root at 1,An alternative is to use
Taylor’s Theorem,
Theorem 1 (Taylor’s Theorem),
f
(0) f
(0) f
(k)
(0)
2 3 k
f(x) = f(0) + f
(0)x + x + x + + x +
2! 3!
···
k!
···
This theorem says that the k-th coef?cient of 1/(1? x)
n
is equal to its k-th derivative
evaluated at 0 and divided by k!,And computing the k-th derivative turns out not to be
very dif?cult,Let
g(x) =
1
(1?x)
n
= (1?x)
n
Then we have,
G
(x) = n(1?x)
n?1
G
(x) = n(n + 1)(1?x)
n?2
G
(x) = n(n + 1)(n + 2)(1?x)
n?3
G
(k)
(x) = n(n + 1)···(n + k?1)(1?x)
n?k
Thus,the coef?cient of x
k
in the generating function is,
G
(k)
(0)/k! =
n(n + 1)···(n + k?1)
k!
(n + k?1)!
=
(n?1)! k!
n + k?1
=
k
Therefore,the number of ways to select k items from an n-element set with repetition
allowed is,
n + k?1
k
This makes sense,since there is a bijection between such selections and (n + k? 1)-bit
sequences with k zeroes (representing the items) and n?1 ones (separating the n different
types of item),
5 An,Impossible” Counting Problem
So far everything we’ve done with generating functions we could have done another way,
But here is an absurd counting problem— really over the top! In how many ways can we
ll a bag with n fruits subject to the following constraints?
13 Generating Functions
The number of apples must be even,
The number of bananas must be a multiple of 5,
There can be at most four oranges,
There can be at most one pear.
For example,there are 7 ways to form a bag with 6 fruits:
Apples 6 4 4 2 2 0 0
Bananas 0 0 0 0 0 5 5
Oranges 0 2 1 4 3 1 0
Pears 0 0 1 0 1 0 1
These constraints are so complicated that the problem seems hopeless! But let’s see what
generating functions reveal,
Let’s?rst construct a generating function for selecting apples,We can select a set of
0 apples in one way,a set of 1 apples in zero ways (since the number of apples must be
even),a set of 2 applies in one way,a set of 3 apples in zero ways,and so forth,So we
have,
1
4 6
A(x) = 1 + x
2
+ x + x + = ···
1?x
2
Similarly,the generating function for selecting bananas is,
1
10 15
B(x) = 1 + x
5
+ x + x +··· =
1?x
5
Now,we can select a set of 0 oranges in one way,a set of 1 orange in one ways,and so on,
However,we can not select more than four oranges,so we have the generating function,
3 4
O(x) = 1 + x + x
2
+ x + x =
1?x
5
1?x
Here we’re using the geometric sum formula,Finally,we can select only zero or one pear,
so we have,
P(x) = 1 + x
The Convolution Rule says that the generating function for selecting from among all
four kinds of fruit is,
1 1
A(x)B(x)O(x)P(x) =
1?x
5
(1 + x)
1?x
2
1?x
5
1?x
1
=
(1?x)
2
3
= 1 + 2x + 3x
2
+ 4x +···
Almost everything cancels! We’re left with 1/(1?x)
2
,which we found a power series for
earlier,the coef?cient of x
n
is simply n + 1,Thus,the number of ways to form a bag of n
fruits is just n + 1,This is consistent with the example we worked out,since there were 7
different fruit bags containing 6 fruits,Amazing!
Srini Devadas and Eric Lehman Lecture Notes
Generating Functions
Generating functions are one of the most surprising,useful,and clever inventions in
discrete math,Roughly speaking,generating functions transform problems about se-
quences into problems about functions,This is great because we’ve got piles of mathe-
matical machinery for manipulating functions,Thanks to generating functions,we can
apply all that machinery to problems about sequences,In this way,we can use generating
functions to solve all sorts of counting problems,There is a huge chunk of mathematics
concerning generating functions,so we will only get a taste of the subject,
In this lecture,we’ll put sequences in angle brackets to more clearly distinguish them
from the many other mathemtical expressions?oating around,
1 Generating Functions
The ordinary generating function for the in?nite sequence?g
0
,g
1
,g
2
,g
3
...? is the formal
power series,
3
G(x) = g
0
+ g
1
x + g
2
x
2
+ g
3
x +···
A generating function is a,formal” power series in the sense that we usually regard x
as a placeholder rather than a number,Only in rare cases will we let x be a real number
and actually evaluate a generating function,so we can largely forget about questions of
convergence,Not all generating functions are ordinary,but those are the only kind we’ll
consider here,
Throughout the lecture,we’ll indicate the correspondence between a sequence and its
generating function with a double-sided arrow as follows,
2 3
+ g
3
x?g
0
,g
1
,g
2
,g
3
,...? ←→ g
0
+ g
1
x + g
2
x +···
For example,here are some sequences and their generating functions,
3
0,0,0,0,...? ←→ 0 + 0x + 0x
2
+ 0x = 0 +···
3
1,0,0,0,...? ←→ 1 + 0x + 0x
2
+ 0x = 1 +···
3
3,2,1,0,...? ←→ 3 + 2x + 1x
2
+ 0x = 3 + 2x + x
2
+···
The pattern here is simple,the i-th term in the sequence (indexing from 0) is the coef?cient
of x
i
in the generating function,
Recall that the sum of an in?nite geometric series is,
1
3
1 + z + z
2
+ z =+···
1?z
2 Generating Functions
This equation does not hold when z ≥ 1,but once again we won’t worry about conver-||
gence issues,This formula gives closed-form generating functions for a whole range of
sequences,For example,
1
,1,1,1,...? 1 + x + x
2
+ x =?1 ←→
3
+···
1?x
1
4
=?1,?1,1,?1,...x
3
+ x←→ 1?x + x
2
···
1 + x
1
3 3
1,a,a
2
,a,...? 1 + ax + a
2
x
2
+ a x =
1?ax
←→
3
+···
1
4
+ x
6
1,0,1,0,1,0,...? 1 + x
2
+ x =
1?x
2
←→ +···
2 Operations on Generating Functions
The magic of generating functions is that we can carry out all sorts of manipulations on
sequences by performing mathematical operations on their associated generating func-
tions,Let’s experiment with various operations and characterize their effects in terms of
sequences,
2.1 Scaling
Multiplying a generating function by a constant scales every term in the associated se-
quence by the same constant,For example,we noted above that,
1
4 6
1,0,1,0,1,0,...? ←→ 1 + x
2
+ x + x =
1?x
2
+···
Multiplying the generating function by 2 gives
2
= 2 + 2x
2
+ 2x
4
+ 2x
6
1?x
2
+···
which generates the sequence,
,0,2,0,2,0,...2
Rule 1 (Scaling Rule),If
x),?f
0
,f
1
,f
2
,...? ←→ F(
then
cf
0
,cf
1
,cf
2
,F(x)....? ←→ c·
Generating Functions 3
Proof,
cf
0
,cf
1
,cf
2
,...? cf
0
+ cf
1
x + cf
2
x
2
←→ +· · ·
= c· (f
0
+ f
1
x + f
2
x
2
+· · · )
= cF(x)
2.2 Addition
Adding generating functions corresponds to adding the two sequences term by term,For
example,adding two of our earlier examples gives,
1
1,1,1,1,1,1,..,? ←→
1? x
1
+? 1,? 1,1,? 1,1,? 1,..,? ←→
1 + x
1 1
2,0,2,0,2,0,..,+ ←→
1? x 1 + x
We’ve now derived two different expressions that both generate the sequence? 2,0,2,0,...?,
Not surprisingly,they turn out to be equal,
1 1 (1 + x) + (1? x) 2
+ = =
1? x 1 + x (1? x)(1 + x) 1? x
2
Rule 2 (Addition Rule),If
f
0
,f
1
,f
2
,...? ←→ F(x),and
g
0
,g
1
,g
2
,...? ←→ G(x),
then
f
0
+ g
0
,f
1
+ g
1
,f
2
+ g
2
,...? ←→ F(x) + G(x),
Proof,
∞
f
0
+ g
0
,f
1
+ g
1
,f
2
+ g
2
,...? ←→ (f
n
+ g
n
)x
n
n=0
∞
∞
= f
n
x
n
+ g
n
x
n
n=0 n=0
= F(x) + G(x)
4 Generating Functions
2.3 Right Shifting
Let’s start over again with a simple sequence and its generating function,
1
,1,1,1,...? ←→?1
1?x
Now let’s right-shift the sequence by adding k leading zeros,
k+1 k+2 k+3
0,0,...,0,1,1,1,...? x
k
+ x + x + x
←→ +···
k zeroes
k 3
= x ·(1 + x + x
2
+ x +···)
k
x
=
1?x
Evidently,adding k leading zeros to the sequence corresponds to multiplying the gener-
ating function by x
k
,This holds true in general,
Rule 3 (Right-Shift Rule),If?f
0
,f
1
,f
2
,...? ←→ F(x),then,
0,0,...,0,f
0
,f
1
,f
2
,...? ←→ x
k
F(x)
·
k zeroes
Proof,
k zeroes
f
0
x
k
+ f
1
x
k+1
+ f
2
x
k+2
0,0,...,0,f
0
,f
1
,f
2
,... ←→ +···
3
= x
k
·(f
0
+ f
1
x + f
2
x
2
+ f
3
x +···)
k
= x F(x)·
2.4 Differentiation
What happens if we take the derivative of a generating function? As an example,let’s
differentiate the now-familiar generating function for an in?nite sequence of 1’s,
d 1d
(1 + x + x
2
+ x
3
+ x
4
=
dx
+···)
dx 1?x
1
3
1 + 2x + 3x
2
+ 4x =
2
+···
(1?x)
1
1,2,3,4,...? ←→
(1?x)
2
We found a generating function for the sequence?1,2,3,4,...?!
In general,differentiating a generating function has two effects on the corresponding
sequence,each term is multiplied by its index and the entire sequence is shifted left one
place,
5 Generating Functions
Rule 4 (Derivative Rule),If
f
0
,f
1
,f
2
,f
3
,...? ←→ F(x),
then
(x).?f
1
,2f
2
,3f
3
,...? ←→ F
Proof,
f
1
,2f
2
,3f
3
,...? = f
1
+ 2f
2
x + 3f
3
x
2
+ ···
d
(f
0
+ f
1
x + f
2
x
2
+ f
3
x
3
+=
dx
···)
d
= F(x)
dx
The Derivative Rule is very useful,In fact,there is frequent,independent need for
each of differentiation’s two effects,multiplying terms by their index and left-shifting one
place,Typically,we want just one effect and must somehow cancel out the other,For ex-
ample,let’s try to?nd the generating function for the sequence of squares,?0,1,4,9,16,...?,
If we could start with the sequence?1,1,1,1,...?and multiply each term by its index two
times,then we’d have the desired result,
0,1 1,2 2,3 3,...? =?0,1,4,9,...0 · · · ·
A challenge is that differentiation not only multiplies each term by its index,but also
shifts the whole sequence left one place,However,the Right-Shift Rule 3 tells how to
cancel out this unwanted left-shift,multiply the generating function by x,
Our procedure,therefore,is to begin with the generating function for?1,1,1,1,...?,
differentiate,multiply by x,and then differentiate and multiply by x once more,
1
1,1,1,1,...? ←→
1?x
d 1 1
=?1,2,3,4,...? ←→
dx 1?x (1?x)
2
1 x
=?0,1,2,3,...? ←→ x·
(1?x)
2
(1?x)
2
d x 1 + x
=?1,4,9,16,...? ←→
dx (1?x)
2
(1?x)
3
1 + x x(1 + x)
=?0,1,4,9,...? ←→ x·
(1?x)
3
(1?x)
3
Thus,the generating function for squares is,
x(1 + x)
(1?x)
3
6 Generating Functions
3 The Fibonacci Sequence
Sometimes we can?nd nice generating functions for more complicated sequences,For
example,here is a generating function for the Fibonacci numbers,
x
0,1,1,2,3,5,8,13,21,...? ←→
1?x?x
2
The Fibonacci numbers are a fairly nasty bunch,but the generating function is simple!
We’re going to derive this generating function and then use it to?nd a closed form for
the n-Fibonacci number,Of course,we already have a closed form for Fibonacci numbers,
obtained from the cookbook procedure for solving linear recurrences,But there are a
couple reasons to cover the same ground again,First,we’ll gain some insight into why
the cookbook method for linear recurrences works,And,second,the techniques we’ll use
are applicable to a large class of recurrence equations,including some that we have no
other way to tackle,
3.1 Finding a Generating Function
Let’s begin by recalling the de?nition of the Fibonacci numbers,
f
0
= 0
f
1
= 1
f
n
= f
n?1
+ f
n?2
(for n≥ 2)
We can expand the?nal clause into an in?nite sequence of equations,Thus,the Fibonacci
numbers are de?ned by,
f
0
=0
f
1
=1
f
2
=f
1
+ f
0
f
3
=f
2
+ f
1
f
4
=f
3
+ f
2
,
,
,
Now the overall plan is to de?ne a function F(x) that generates the sequence on the left
side of the equality symbols,which are the Fibonacci numbers,Then we derive a function
that generates the sequence on the right side,Finally,we equate the two and solve for
F(x),Let’s try this,First,we de?ne,
3
+ f
4
x
4
F(x) = f
0
+ f
1
x + f
2
x
2
+ f
3
x + ···
7 Generating Functions
Now we need to derive a generating function for the sequence,
,1,f
1
+ f
0
,f
2
+ f
1
,f
3
+ f
2
,... 0
One approach is to break this into a sum of three sequences for which we know generating
functions and then apply the Addition Rule,
0, 1,0,0,0,x? ,.,? ←→
0,f
0
,f
1
,f
2
,f
3
, xF(x)? ,.,? ←→
+ ? 0,0,f
0
,f
1
,f
2
,..,? ←→ x
2
F(x)
0,1 + f
0
,f
1
+ f
0
,f
2
+ f
1
,f
3
+ f
2
,..,? ←→ x + xF(x) + x
2
F(x)
This sequence is almost identical to the right sides of the Fibonacci equations,The one
blemish is that the second term is 1 + f
0
instead of simply 1,However,this amounts to
nothing,since f
0
= 0 anyway,
Now if we equate F(x) with the new function x+xF(x)+x
2
F(x),then we’re implicitly
writing down all of the equations that de?ne the Fibonacci numbers in one fell swoop,
F(x) = f
0
+ f
1
x + f
2
x
2
+ f
3
x
3
+ f
4
x
4
+,.,
x + xF(x) + x
2
F(x) = 0 + (1 + f
0
) x + (f
1
+ f
0
) x
2
+ (f
2
+ f
1
) x
3
+ (f
3
+ f
2
) x
4
+· · ·
Solving for F(x) gives the generating function for the Fibonacci sequence,
F(x) = x + xF(x) + x
2
F(x)
x
F(x) =
1? x? x
2
Sure enough,this is the simple generating function we claimed at the outset!
3.2 Finding a Closed Form
Why should one care about the generating function for a sequence? There are several
answers,but here is one,if we can?nd a generating function for a sequence,then we can
often?nd a closed form for the n-th coef?cient— which can be pretty useful! For example,
a closed form for the coef?cient of x
n
in the power series for x/(1? x? x
2
) would be an
explicit formula for the n-th Fibonacci number,
So our next task is to extract coef?cients from a generating function,There are sev-
eral approaches,For a generating function that is a ratio of polynomials,we can use the
method of partial fractions,which you learned in calculus,Just as the terms in a par-
tial fractions expansion are easier to integrate,the coef?cients of those terms are easy to
compute,
Let’s try this approach with the generating function for Fibonacci numbers,First,we
factor the denominator,
1? x? x
2
= (1? α
1
x)(1? α
2
x)
8 Generating Functions
1 1
where α
1
=
2
(1 +
√
5) and α
2
=
2
(1?
√
5),Next,we?nd A
1
and A
2
which satisfy,
x A
1
A
2
= +
1?x?x
2
1?α
1
x 1?α
2
x
We do this by plugging in various values of x to generate linear equations in A
1
and A
2
,
We can then?nd A
1
and A
2
by solving a linear system,This gives,
1 1
A
1
= =
α
1
α
2
√
5
1?1
A
2
= =
α
1
α
2
√
5
Substituting into the equation above gives the partial fractions expansion of F(x),
x 1 1 1
=
1?x?x
2
√
5
1?α
1
x
1?α
2
x
Each term in the partial fractions expansion has a simple power series given by the geo-
metric sum formula,
1
2
= 1 + α
1
x + α
2
1
x
1?α
1
x
+···
1
2
= 1 + α
2
x + α
2
2
x
1?α
2
x
+···
Substituting in these series gives a power series for the generating function,
1 1 1
F(x) = √
5
1?α
1
x
1?α
2
x
1
2
2
= √
5
(1 + α
1
x + α
2
2
x
1
x +···)?(1 + α
2
x + α
2
+···)
α
n
1
α
n
f
n
= √
5
2
1?
√
5
n n
1 1 +
√
5
= √
5
2
2
This is the same scary formula for the n-th Fibonacci number that we found using the
method for solving linear recurrences,And this alternate approach sheds some light on
that method,In particular,the strange rules involving repeated roots of the characteristic
equation are re?ections of the rules for?nding a partial fractions expansion!
4 Counting with Generating Functions
Generating functions are particularly useful for solving counting problems,In particular,
problems involving choosing items from a set often lead to nice generating functions,
When generating functions are used in this way,the coef?cient of x
n
is the number of
ways to choose n items,
Generating Functions 9
4.1 Choosing Distinct Items from a Set
The generating function for binomial coef?cients follows directly from the Binomial The-
orem,
k k k k k k k
2
k
k
,,,...,,0,0,0,..,+ x + x + x
0 1 2 k
←→
0 1 2
+···
k
= (1 + x)
k
Thus,the coef?cient of x
n
in (1 + x)
k
is the number of ways to choose n distinct items
k
from a k-element set,For example,the coef?cient of x
2
is,the number of ways to
2
choose 2 items from a k-element set,Similarly,the coef?cient of x
k+1
is the number of
ways to choose k + 1 items from a k-element set,which is zero,
4.2 Building Generating Functions that Count
Often we can translate the description of a counting problem directly into a generating
function for the solution,For example,we could?gure out that (1 + x)
k
generates the
number of ways to select n distinct items from a k-element subset without resorting to
the Binomial Theorem or even fussing with binomial coef?cients!
Here is how,First,consider a single-element set {a
1
},The generating function for the
number of ways to choose n elements from this set is simply 1 + x,we have 1 way to
choose zero elements,1 way to choose one element,and 0 ways to choose more than one
element,Similarly,the number of ways to choose n elements from the set {a
2
} is also
given by the generating function 1 + x,The fact that the elements differ in the two cases
is irrelevant,
Now here is the the main trick,the generating function for choosing elements from a union of
disjoint sets is the product of the generating functions for choosing from each set,We’ll justify this
in a moment,but let’s?rst look at an example,According to this principle,the generating
function for the number of ways to choose n elements from the {a
1
,a
2
}is,
(1 + x) (1 + x) = (1 + x)
2
= 1 + 2x + x
2
·
OGF for OGF for OGF for
{a
1
,a
2
}{a
1
} {a
2
}
Sure enough,for the set {a
1
,a
2
},we have 1 way to choose zero elements,2 ways to choose
one element,1 way to choose two elements,and 0 ways to choose more than two ele-
ments,
Repeated application of this rule gives the generating function for choosing n items
from a k-element set {a
1
,a
2
,...,a
k
},
(1 + x) (1 + x) (1 + x) = (1 + x)
k
·
···
OGF for OGF for OGF for OGF for
{a
1
,a
2
,...,a
k
}{a
1
} {a
2
} {a
k
}
10 Generating Functions
This is the same generating function that we obtained by using the Binomial Theorem,
But this time around we translated directly from the counting problem to the generating
function,
We can extend these ideas to a general principle,
Rule 5 (Convolution Rule),Let A(x) be the generating function for selecting items from set A,
and let B(x) be the generating function for selecting items from set B,If A and B are disjoint,
then the generating function for selecting items from the union A∪Bis the product A(x)·B(x),
This rule is rather ambiguous,what exactly are the rules governing the selection of
items from a set? Remarkably,the Convolution Rule remains valid under many inter-
pretations of selection,For example,we could insist that distinct items be selected or
we might allow the same item to be picked a limited number of times or any number of
times,Informally,the only restrictions are that (1) the order in which items are selected
is disregarded and (2) restrictions on the selection of items from sets Aand Balso apply
in selecting items from A∪B,(Formally,there must be a bijection between n-element
selections from A∪Band ordered pairs of selections from Aand B containing a total of
n elements.)
Proof,De?ne,
∞ ∞ ∞
A(x) = a
n
x
n
,B(x) = b
n
x
n
,C(x) = A( B(x) = c
n
x
n
.x)·
n=0 n=0 n=0
Let’s?rst evaluate the product A(x) B(x) and express the coef?cient c
n
in terms of the ·
a and b coef?cients,We can tabulate all of the terms in this product in a table,
b
0
x
0
b
1
x
1
b
2
x
2
b
3
x
3
..,
a
0
x
0
a
0
b
0
x
0
a
0
b
1
x
1
a
0
b
2
x
2
a
0
b
3
x
3
..,
a
1
x
1
a
1
b
0
x
1
a
1
b
1
x
2
a
1
b
2
x
3
..,
a
2
x
2
a
2
b
0
x
2
a
2
b
1
x
3
..,
a
3
x
3
a
3
b
0
x
3
..,
,
,
.,.,
Notice that all terms involving the same power of x lie on a /-sloped diagonal,Collecting
these terms together,we?nd that the coef?cient of x
n
in the product is,
c
n
= a
0
b
n
+ a
1
b
n?1
+ a
2
b + a
n
b
0n?2
+···
Generating Functions 11
Now we must show that this is also the number of ways to select n items from A∪B,
In general,we can select a total of n items from A ∪ B by choosing j items from A and
n?j items from B,where j is any number from 0 to n,This can be done in a
j
b
n?j
ways,
Summing over all the possible values of j gives a total of
a
0
b
n
+ a
1
b
n?1
+ a
2
b
n?2
+ + a
n
b
0
···
ways to select n items from A∪B,This is precisely the value of c
n
computed above,
The expression c
n
= a
0
b
n
+a
1
b
n?1
+a
2
b +a
n
b
0
may be familiar from a signal pro-
n?2
+···
cessing course; the sequence?c
0
,c
1
,c
2
,...?is the convolution of sequences?a
0
,a
1
,a
2
,...?
and?b
0
,b
1
,b
2
,...?,
4.3 Choosing Items with Repetition
The?rst counting problem we considered asked for the number of ways to select a dozen
doughnuts when there were?ve varieties available,We can generalize this question as
follows,in how many ways can we select k items from an n-element set if we’re allowed
to pick the same item multiples times? In these terms,the doughnut problem asks in how
many ways we can select a dozen doughnuts from the set,
{chocolate,lemon-?lled,sugar,glazed,plain}
if we’re allowed to pick several doughnuts of the same variety,Let’s approach this ques-
tion from a generating functions perspective,
Suppose we choose n items (with repetition allowed) from a set containing a single
item,Then there is one way to choose zero items,one way to choose one item,one way
to choose two items,etc,Thus,the generating function for choosing n elements with
repetition from a 1-element set is,
3
1,1,1,1,...? 1 + x + x
2
+ x +←→ ···
1
=
1?x
The Convolution Rule says that the generating function for selecting items from a
union of disjoint sets is the product of the generating functions for selecting items from
each set,
1 1 1 1
=
1?x
·
1?x
···
1?x (1?x)
n
OGF for OGF for OGF for
OGF for
{a
1
} {a
2
} {a
n
}
{a
1
,a
2
,...,a
n
}
Therefore,the generating function for selecting items from a n-element set with repetition
allowed is 1/(1?x)
n
,
12 Generating Functions
Now we need to?nd the coef?cients of this generating function,We could try to use
partial fractions,but (1? x)
n
has a nasty repeated root at 1,An alternative is to use
Taylor’s Theorem,
Theorem 1 (Taylor’s Theorem),
f
(0) f
(0) f
(k)
(0)
2 3 k
f(x) = f(0) + f
(0)x + x + x + + x +
2! 3!
···
k!
···
This theorem says that the k-th coef?cient of 1/(1? x)
n
is equal to its k-th derivative
evaluated at 0 and divided by k!,And computing the k-th derivative turns out not to be
very dif?cult,Let
g(x) =
1
(1?x)
n
= (1?x)
n
Then we have,
G
(x) = n(1?x)
n?1
G
(x) = n(n + 1)(1?x)
n?2
G
(x) = n(n + 1)(n + 2)(1?x)
n?3
G
(k)
(x) = n(n + 1)···(n + k?1)(1?x)
n?k
Thus,the coef?cient of x
k
in the generating function is,
G
(k)
(0)/k! =
n(n + 1)···(n + k?1)
k!
(n + k?1)!
=
(n?1)! k!
n + k?1
=
k
Therefore,the number of ways to select k items from an n-element set with repetition
allowed is,
n + k?1
k
This makes sense,since there is a bijection between such selections and (n + k? 1)-bit
sequences with k zeroes (representing the items) and n?1 ones (separating the n different
types of item),
5 An,Impossible” Counting Problem
So far everything we’ve done with generating functions we could have done another way,
But here is an absurd counting problem— really over the top! In how many ways can we
ll a bag with n fruits subject to the following constraints?
13 Generating Functions
The number of apples must be even,
The number of bananas must be a multiple of 5,
There can be at most four oranges,
There can be at most one pear.
For example,there are 7 ways to form a bag with 6 fruits:
Apples 6 4 4 2 2 0 0
Bananas 0 0 0 0 0 5 5
Oranges 0 2 1 4 3 1 0
Pears 0 0 1 0 1 0 1
These constraints are so complicated that the problem seems hopeless! But let’s see what
generating functions reveal,
Let’s?rst construct a generating function for selecting apples,We can select a set of
0 apples in one way,a set of 1 apples in zero ways (since the number of apples must be
even),a set of 2 applies in one way,a set of 3 apples in zero ways,and so forth,So we
have,
1
4 6
A(x) = 1 + x
2
+ x + x + = ···
1?x
2
Similarly,the generating function for selecting bananas is,
1
10 15
B(x) = 1 + x
5
+ x + x +··· =
1?x
5
Now,we can select a set of 0 oranges in one way,a set of 1 orange in one ways,and so on,
However,we can not select more than four oranges,so we have the generating function,
3 4
O(x) = 1 + x + x
2
+ x + x =
1?x
5
1?x
Here we’re using the geometric sum formula,Finally,we can select only zero or one pear,
so we have,
P(x) = 1 + x
The Convolution Rule says that the generating function for selecting from among all
four kinds of fruit is,
1 1
A(x)B(x)O(x)P(x) =
1?x
5
(1 + x)
1?x
2
1?x
5
1?x
1
=
(1?x)
2
3
= 1 + 2x + 3x
2
+ 4x +···
Almost everything cancels! We’re left with 1/(1?x)
2
,which we found a power series for
earlier,the coef?cient of x
n
is simply n + 1,Thus,the number of ways to form a bag of n
fruits is just n + 1,This is consistent with the example we worked out,since there were 7
different fruit bags containing 6 fruits,Amazing!
