Alexandre Zotine MATH3U03 Course Notes
Lecture 21 (Friday, November 1)
(§5.3 in book)
Example 1. Find the number of (ordered) ten letter words from the alphabet {a, b, c, d}
that satisfying the same four properties.
Solution. With the order in mind, one might think we just multiply 24 by 10!. However, we
have some problems. The as are indistinguishable, so we need to divide by the ways to order
the as, and the bs... etc. Luckily, this isn’t actually that big of a problem! The coefficients
of our generating function just change slightly. Instead we need:
(i) (1 + x4 /4!) for the as.
(ii) (1 + x2 /2! + x4 /4! + x6 /6! + · · · ) for the bs.
(iii) (x3 /3! + x4 /4! + x5 /5! + x6 /6! + · · · ) for the cs.
(iv) (1 + x + x2 /2! + x3 /3! + x4 /4! + x5 /5!) for the ds.
The only problem is, what are the generating functions for these expressions? △
Exponential Generating Functions
In situations like the example above, it is useful to keep track of the order of things. For
this, the exponential power series will play the same role as the geometric series.
Proposition 2. We have that
X xn x2 x 3 x4
(i) ex = =1+x+ + + + ··· ,
n≥0
n! 2! 3! 4!
2n+1
X
n x x3 x5 x7
(ii) sin(x) = (−1) =x− + − + ··· ,
n≥0
(2n + 1)! 3! 5! 7!
X x2n x2 x4 x6
(iii) cos(x) = (−1)n =1− + − + ··· ,
n≥0
(2n)! 2! 4! 6!
X x2n+1 x3 x5 x7
(iv) sinh(x) = =x+ + + + ··· ,
n≥0
(2n + 1)! 3! 5! 7!
X x2n x 2 x4 x6
(v) cosh(x) = =1+ + + + ··· .
n≥0
(2n)! 2! 4! 6!
To finish the example, we need to find the coefficient of x10 in
10!(1 + x4 /4!) cosh(x)(ex − 1 − x − x2 /2)(1 + x + x2 /2! + x3 /3! + x4 /4! + x5 /5!),
which Wolfram Alpha gives as 44933.
1
Alexandre Zotine MATH3U03 Course Notes
Computing Formulas/Identities
Example 3. Recall that the generating function for the Fibonacci numbers fn (starting
f0 = 0, f1 = 1) is
x
f (x) = .
1 − x − x2
Using this generating series, we can find an explicit formula for the n-th Fibonacci
√ number.
2 −1
The denominator factors as 1 − x − x = (1 − φx)(1 + φ x), where φ = (1 + 5)/2 is the
Golden ratio. Hence we have a partial fraction decomposition
A B
f= −1
+ .
(1 + φ x) (1 − φx)
We first see that A + B = 0, so A = −B. Then we can plug in x = −φ to get that
B(1 + φ2 ) = −φ. Solving yields A = √15 = −B. So we have
1 1 1
f (x) = √ −
5 (1 − φx) (1 + φ−1 x)
1 X n
=√ (φ − (−φ)−n )xn .
5 n≥0
We conclude that fn = √1 (φn
5
− (−φ)−n ). △
Example 4. Prove that f0 + f1 + · · · + fn = fn+2 − 1 for all n ∈ N.
Solution. We saw this in the first lecture. Let’s prove it using generating functions. Here’s
another nice trick: using the multiplication rule, we have that
n
!
1 X X
f (x) · = f k · 1 xn
1 − x n≥0 k=0
1
= f0 + (f0 + f1 )x + (f0 + f1 + f2 )x2 + · · · . = .
(1 − x − x2 )(1 − x)
So multiplying by the geometric series gives us a new sequence which is the sum of the first
k terms of our sequence. This is handy, because now we’ve encoded the left side of the
equation. On the other hand,
X f (x) − f1 x − f0 1
(fn+2 − 1)xn = −
n≥0
x2 1−x
1 1 1
= 2
− −
x(1 − x − x ) x 1 − x
(1 − x) − (1 − x)(1 − x − x2 ) − x(1 − x − x2 )
=
x(1 − x)(1 − x − x2 )
1
= .
(1 − x − x2 )(1 − x)
Since both of these are equal, their coefficients are equal, so the identity holds for all n ∈
N. △
2
Alexandre Zotine MATH3U03 Course Notes
We can also produce a generating function for the Catalan numbers. To do so, we need
to generalize binomial coefficients.
Definition 5. Given an integer k ∈ N, the falling factorial is
k
Y
k
x = x(x − 1)(x − 2) · · · (x − k + 1) = (x − i + 1) ∈ Z[x].
i=1
The binomial coefficient
xk
x
=
k k!
x
is a polynomial of degree k in Z[x]. If k < 0, we set k
= 0.
Importantly, we can plug in values into x. For instance,
−1/2 −1/2 −1/2 −1/2
= −1/2, = 3/8, = −5/16, = 35/128, · · ·
1 2 3 4
i i i i
= i, = (−1 − i)/2, = 1/2 + i/6, = −5/12, · · ·
1 2 3 4
which of course makes perfect sense, because obviously when you want to pick 4 objects out
of i options, there are −5/12 ways to do that.
