MTH00050 – Combinatorial Mathematics

Lecture 5: Generating functions

Lecturer: Bùi Văn Thạch

TA: Trần Thị Thảo Nhi
Lab instructors: Trần Thị Thảo Nhi, Nguyễn Ngọc Toàn
{bvthach,tttnhi,nntoan}@[Link]
1
 (Expected) Schedule 2025-2026
No. Date Location Topic No. Date Location Topic
6 07/11 F106 Graphs (Part I)
1 03/10 F106 Introduction, Sets
7 14/11 F106 Graphs (Part II)
2 10/10 F106 Off for FIT-30 anniversary 8 21/11 F106 Path problems
3 17/10 F106 General counting methods 24-29/11 Mid-term test
Inclusion-exclusion 9 05/12 F106 Tree problems
4 24/10 F106 principle - Recurrence 10 12/12 F106 Network flows (Part I)
relations
11 19/12 F106 Network flows (Part II)
5 31/10 F106 Generating functions
12 26/12 F106 Review

2
Goals
1. To help students understand and be able to use generating
functions to analyze the complexity of an algorithm.

3
Fibonacci in Animal Breeding Patterns and Hanoi’s Tower
How to solve these recurrences without using techniques like the master theorem?
Rabbit pairs
Fibonacci’s rabbit Time (Fibonacci
breeding theory (months) sequence)

1 1
⋆
⋆ 2 2
⋆ ⋆ 3 3
4 5
+3 5 8
*offspring not breeding
(etc.) (etc.)
until two months of age
#rabbits at the 𝑛th month: Number of moves:
𝑇 𝑛 =𝑇 𝑛−1 +𝑇 𝑛−2 𝑇 𝑛 = 2𝑇 𝑛 − 1 + 1
4
Outline

1. Generating functions for basic sequences

2. Operations on generating functions

3. Counting

4. Solving recurrences

5
Outline

1. Generating functions for basic sequences

2. Operations on generating functions

3. Counting

4. Solving recurrences

6
Abstract

a sequence of numbers a function

a polynomial

• Through this mapping, we can apply our techniques for

manipulating functions.

7
Ordinary Generating Functions

• Let 𝑔𝑛 for 𝑛 = 0,1, …, be a sequence, denoted as

g 0 , g1 , g 2 , … … .

• The ordinary generating function is:

∞

𝐺 𝑥 = ෍ 𝑔𝑖 𝑥 𝑖 = 𝑔0 + 𝑔1 𝑥 + 𝑔2 𝑥 2 + ⋯
𝑖=0

• We use a double sided arrow to indicate the correspondence.

g 0 , g1 , g 2 , … … ⟺ 𝑔0 + 𝑔1 𝑥 + 𝑔2 𝑥 2 + ⋯

8
Simple Examples
• 0,0,0,0, … ⟺ 0 + 0𝑥 + 0𝑥 2 + 0𝑥 3 + ⋯ = 0
• 1,0,0,0, … ⟺ 1 + 0𝑥 + 0𝑥 2 + 0𝑥 3 + ⋯ = 1

The pattern here is simple:

the 𝑖th term in the sequence (indexing from 0) is the
coefficient of 𝑥𝑖 in the generating function.

9
Geometric Series
• 𝐺𝑛 𝑥 = 1 + 𝑥 + 𝑥 2 + ⋯ + 𝑥 𝑛 + ⋯
• What is the closed form expression of 𝐺𝑛 𝑥 ?

𝐺𝑛 𝑥 = 1 + 𝑥 + 𝑥 2 + ⋯ + 𝑥 𝑛 + ⋯
−
𝑥𝐺𝑛 𝑥 = 𝑥 + 𝑥 2 + ⋯ + 𝑥 𝑛 + 𝑥 𝑛+1 + ⋯

𝐺𝑛 𝑥 − 𝑥𝐺𝑛 𝑥 = 1
1
𝐺𝑛 𝑥 =
1−𝑥
10
More Examples
2 3 1
• 1,1,1,1, … ⟺ 1 + 1𝑥 + 1𝑥 + 1𝑥 + ⋯ =
1−𝑥
2 3 1
• 1, −1,1, −1, … ⟺ 1 − 1𝑥 + 1𝑥 − 1𝑥 + ⋯ =
1+𝑥
2 3 2 2 3 3 1
• 1, 𝑎, 𝑎 , 𝑎 , … ⟺ 1 + 𝑎𝑥 + 𝑎 𝑥 + 𝑎 𝑥 + ⋯ =
1−𝑎𝑥
2 3 1
• 1,0,1,0, … ⟺ 1 + 0𝑥 + 1𝑥 + 0𝑥 + ⋯ =
1−𝑥 2

These are all closed form generating functions.

11
Outline

1. Generating functions for basic sequences

2. Operations on generating functions

3. Counting

4. Solving recurrences

12
 manipulations on sequences manipulations on functions

• There are a few basic operations we’ll learn.

– Scaling
– Addition
– Right shift
– Differentiation
– Product
• We can use these operations to get new sequences from known
sequences, and new generating functions from known generating
functions.
13
Scaling
Multiplying a generating function by a constant
➔ scales every term in the associated sequence by the same constant.
1
1,0,1,0, … ⟺ 1 + 0𝑥 + 1𝑥 2 + 0𝑥 3 +⋯=
1 − 𝑥2
Multiply the generating function by 2 gives
2 2 3 4
2
= 2 + 0𝑥 + 2𝑥 + 0𝑥 + 2𝑥 +⋯
1−𝑥

which yields the sequence: 2,0,2,0, …

14
Addition
Adding generating functions corresponds to adding sequences term by term.

1
1,1,1,1,1,1, … ⟺
+ 1−𝑥
1
1, −1,1, −1,1, −1, … ⟺
1+𝑥
1 1
2,0,2,0,2,0, … ⟺ +
1−𝑥 1+𝑥
2
The same result as in the previous slide: =
1 − 𝑥2
15
Right shift
1
1,1,1,1, … ⟺ 1 + 1𝑥 + 1𝑥 2 + 1𝑥 3 +⋯=
1−𝑥
How to generate the sequence 0,0, … , 0,1,1,1,1, … ?

𝑘 zeros
0,0, … , 0,1,1,1,1, … ⟺ 𝑥 𝑘 + 𝑥 𝑘+1 + 𝑥 𝑘+2 + ⋯
𝑘 zeros = 𝑥𝑘 1 + 𝑥 + 𝑥2 + ⋯
𝑥𝑘
=
1−𝑥
Adding 𝑘 zeros ⟺ multiplying 𝑥𝑘 on the generating function.
16
Differentiation (1/3)
How to generate the sequence 1,2,3,4,5, … ?

The generating function is 1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 + 5𝑥 4 + ⋯

How to obtain a closed form of this function?

𝑑 2 3
𝑑 1
1+𝑥+𝑥 +𝑥 +⋯ ⟺
𝑑𝑥 𝑑𝑥 1 − 𝑥
2 3 1
1 + 2𝑥 + 3𝑥 + 4𝑥 + ⋯ ⟺
1−𝑥 2
1
1,2,3,4,5, … ⟺
1−𝑥 2

17
Differentiation (2/2)
How to generate the sequence 1,4,9,16, … ?
1
1 + 2𝑥 + 3𝑥 2
+ 4𝑥 3
+⋯⟺ 2
1−𝑥
2 3 3
𝑥
𝑥 + 2𝑥 + 3𝑥 + 4𝑥 + ⋯ ⟺ 2
1−𝑥
𝑑 𝑥
𝑥 + 2𝑥 2 + 3𝑥 3 + 4𝑥 4 + ⋯ ⟺ 𝑑 2
𝑑𝑥 1−𝑥
2 3
1+𝑥
= 1 + 4𝑥 + 9𝑥 + 16𝑥 + ⋯ ⟺
1−𝑥 3
1+𝑥
1,4,9,16, … ⟺
1−𝑥 3 18
Product
𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 , … ⟺ 𝐴 𝑥 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯
𝑏0 , 𝑏1 , 𝑏2 , 𝑏3 , … ⟺ 𝐵 𝑥 = 𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + 𝑏3 𝑥 3 + ⋯

What is the sequence corresponds to the polynomial 𝐶 𝑥 = 𝐴 𝑥 𝐵 𝑥 ?

𝐶 𝑥 = 𝐴 𝑥 𝐵 𝑥 = 𝑎0 + 𝑎1 𝑥 + ⋯ 𝑏0 + 𝑏1 𝑥 +
𝑘

𝑐𝑘 = 𝑎0 𝑏𝑘 + 𝑎1 𝑏𝑘−1 + 𝑎2 𝑏𝑘−2 + ⋯ + 𝑎𝑘−1 𝑏1 + 𝑎𝑘 𝑏0 = ෍ 𝑎𝑖 𝑏𝑘−𝑖

𝑖=0
19
Outline

1. Generating functions for basic sequences

2. Operations on generating functions

3. Counting

4. Solving recurrences

20
General strategy
Coefficient of 𝑥 𝑘 = number of ways to choose 𝑘 items.

𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
, ,…, , 0,0, … ⟺ + 𝑥 + ⋯+ 𝑥 = 1+𝑥
0 1 𝑘 0 1 𝑘

the coefficient of 𝑥 𝑘 in 1 + 𝑥 𝑛
is the number of ways
to choose 𝑘 distinct items from a set of size 𝑛.

21
Convolution rule

1. Let 𝐴 𝑥 be the generating function for selecting items from set 𝐴.

2. Let 𝐵 𝑥 be the generating function for selecting items from set 𝐵.
3. If 𝐴 and 𝐵 are disjoint, then the generating function for selecting
items from the union 𝐴 ∪ 𝐵 is the product 𝐴 𝑥 ⋅ 𝐵 𝑥 .

𝐴 𝑥 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ 𝐵 𝑥 = 𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + ⋯
𝑘

𝑐𝑘 = 𝑎0 𝑏𝑘 + 𝑎1 𝑏𝑘−1 + 𝑎2 𝑏𝑘−2 + ⋯ + 𝑎𝑘−1 𝑏1 + 𝑎𝑘 𝑏0 = ෍ 𝑎𝑖 𝑏𝑘−𝑖

𝑖=0

𝐶 𝑥 = 𝐴 𝑥 𝐵 𝑥 = 𝑎0 + 𝑎1 𝑥 + ⋯ 𝑏0 + 𝑏1 𝑥 +
22
Example: choosing fruits: an “impossible” counting problem…
How many ways can we fill a bag with 𝑛 fruits with the following constraints?

• How many ways can we fill a bag with For example, when 𝑛 = 6,
𝑛 fruits with the following constraints? there are 7 ways to form a
– The number of apples must be bag with 6 fruits.
even.
Apple 6 4 4 2 2 0 0
– The number of bananas must be a
multiple of 5. Banana 0 0 0 0 0 5 5
– There can be at most one mango. Mango 0 0 1 0 1 0 1
– There can be at most four oranges. Orange 0 2 1 4 3 1 0
23
Example: choosing fruits: generating functions (1/2)
– The number of apples must be even.
– The number of bananas must be a multiple of 5.
– There can be at most one mango.
– There can be at most four oranges.
1
GF for apples: 𝐴 𝑥 = 𝑥0 + 𝑥2
+⋯= + 𝑥4
1 − 𝑥2
0 5 10
1
GF for bananas: 𝐵 𝑥 =𝑥 +𝑥 +𝑥 +⋯=
1 − 𝑥5
GF for mangoes: 𝑀 𝑥 = 𝑥 0 + 𝑥1 = 1 + 𝑥
1 − 𝑥 5
GF for oranges: 𝑂 𝑥 = 𝑥 0 + 𝑥1 + 𝑥 2 + 𝑥 3 + 𝑥 4 =
1−𝑥
1 1 1 − 𝑥5 1
GF for fruits: 𝐴 𝑥 𝐵 𝑥 𝑀 𝑥 𝑂 𝑥 = 2
⋅ 5
⋅ 1+𝑥 ⋅ = 2
1−𝑥 1−𝑥 1−𝑥 1−𝑥 24
Example: choosing fruits: generating functions (2/2)
1
Generating function for fruits:
1−𝑥 2

How many ways can we fill a bag with 𝑛 fruits with the following constraints?

𝑑 2 3
𝑑 1
1+𝑥+𝑥 +𝑥 +⋯ ⟺
𝑑𝑥 𝑑𝑥 1 − 𝑥
1
1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 +⋯⟺
1−𝑥 2

The number of ways to choose 𝑛 fruits is the coefficient of 𝑥 𝑛 , which is exactly 𝑛 + 1

25
Exercises (1/2)
1. How many ways are there to get 𝑛 fruits that satisfy the
following three conditions?
– There are at most 2 apples.
– The number of bananas is arbitrary.
– The number of mangoes must be divisible by 3.
2. How many ways can we select 𝑛 mangoes with 𝑘 varieties?
3. How many ways can we select 𝑛 mangoes with 𝑘 varieties
such that each variety has at least two?

26
Exercises (2/2)
4. We need $17 to contribute to the disaster relief for the
people affected by the flood.
➢ There are 20 students participating in the contribution.
➢ It is known that the first 19 people will contribute $1 or nothing,
and the 20th person will contribute $1, $5, or nothing.
Use a generating function to calculate the number of ways to
contribute $17.

27
Outline

1. Generating functions for basic sequences

2. Operations on generating functions

3. Counting

4. Solving recurrences

37
 Example: Fibonacci in Animal Breeding Patterns
1. Rabbits follow the Fibonacci sequence in their
reproductive pattern.
Rabbit pairs 2. A single pair of rabbits (one male and one female)
Fibonacci’s rabbit Time (Fibonacci produces another pair in the second month.
breeding theory (months) sequence)
3. From the third month onwards, each pair produces
1 1 a new pair every month.
⋆ 4. The sequence of pairs of rabbits is 1, 1, 2, 3, 5, 8,
⋆ 2 2
3 3 13, and so on.
⋆ ⋆ 5. The breeding pattern reflects the natural balance of
4 5
reproduction and population growth.
+3 5 8 6. The population grows slowly initially as the
*offspring not breeding
(etc.) (etc.) breeding pairs are young and need time to mature.
until two months of age
7. As the population increases, more pairs are
available to reproduce, leading to an exponential
growth rate that follows the Fibonacci sequence. 38
Rabbit Populations
• Rabbits mature after one month, i.e., an offspring does not breed
until two months of age.
– 𝑤𝑛 = # newborn pairs after 𝑛 months
– 𝑟𝑛 = # reproducing pairs after 𝑛 months
• Start with a newborn pair: 𝑤0 = 1, 𝑟0 = 0
• 𝑟1 = 1
How many rabbits after 𝑛 months?
• 𝑟𝑛 = 𝑟𝑛−1 + 𝑤𝑛−1
• 𝑤𝑛 = 𝑟𝑛−1 so
• 𝑟𝑛 = 𝑟𝑛−1 + 𝑟𝑛−2 It was Fibonacci who was studying
rabbit population growth.
39
Fibonacci sequence

• The Fibonacci sequence we want to analyze is:

𝑟0 , 𝑟1 , 𝑟2 , 𝑟3 , … = 0,1,1,2,3,5,8,11 …

• Define a generating function for this sequence:

𝑅 𝑥 = 𝑟0 + 𝑟1 𝑥 + 𝑟2 𝑥 2 + 𝑟3 𝑥 3 + ⋯

• Remember 𝑟𝑖+2 = 𝑟𝑖+1 + 𝑟𝑖

First we want to obtain a closed form for 𝑅 𝑥

40
Generating Function for Rabbits

𝑅 𝑥 = 𝑟0 + 𝑟1 𝑥 + 𝑟2 𝑥 2 + 𝑟3 𝑥 3 + ⋯
−𝑥𝑅 𝑥 = −𝑟0 𝑥 − 𝑟1 𝑥 2 − 𝑟2 𝑥 3 − 𝑟3 𝑥 4 − ⋯
−𝑥 2 𝑅 𝑥 = −𝑟0 𝑥 2 − 𝑟1 𝑥 3 − 𝑟2 𝑥 4 − 𝑟3 𝑥 5 − ⋯

0 0 0 …

Remember 𝑟𝑖+2 = 𝑟𝑖+1 + 𝑟𝑖

41
 Closed form of 𝑅 𝑥 (1/2)

𝑅 𝑥 = 𝑟0 + 𝑟1 𝑥 + 𝑟2 𝑥 2 + 𝑟3 𝑥 3 + ⋯
−𝑥𝑅 𝑥 = −𝑟0 𝑥 − 𝑟1 𝑥 2 − 𝑟2 𝑥 3 − 𝑟3 𝑥 4 − ⋯
−𝑥 2 𝑅 𝑥 = −𝑟0 𝑥 2 − 𝑟1 𝑥 3 − 𝑟2 𝑥 4 − 𝑟3 𝑥 5 − ⋯

𝑅 𝑥 − 𝑥𝑅 𝑥 − 𝑥 2 𝑅 𝑥 = 𝑟0 + 𝑟1 𝑥 − 𝑟0 𝑥 = 𝑥
𝑥
𝑅 𝑥 =
1 − 𝑥 − 𝑥2
42
Closed form of 𝑅 𝑥 (2/2)
𝑥
𝑅 𝑥 =
1 − 𝑥 − 𝑥2
What is the closed form of 𝑟𝑛?
𝑥 𝐴 𝐵
• 𝑅 𝑥 = = +
1−𝛼𝑥 1−𝛽𝑥 1−𝛼𝑥 1−𝛽𝑥
1
• = 1 + 𝛼𝑥 + 𝛼 2 𝑥 2 + ⋯ + 𝛼 𝑛 𝑥 𝑛 + ⋯
1−𝛼𝑥
1
• = 1 + 𝛽𝑥 + 𝛽 2 𝑥 2 + ⋯ + 𝛽 𝑛 𝑥 𝑛 + ⋯
1−𝛽𝑥
• So 𝑟𝑛 = coefficient of 𝑥 𝑛 in 𝑅 𝑥 = 𝐴𝛼 𝑛 + 𝐵𝛽 𝑛
43
Closed form of coefficients
𝑥 𝐴 𝐵
• 𝑅 𝑥 = = +
1−𝛼𝑥 1−𝛽𝑥 1−𝛼𝑥 1−𝛽𝑥
1+ 5 1− 5
𝛼= and 𝛽 =
2 2
1 1 1 1
𝐴= = and 𝐵 = = −
𝛼−𝛽 5 𝛽−𝛼 5

• So 𝑟𝑛 = coefficient of 𝑥 𝑛 in 𝑅 𝑥
= 𝐴𝛼 𝑛 + 𝐵𝛽 𝑛
𝑛 𝑛
11+ 5 11− 5
= −
5 2 5 2
44
Exercise
Consider the sequence 𝑎𝑛 defined by the recurrence relation:
𝑎0 = 1
ቊ
𝑎𝑛 = 2𝑎𝑛−1 + 3
1. Derive the ordinary generating function A(x) for the
sequence an.
2. Use the generating function to find a closed-form
expression for 𝑎𝑛 .

50
Q&A

51