Lecture 8: Counting

?
Nitin Saxena

IIT Kanpur

1 Generating functions (Fibonacci)

1
We had obtained φ(t) = i≥0 Fi ti = 1−t−t
P
2 .

We can factorize the polynomial, 1 − t − t2 = (1 − αt)(1 − βt), where α, β ∈ C.

√ √
1+ 5 1− 5
Exercise 1. Show that α = 2 ,β = 2 .

We can simplify the formula a bit more,

1 c1 c2
φ(t) = 2
= + = c1 (1 + αt + α2 t2 + · · · ) + c2 (1 + βt + β 2 t2 + · · · ) .
1−t−t 1 − αt 1 − βt

We got the second equality by putting c1 = √1 α and c2 = − √15 β. The final expression gives us an explicit
5
formula for the Fibonacci sequence,
1
Fn = √ (αn+1 − β n+1 ) .
5
This is actually a very strong method and can be used for solving linear recurrences of the kind, Sn =
a1 Sn−1 + · · · + ak Sn−k . Here k, a1 , a2 , · · · , ak are constants. Suppose φ(t) is the recurrence for Sn , then by
the above method,

b1 + b2 t + · · · + bk tk−1 c1 ck
φ(t) = = + ··· + .
1 − a1 t − a2 t2 − · · · − ak tk 1 − α1 t 1 − αk t
Where α1 , · · · , αk are the roots (assumed distinct) of polynomial xk − a1 xk−1 − · · · − ak = 0 (replace t
by x1 ). This is known as the characteristic polynomial of the recurrence.

Exercise 2. How are the coefficients b1 , · · · , bk or c1 , · · · , ck determined?

Initial conditions.

So we get Sn = c1 α1n + · · · + ck αkn .

Note 1. For a linear recurrence if Fn and Gn are solutions then their linear combinations aFn + bGn are
also solutions. For a k term recurrence, the possible solutions are α1n , · · · , αkn and their linear combinations
(where α1 , · · · , αk are roots of the characteristic polynomial). The coefficients of the linear combination are
fixed by the initial conditions.

Exercise 3. Does every polynomial over C has a complex root?

Fundamental theorem of algebra.

Exercise 4. What happens when the characteristic polynomial has repeated roots?
Use the power series for (1 − αt)−d .

?
Edited from Rajat Mittal’s notes.
2 Exponential generating function
What do we do when the recurrence is non-linear ? We will now see some related methods.
A permutation is called an involution if all cycles1 in the permutation are of length 1 or 2. We are
interested in counting the total number of involutions of {1, 2, · · · , n}, call that I(n). Eg. I(0) = I(1) = 1,
I(2) = 2.
There can be two cases.
1. The number n maps to itself. This case will give rise to I(n − 1) involutions.
2. The number n maps to another number i. There are n − 1 choices of i and then we can pick an involution
for remaining n − 2 numbers in I(n − 2) ways.
By this argument, we get a simple recurrence,

I(n) = I(n − 1) + (n − 1)I(n − 2) .

Exercise 5. Why is this not a linear recurrence?

Since the coefficient of I(n − 2) is not a constant, we cannot apply the usual approach of generating
functions. Even without getting an explicit formula for I(n), the recurrence can give us some information
about the quantity.
√
Theorem 1. For n ≥ 2, the number I(n) is even and greater than n! .
Proof. Both the statements can be proven using induction.
Exercise 6. What will be the base case and the induction step ?
n, for n ≥ 1. n−1≥ Check that I(2), I(3) are both even. Verify that 1 +
√ √

In the case of involutions, the regular generating function will not be of much help. We define exponential
generating function for the sequence I(n) to be,
X I(k)tk
θ(t) := .
k!
k≥0

Exercise 7. Why is it called an exponential generating function?

Put I(k) = 1, for all k, and we get the series for the exponential function et .

Note 2. It is merely the generating function of I(k)/k!.

We can actually come up with a closed form solution for the exponential generating function of involutions.
We will differentiate the function θ(t),

d X I(k)tk−1
θ(t) = (formal differentiation) (1)
dt (k − 1)!
k≥1
X I(k − 1)tk−1 X (k − 1) · I(k − 2) · tk−1
= + (recurrence relation) (2)
(k − 1)! (k − 1)!
k≥1 k≥1
X I(k − 2)tk−2
= θ(t) + t (second term’s first entry is zero) (3)
(k − 2)!
k≥2

= θ(t) + tθ(t) . (4)

1
Every permutation can be decomposed into cycles. Eg. (12)(3)(45)(67)(8) is an involution. Permutation (123) is
not an involution.

2
 This transforms into the differential equation,
d
log θ(t) = 1 + t .
dt
We can solve this, as,
t2
θ(t) = et+ 2 +c .
Comparing the constant coefficient, we get c = 0 (since I(0) = 1). Thus,
t2
θ(t) = et+ 2 .

Note 3. Again we should notice that the power series we are considering are not shown to be well behaved
(convergence etc.). But there is a justification for being able to differentiate and do other formal operations
on them; the details are outside the scope of this course.

References
1. P. J. Cameron. Combinatorics: Topics, Techniques and Algorithms. Cambridge University Press, 1994.
2. K. H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill, 1999.