MODULE III
COMBINATORICS
Permutation & Combination: Many counting problems can be solved by finding the number of ways
to arrange a specified number of distinct elements of a set of a particular size, where the order of
these elements matters. Many other counting problems can be solved by finding the number of
ways to select a particular number of elements from a set of a particular size, where the order of the
elements selected does not matter. For example, in how many ways can we select three students
from a group of five students to stand in line for a picture? How many different committees of three
students can be formed from a group of four students? In this section we will develop methods to
answer questions such as these.
Permutations
We begin by solving the first question posed in the introduction to this section.
Example. In how many ways can we select three students from a group of five students to stand in
line for a picture? In how many ways can we arrange all five of these students in a line for a picture?
Solution: First, note that the order in which we select the students matters.
There are five ways to select the first student to stand at the start of the line.
Once this student has been selected, there are four ways to select the second student in the line.
After the first and second students have been selected, there are three ways to select the third
student in the line.
By the product rule, there are 5 · 4 · 3 = 60 ways to select three students from a group of five
students to stand in line for a picture.
To arrange all five students in a line for a picture, we select the first student in five ways, the second
in four ways, the third in three ways, the fourth in two ways, and the fifth in one way.
Consequently, there are 5 · 4 · 3 · 2 · 1 = 120 ways to arrange all five students in a line for a picture.
Example. Let S = {1, 2, 3}. The ordered arrangement 3, 1, 2 is a permutation of S. The ordered
arrangement 3, 2 is a 2-permutation of S.
The number of r-permutations of a set with n elements is denoted by P (n, r). We can find P (n, r)
using the product rule.
Example. Let S = {a, b, c}. The 2-permutations of S are the ordered arrangements a, b; a, c; b, a; b, c;
c, a; and c, b. Consequently, there are six 2-permutations of this set with three elements. There are
always six 2-permutations of a set with three elements. There are three ways to choose the first
element of the arrangement. There are two ways to choose the second element of the arrangement,
because it must be different from the first element. Hence, by the product rule, we see that P (3, 2)
= 3 · 2 = 6. the first element. By the product rule, it follows that P (3, 2) = 3 · 2 = 6.
We now use the product rule to find a formula for P (n, r) whenever n and r are positive integers
with 1 ≤ r ≤ n.
Theorem. If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are
𝑃 (𝑛, 𝑟) = 𝑛(𝑛 − 1)(𝑛 − 2) ··· (𝑛 − 𝑟 + 1)
r-permutations of a set with n distinct elements.
𝑛!
Corollary. If n and r are integers with 0 ≤ r ≤ n, then 𝑃 (𝑛, 𝑟) = (𝑛 − 𝑟)! .
Example. How many ways are there to select a first-prize winner, a second-prize winner, and a
third-prize winner from 100 different people who have entered a contest?
Solution: Because it matters which person wins which prize, the number of ways to pick the three
prize winners is the number of ordered selections of three elements from a set of 100 elements,
that is, the number of 3-permutations of a set of 100 elements.
Consequently, the answer is P (100, 3) = 100 · 99 · 98 = 970,200.
Example. How many permutations of the letters 𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻 contain the string 𝐴𝐵𝐶 ?
Solution: Because the letters 𝐴𝐵𝐶 must occur as a block, we can find the answer by finding the
number of permutations of six objects, namely, the block 𝐴𝐵𝐶 and the individual letters 𝐷, 𝐸, 𝐹, 𝐺,
and 𝐻.
Because these six objects can occur in any order, there are 6! = 720 permutations of the letters
𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻 in which 𝐴𝐵𝐶 occurs as a block.
Combinations
We now turn our attention to counting unordered selections of objects. We begin by solving a
question posed in the introduction to this section of the chapter.
Example. How many different committees of three students can be formed from a group of four
students?
Solution: To answer this question, we only need to find the number of subsets with three elements
from the set containing the four students.
We see that there are four such subsets, one for each of the four students, because choosing three
students is the same as choosing one of the four students to leave out of the group.
This means that there are four ways to choose the three students for the committee, where the
order in which these students are chosen does not matter.
Example. Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S. (Note that {4, 1, 3} is
the same 3-combination as {1, 3, 4}, because the order in which the elements of a set are listed does
not matter.)
The number of r-combinations of a set with n distinct elements is denoted by C(n, r). Note that C(n,
𝑛
r) is also denoted by ( ) and is called a binomial coefficient.
𝑟
Example. We see that C(4, 2) = 6, because the 2-combinations of {a, b, c, d} are the six subsets {a, b},
{a, c}, {a, d}, {b, c}, {b, d}, and {c, d}.
We can determine the number of r-combinations of a set with n elements using the formula for the
number of r-permutations of a set. To do this, note that the r-permutations of a set can be obtained
by first forming r-combinations and then ordering the elements in these combinations. The proof of
next Theorem, which gives the value of C(n, r), is based on this observation.
Theorem. The number of r-combinations of a set with n elements, where n is a nonnegative integer
𝑛!
and r is an integer with 0 ≤ r ≤ n, equals 𝐶(𝑛, 𝑟) = .
𝑟!(𝑛 − 𝑟)!
Example. How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also,
how many ways are there to select 47 cards from a standard deck of 52 cards?
Solution: Because the order in which the five cards are dealt from a deck of 52 cards does not
matter, there are
52!
𝐶(52, 5) = 5!47! different hands of five cards that can be dealt.
To compute the value of C(52, 5), first divide the numerator and denominator by 47! to obtain
48
𝐶(52, 5) = 52 · 51 · 50 · 49 · 5 · 4 · 3 · 2 · 1 .
This expression can be simplified by first dividing the factor 5 in the denominator into the factor 50
in the numerator to obtain a factor 10 in the numerator, then dividing the factor 4 in the
denominator into the factor 48 in the numerator to obtain a factor of 12 in the numerator, then
dividing the factor 3 in the denominator into the factor 51 in the numerator to obtain a factor of 17
in the numerator, and finally, dividing the factor 2 in the denominator into the factor 52 in the
numerator to obtain a factor of 26 in the numerator.
We find that 𝐶(52, 5) = 26 · 17 · 10 · 49 · 12 = 2,598,960.
Consequently, there are 2,598,960 different poker hands of five cards that can be dealt from a
standard deck of 52 cards.
52!
Note that there are 𝐶(52, 47) = 47!5! different ways to select 47 cards from a standard deck of 52
cards.
We do not need to compute this value because C(52, 47) = C(52, 5). (Only the order of the factors
5! and 47! is different in the denominators in the formulae for these quantities.)
It follows that there are also 2,598,960 different ways to select 47 cards from a standard deck of 52
cards.
Corollary. Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).
Example. How many ways are there to select five players from a 10-member tennis team to make a
trip to a match at another school?
Solution: The answer is given by the number of 5-combinations of a set with 10 elements.
10!
The number of such combinations is C(10, 5) = 5! 5! = 252.
Example. A group of 30 people have been trained as astronauts to go on the first mission to Mars.
How many ways are there to select a crew of six people to go on this mission (if all crew members
have the same job)?
Solution: The number of ways to select a crew of six from the pool of 30 people is the number of 6-
combinations of a set with 30 elements, because the order in which these people are chosen does
not matter.
By Theorem, the number of such combinations is
30! 30 · 29 · 28 · 27 · 26 ·25
𝐶(30, 6) = 6! 24! = 6·5·4·3·2·1
= 593,775.
Example. How many bit strings of length n contain exactly ‘r’ 1s?
Solution: The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2,
3,...,n}.
Hence, there are C(n, r) bit strings of length n that contain exactly r 1s.
Example. Suppose that there are 9 faculty members in the mathematics department and 11 in the
computer science department. How many ways are there to select a committee to develop a
discrete mathematics course at a school if the committee is to consist of three faculty members
from the mathematics department and four from the computer science department?
Solution: By the product rule, the answer is the product of the number of 3-combinations of a set
with nine elements and the number of 4-combinations of a set with 11 elements.
By Theorem 2, the number of ways to select the committee is
9! 11
𝐶(9, 3) · 𝐶(11, 4) = 3!6! · 4!7!
= 84 · 330 = 27,720.
Exercises
1. List all the permutations of {a, b, c}.
2. How many different permutations are there of the set {a, b, c, d, e, f, g}?
3. How many permutations of {a, b, c, d, e, f, g} end with a?
4. A group contains n men and n women. How many ways are there to arrange these people in
a row if the men and women alternate?
5. In how many ways can a set of two positive integers less than 100 be chosen?
6. In how many ways can a set of five letters be selected from the English alphabet?
7. How many subsets with an odd number of elements does a set with 10 elements have?
8. Cars of a particular manufacturer come in 4 models, 12 colors, 3 engine sizes and 2
transmission types.
a) How many distinct cars of a company can be manufactured?
b) Of these how many have the same color?
9. A coin is flipped eight times where each flip comes up either heads or tails. How many
possible outcomes
a) are there in total?
b) contain exactly three heads?
c) contain at least three heads?
d) contain the same number of heads and tails?
10. How many bit strings of length 10 have
a) exactly three 0s?
b) more 0s than 1s?
c) at least seven 1s?
d) at least three 1s?
11. How many 3-digit numbers can be formed by using the 6 digits 2,3,4,5,6,8 if
(a) Repetitions of digits are allowed.
(b) Repetitions of digits are not allowed.
12. Find the number of ways of arranging different objects around a circle.
OR
In how many ways can n people be seated at a round table if arrangements are considered
the same when one can be obtained from the other by rotation?
13. Find the number of permutations of the letters of the word MASSASAUGA. In how many of
these, all four A’s are together? How many of them begin with S?
14. In how many ways can seven books be arranged on a shelf if
(a) any arrangement is allowed?
(b) three books (in particular) must always be together.
(c) two books (in particular) must occupy ends.
15. A certain question paper contains three parts A, B, C with four questions in part A, five
questions in part B and six questions in part C. It is required to answer seven questions
selecting at least two questions from each part. In how many ways can a student select his
seven questions to answer?
16. A woman has 11 close relatives, and she wishes to invite 5 of them to dinner. In how many
ways can she invite them in the following situations
i) There is no restriction on the choice
ii) Two people will not attend separately
iii) Two people will not attend together
17. Find the number of nonnegative integer solutions of the equation
X1+X2+X3+X4+X5=8
18. Find the number of integer solutions of the equation
X1+X2+X3+X4+X5=30 where X1≥2, X2≥3, X3≥4, X4≥2, X5≥0
Inclusion- Exclusion principle
We showed that the number of elements in the union of the two sets A and B is the sum of the
numbers of elements in the sets minus the number of elements in their intersection. That is, |A ∪
B|=|A|+|B|−|A ∩ B|.
Example. In a discrete mathematics class, every student is either a major in Computer science or
Mathematics, or both. The number of students having Computer science as a major (possibly along
with Mathematics) is 25; the number of students having Mathematics as a major (possibly along
with Computer science) is 13; and the number of students majoring in both Computer Science and
Mathematics is 8. How many students are in this class?
Solution: Let A be the set of students in the class majoring in computer science and B be the set of
students in the class majoring in mathematics.
Then A ∩ B is the set of students in the class who are joint mathematics and computer science
majors.
Because every student in the class is majoring in either computer science or mathematics (or both),
it follows that the number of students in the class is |A ∪ B|.
Therefore, |A ∪ B|=|A|+|B|−|A ∩ B| = 25 + 13 − 8 = 30.
Therefore, there are 30 students in the class.
Example. How many positive integers not exceeding 1000 are divisible by 7 or 11?
Solution: Let A be the set of positive integers not exceeding 1000 that are divisible by 7, and let B be
the set of positive integers not exceeding 1000 that are divisible by 11.
Then A ∪ B is the set of integers not exceeding 1000 that are divisible by either 7 or 11, and A ∩ B is
the set of integers not exceeding 1000 that are divisible by both 7 and 11.
From previous Example, we know that among the positive integers not exceeding 1000 there are
1000/7 integers divisible by 7 and 1000/11 divisible by 11.
Because 7 and 11 are relatively prime, the integers divisible by both 7 and 11 are those divisible by
7 · 11.
Consequently, there are 1000/(11 · 7) positive integers not exceeding 1000 that are divisible by
both 7 and 11.
It follows that there are
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|
1000 1000 1000
=⌊ ⌋ + ⌊ 11 ⌋ − ⌊ 7.11 ⌋
7
= 142 + 90 − 12 = 220
positive integers not exceeding 1000 that are divisible by either 7 or 11.
Principle of inclusion–exclusion:
Let 𝐴1 , 𝐴2 , . . . , 𝐴𝑛 be finite sets, then
|𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑛 | = ∑1≤𝑖≤𝑛 |𝐴𝑖 | − ∑1≤𝑖<𝑗≤𝑛 |𝐴𝑖 ∩ 𝐴𝑗 | + ∑1≤𝑖<𝑗<𝑘≤𝑛|𝐴𝑖 ∩ 𝐴𝑗 ∩ 𝐴𝑘 | − ⋯ +
(−1)𝑛+1 |𝐴1 ∩ 𝐴2 ∩ … ∩ 𝐴𝑛 |.
Example. Give a formula for the number of elements in the union of four sets.
Solution: The inclusion–exclusion principle shows that
|𝐴1 ∪ 𝐴2 ∪ 𝐴3 ∪ 𝐴4 | = |𝐴1 | + |𝐴2 | + |𝐴3 | + |𝐴4 | − |𝐴1 ∩ 𝐴2 | − |𝐴1 ∩ 𝐴3 | − |𝐴1 ∩ 𝐴4 | − |𝐴2 ∩
𝐴3 | − |𝐴2 ∩ 𝐴4 | − |𝐴3 ∩ 𝐴4 | + |𝐴1 ∩ 𝐴2 ∩ 𝐴3 | + |𝐴1 ∩ 𝐴2 ∩ 𝐴4 | + |𝐴1 ∩ 𝐴3 ∩ 𝐴4 | + |𝐴2 ∩
𝐴3 ∩ 𝐴4 | − |𝐴1 ∩ 𝐴2 ∩ 𝐴3 ∩ 𝐴4 |.
Note that this formula contains 15 different terms, one for each nonempty subset of {𝐴1 , 𝐴2 , 𝐴3 , 𝐴4 }.
Exercises.
1. How many elements are in 𝐴1 ∪ 𝐴2 if there are 12 elements in 𝐴1 , 18 elements in 𝐴2 , and a)
𝐴1 ∩ 𝐴2 = ∅? b) |𝐴1 ∩ 𝐴2 | = 1? c) |𝐴1 ∩ 𝐴2 | = 6? d) 𝐴1 ⊆ 𝐴2 ?
2. There are 345 students at a college who have taken a course in calculus, 212 who have
taken a course in discrete mathematics, and 188 who have taken courses in both calculus
and discrete mathematics. How many students have taken a course in either calculus or
discrete mathematics?
3. A survey of households in the United States reveals that 96% have at least one television
set, 98% have telephone service, and 95% have telephone service and at least one television
set. What percentage of households in the United States have neither telephone service nor
a television set?
4. There are 2504 computer science students at a school. Of these, 1876 have taken a course in
Java, 999 have taken a course in Linux, and 345 have taken a course in C. Further, 876 have
taken courses in both Java and Linux, 231 have taken courses in both Linux and C, and 290
have taken courses in both Java and C. If 189 of these students have taken courses in Linux,
Java, and C, how many of these 2504 students have not taken a course in any of these three
programming languages?
5. How many integers are between 1 and 300 (inclusive)
a) divisible by at least one of 5, 6, 8?
b) divisible by none of 5, 6, 8?
6. Derangements with Restrictions
(a) Using Inclusion–Exclusion, derive a formula for the number of derangements of
{1,2,...,n}.
(b) Find the number of permutations of {1,2,3,4,5,6} such that at least two elements remain
fixed.
7. How many onto functions exist from a set with 8 elements to a set with 5 elements.
8. How many ways are there to assign 6 distinct tasks to 4 workers such that:
a) Each worker gets at least one task,
b) Worker 1 cannot do task 1,
c) Worker 2 cannot do task 2.
9. Using Inclusion–Exclusion, prove that
𝑛
∑ ( ) (−1)𝑘 (𝑛 − 𝑘)𝑚
𝑘
𝑘
equals the number of onto functions from an m-element set to an n-element set
Pigeon-hole principle
Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20
pigeons but only 19 pigeonholes, at least one of these pigeonholes must have at least two pigeons in
it.
THE PIGEONHOLE PRINCIPLE (General Form)
If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one
box containing two or more of the objects.
Example. Among any group of 367 people, there must be at least two with the same birthday,
because there are only 366 possible birthdays.
Example. In any group of 27 English words, there must be at least two that begin with the same
letter, because there are 26 letters in the English alphabet.
Example. How many students must be in a class to guarantee that at least two students receive the
same score on the final exam, if the exam is graded on a scale from 0 to 100 points?
Solution: There are 101 possible scores on the final.
The pigeonhole principle shows that among any 102 students there must be at least 2 students with
the same score.
Example. Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal
expansion.
Solution: Let n be a positive integer.
Consider the n + 1 integers 1, 11, 111,..., 11 ... 1 (where the last integer in this list is the integer with
n + 1 1s in its decimal expansion).
Note that there are n possible remainders when an integer is divided by n.
Because there are n + 1 integers in this list, by the pigeonhole principle there must be two with the
same remainder when divided by n.
The larger of these integers less the smaller one is a multiple of n, which has a decimal expansion
consisting entirely of 0s and 1s.
THE GENERALIZED PIGEONHOLE PRINCIPLE
𝑁
If N objects are placed into k boxes, then there is at least one box containing at least ⌈ ⌉ objects.
𝑘
100
Example. Among 100 people there are at least ⌈ 12 ⌉ = 9 who were born in the same month.
Example. What is the minimum number of students required in a discrete mathematics class to be
sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?
Solution: The minimum number of students needed to ensure that at least six students receive the
𝑁
same grade is the smallest integer N such that ⌈ ⌉ = 6.
5
The smallest such integer is N = 5 · 5 + 1 = 26.
If you have only 25 students, it is possible for there to be five who have received each grade so that
no six students have received the same grade.
Thus, 26 is the minimum number of students needed to ensure that at least six students will receive
the same grade.
Example. What is the least number of area codes needed to guarantee that the 25 million phones in
a state can be assigned distinct 10-digit telephone numbers? (Assume that telephone numbers are
of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit
from 2 to 9 inclusive, and X represents any digit.)
Solution: There are eight million different phone numbers of the form NXX-XXXX.
25,000,000
Hence, by the generalized pigeonhole principle, among 25 million telephones, at least ⌈ ⌉=
8,000,000
4 of them must have identical phone numbers.
Hence, at least four area codes are required to ensure that all 10-digit numbers are different
Exercises
1. Show that in any set of six classes, each meeting regularly once a week on a particular day of the
week, there must be two that meet on the same day, assuming that no classes are held on
weekends.
2. Show that if there are 30 students in a class, then at least two have last names that begin with the
same letter.
3. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes
socks out at random in the dark.
a) How many socks must he take out to be sure that he has at least two socks of the same
color?
b) How many socks must he take out to be sure that he has at least two black socks?
4. A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking
at them.
a) How many balls must she select to be sure of having at least three balls of the same color?
b) How many balls must she select to be sure of having at least three blue balls?
5. Show that among any group of five (not necessarily consecutive) integers, there are two with the
same remainder when divided by 4.
6. Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive)
integers there are two with the same remainder when they are divided by d.
7. Show that among any 51 integers, there exist 6 integers whose difference is divisible by 10.
8. Prove that among any n^2 + 1 integers, there exist n + 1 integers that give the same remainder when
divided by n.
9. Show that in any sequence of 2n − 1 integers, there exists a subsequence of n integers whose sum is
divisible by n.
10. Prove that among any 17 distinct integers, there exist either 5 increasing or 5 decreasing elements.
Recurrence Relation
Definition: A recurrence relation for a sequence {𝑎𝑛 } is a rule that tells us how to find each term
using the terms that come before it.
That is, for all 𝑛 ≥ 𝑛0 (where 𝑛0 is a non-negative integer), the term 𝑎𝑛 is written in terms of one or
more of the earlier terms
𝑎0 , 𝑎1 , … , 𝑎𝑛−1 .
In simple words: each new term of the sequence is calculated from the previous terms using a fixed
formula.
Example. Let {𝑎𝑛 } be a sequence that satisfies the recurrence relation 𝑎𝑛 = 𝑎𝑛−1 + 3 for n = 1, 2,
3,..., and suppose that 𝑎0 = 2. What are 𝑎1 , 𝑎2 , and 𝑎3 ?
Solution: We see from the recurrence relation that 𝑎1 = 𝑎0 + 3 = 2 + 3 = 5.
It then follows that 𝑎2 = 5 + 3 = 8 and 𝑎3 = 8 + 3 = 11.
Example. Let {𝑎𝑛 } be a sequence that satisfies the recurrence relation 𝑎𝑛 = 𝑎𝑛−1 − 𝑎𝑛−2 for n =
2, 3, 4,..., and suppose that 𝑎0 = 3 and 𝑎1 = 5. What are 𝑎2 and 𝑎3 ?
Solution: We see from the recurrence relation that 𝑎2 = 𝑎1 − 𝑎0 = 5 − 3 = 2 and 𝑎3 = 𝑎2 − 𝑎1
= 2 − 5 = −3.
We can find 𝑎4 , 𝑎5 , and each successive term in a similar way.
Example. The Fibonacci sequence, 𝑓0 , 𝑓1 , 𝑓2 , . . ., is defined by the initial conditions 𝑓0 = 0, 𝑓1 = 1,
and the recurrence relation
𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2 for n = 2, 3, 4,....
Example. Find the Fibonacci numbers 𝑓2 , 𝑓3 , 𝑓4 , 𝑓5, and 𝑓6.
Solution: The recurrence relation for the Fibonacci sequence tells us that we find successive terms
by adding the previous two terms.
Because the initial conditions tell us that 𝑓0 = 0 and 𝑓1 = 1, using the recurrence relation in the
definition we find that
𝑓2 = 𝑓1 + 𝑓0 = 1 + 0 = 1,
𝑓3 = 𝑓2 + 𝑓1 = 1 + 1 = 2,
𝑓4 = 𝑓3 + 𝑓2 = 2 + 1 = 3,
𝑓5 = 𝑓4 + 𝑓3 = 3 + 2 = 5,
𝑓6 = 𝑓5 + 𝑓4 = 5 + 3 = 8.
Example. Determine whether the sequence {𝑎𝑛 }, where 𝑎𝑛 = 3n for every nonnegative integer n, is
a solution of the recurrence relation 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 for n = 2, 3, 4,... . Answer the same
question where 𝑎𝑛 = 2n and where 𝑎𝑛 = 5.
Solution: Suppose that 𝑎𝑛 = 3𝑛 for every nonnegative integer n.
Then, for n ≥ 2, we see that 2𝑎𝑛−1 − 𝑎𝑛−2 = 2(3(𝑛 − 1)) − 3(𝑛 − 2) = 3𝑛 = 𝑎𝑛.
Therefore, {𝑎𝑛 }, where 𝑎𝑛 = 3n, is a solution of the recurrence relation.
Suppose that 𝑎𝑛 = 2n for every nonnegative integer n.
Note that 𝑎0 = 1, 𝑎1 = 2, and 𝑎2 = 4.
Because 2𝑎1 − 𝑎0 = 2 · 2 − 1 = 3 = 𝑎2 , we see that {𝑎𝑛 }, where 𝑎𝑛 = 2n, is not a solution of
the recurrence relation.
Suppose that 𝑎𝑛 = 5 for every nonnegative integer n.
Then for n ≥ 2, we see that 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 = 2 · 5 − 5 = 5 = 𝑎𝑛 .
Therefore, {𝑎𝑛 }, where 𝑎𝑛 = 5, is a solution of the recurrence relation.
Example. Solve the recurrence relation and initial condition in previous Example.
Solution: We can successively apply the recurrence relation in previous Example, starting with the
initial condition 𝑎1 = 2, and working upward until we reach an to deduce a closed formula for the
sequence.
We see that 𝑎2 = 2 + 3 𝑎3 = (2 + 3) + 3 = 2 + 3 · 2 𝑎4 = (2 + 2 · 3) + 3 = 2 + 3 ·
3 . . . 𝑎𝑛 = 𝑎𝑛−1 + 3 = (2 + 3 · (𝑛 − 2)) + 3 = 2 + 3(𝑛 − 1).
We can also successively apply the recurrence relation in Example, starting with the term an and
working downward until we reach the initial condition a1 = 2 to deduce this same formula.
The steps are 𝑎𝑛 = 𝑎𝑛−1 + 3 = (𝑎𝑛−2 ) + 3) + 3 = 𝑎_(𝑛 − 2) + 3 · 2
= (𝑎𝑛−3 + 3) + 3 · 2
= 𝑎𝑛−3 + 3 · 3
. ..
= 𝑎2 + 3(𝑛 − 2) = (𝑎1 + 3) + 3(𝑛 − 2) = 2 + 3(𝑛 − 1)
At each iteration of the recurrence relation, we obtain the next term in the sequence by adding 3 to
the previous term.
We obtain the nth term after n − 1 iterations of the recurrence relation.
Hence, we have added 3(n − 1) to the initial term 𝑎0 = 2 to obtain 𝑎𝑛 .
This gives us the closed formula an = 2 + 3(n − 1). Note that this sequence is an arithmetic
progression.
Exercises
1. Find these terms of the sequence {𝑎𝑛 }, where 𝑎𝑛 = 2 · (−3)𝑛 + 5𝑛 .
a) 𝑎0
b) 𝑎1
c) 𝑎4
d) 𝑎5
2. What is the term a8 of the sequence {an} if an equals
a) 2𝑛−1
b) 7
c) 1 + (−1)𝑛
d) −(−2)𝑛
3. What are the terms 𝑎0 , 𝑎1 , 𝑎2 , and 𝑎3 of the sequence {𝑎𝑛 }, where an equals
a) 2𝑛 + 1
b) (𝑛 + 1)𝑛+1
4. What are the terms a0, a1, a2, and a3 of the sequence {an}, where an equals
a) (−2)𝑛
b) 3
c) 7 + 4𝑛
d) 2𝑛 + (−2)𝑛
5. List the first 10 terms of each of these sequences.
a) the sequence that begins with 2 and in which each successive term is 3 more than the preceding
term
b) the sequence that lists each positive integer three times, in increasing order
c) the sequence that lists the odd positive integers in increasing order, listing each odd integer
twice
d) the sequence whose nth term is n! − 2n
e) the sequence that begins with 3, where each succeeding term is twice the preceding term
f ) the sequence whose first term is 2, second term is 4, and each succeeding term is the sum of the
two preceding terms
g) the sequence whose nth term is the number of bits in the binary expansion of the number n
h) the sequence where the nth term is the number of letters in the English word for the index n.
6. If 𝑎𝑛 is a solution of the recurrence relation 𝑎𝑛+1 = 𝑘 𝑎𝑛 for 𝑛 ≥ 0, and 𝑎3 = 153/49, 𝑎5 =
𝟑
1377/2401, what is k? [Ans: 𝒌 = ± 𝟕]
Generating functions
Definition. The generating function for the sequence 𝑎0 , 𝑎1 , … , 𝑎𝑘 , … of real numbers is the infinite
series 𝐺(𝑥) = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑘 𝑥 𝑘 + ⋯ = ∑∞𝑘=0 𝑎𝑘 𝑥
𝑘
Example. The generating functions for the sequences {𝑎𝑘 } with 𝑎𝑘 = 3, 𝑎𝑘 = 𝑘 + 1, and 𝑎𝑘 = 2𝑘
are ∑∞ 𝑘 ∞ 𝑘 ∞ 𝑘 𝑘
𝑘=0 3𝑥 , ∑𝑘=0(𝑘 + 1)𝑥 and ∑𝑘=0 2 𝑥 , respectively.
We can define generating functions for finite sequences of real numbers by extending a finite
sequence 𝑎0 , 𝑎1 , . . . , 𝑎𝑛 into an infinite sequence by setting 𝑎𝑛+1 = 0, 𝑎𝑛+2 = 0, and so on.
The generating function G(x) of this infinite sequence {𝑎𝑛 } is a polynomial of degree n because no
terms of the form 𝑎𝑗 𝑥𝑗 with 𝑗 > 𝑛 occur, that is, 𝐺(𝑥) = 𝑎0 + 𝑎1 𝑥 +··· + 𝑎𝑛 𝑥 𝑛 .
Example. What is the generating function for the sequence 1, 1, 1, 1, 1, 1?
Solution: The generating function of 1, 1, 1, 1, 1, 1 is
1 + 𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4 + 𝑥 5.
𝑥6 − 1
By Theorem we have 𝑥−1
= 1 + 𝑥 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5
𝑥6 − 1
when x ≠ 1. Consequently, 𝐺(𝑥) = 𝑥−1
is the generating function of the sequence 1, 1, 1, 1, 1, 1.
[Because the powers of x are only place holders for the terms of the sequence in a generating
function, we do not need to worry that G(1) is undefined.]
Example. Let m be a positive integer. Let 𝑎𝑘 = C(m, k), for k = 0, 1, 2,...,m. What is the generating
function for the sequence 𝑎0 , 𝑎1 , . . . , 𝑎𝑚 ?
Solution: The generating function for this sequence is
𝐺(𝑥) = 𝐶(𝑚, 0) + 𝐶(𝑚, 1)𝑥 + 𝐶(𝑚, 2)𝑥 2 +··· + 𝐶(𝑚, 𝑚)𝑥 𝑚 .
Binomial theorem shows that 𝐺(𝑥) = (1 + 𝑥)𝑚 .
Theorem. Let 𝑓(𝑥) = ∑∞ 𝑘 ∞ 𝑘
𝑘=0 𝑎𝑘 𝑥 and 𝑔(𝑥) = ∑𝑘=0 𝑏𝑘 𝑥 . Then
∞ ∞ 𝑘
𝑓(𝑥) + 𝑔(𝑥) = ∑(𝑎𝑘 + 𝑏𝑘 )𝑥 𝑘 𝑎𝑛𝑑 𝑓(𝑥)𝑔(𝑥) = ∑ (∑ 𝑎𝑗 𝑏𝑘−𝑗 ) 𝑥 𝑘
𝑘=0 𝑘=0 𝑗=0
1
Example. Let 𝑓 (𝑥) = (1 − 𝑥)2 . Find the coefficients 𝑎0 , 𝑎1 , 𝑎2 , ... in the expansion 𝑓 (𝑥) = ∑∞ 𝑘
𝑘=0 𝑎𝑘 𝑥 .
1
Solution: Using the known expansion 1−𝑥 = 1 + 𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4 + ⋯
1
for ∣ 𝑥 ∣< 1 and differentiating term by term, we get 2 = 1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 + 5𝑥 4 + ⋯
(1−𝑥)
Hence the coefficients are 𝑎0 = 1, 𝑎1 = 2, 𝑎2 = 3, …
and in general 𝑎𝑘 = 𝑘 + 1for ∣ 𝑥 ∣< 1.
Definition. Let u be a real number and k a nonnegative integer. Then the extended binomial
𝑢(𝑢−1)…𝑢−𝑘+1
𝑢 𝑢
coefficient ( ) is defined by ( ) = { 𝑘! 𝑖𝑓 𝑘 > 0
𝑘 𝑘 1 𝑖𝑓 𝑘 = 0
1
−2
Example. Find the values of the extended binomial coefficients ( ) and ( 2 ).
3 3
−2 (−2)(−3)(−4)
Solution: Taking u = −2 and k = 3, we get ( )= = −4.
3 3!
Similarly, taking u = 1/2 and k = 3 gives us
1 1 1 1
( )( − 1)( − 2)
1 1 3
( )(− )(− )
2 2 2 2 2 2 1
(2) = 3!
= 6
= 16.
3
Example. In how many ways can eight identical cookies be distributed among three distinct
children if each child receives at least two cookies and no more than four cookies?
Solution: Let 𝑥1 , 𝑥2 , 𝑥3 be the numbers of cookies given to the three distinct children.
Given 𝑥1 + 𝑥2 + 𝑥3 = 8with 2 ≤ 𝑥𝑖 ≤ 4.
First remove the minimum condition by putting 𝑥𝑖 = 𝑦𝑖 + 2 .
Then 𝑦1 + 𝑦2 + 𝑦3 = 8 − 6 = 2and 𝑦𝑖 ≥ 0.
Now count the non-negative integer solutions of 𝑦1 + 𝑦2 + 𝑦3 = 2 .
Using stars and bars, the number of solutions is (2+3−1
3−1
) = (42) = 6.
So, the number of ways to distribute the cookies is 6.
Exercises
1. Find the generating function for the finite sequence 2, 2, 2, 2, 2, 2.
2. Find the generating function for the finite sequence 1, 4, 16, 64, 256.
3. Find a closed form for the generating function for each of these sequences. (For each sequence,
use the most obvious choice of a sequence that follows the pattern of the initial terms listed.)
a) 0, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, ...
b) 0, 0, 0, 1, 1, 1, 1, 1, 1, ...
c) 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ...
d) 2, 4, 8, 16, 32, 64, 128, 256, ...
7 7 7 7
e) ( ) , ( ) , ( ) , … ( ), 0, 0, 0, 0, 0, ...
0 1 2 7
f ) 2, −2, 2, −2, 2, −2, 2, −2, ...
g) 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, ...
h) 0, 0, 0, 1, 2, 3, 4, ...
4. Use generating functions to solve the recurrence relation aₙ = aₙ₋₁ + 2aₙ₋₂, with a₀ = 1 and a₁ =
2.
5. Let aₙ= 1 for all n ≥ 0 and bₙ = n. Find the generating function of the sequence cₙ = ∑𝑛𝑘=0 𝑎𝑘 𝑏𝑛−𝑘 .
6. Using generating functions, find the number of ways to select items if at most 2 items of type A, at
most 3 items of type B, and at most 1 item of type C are allowed. Find the coefficient of x⁴.
7. Suppose A(x) = (1 + 2x) / (1 - 3x)(1 - x). Find the recurrence satisfied by 𝑎𝑛 .
8. If A(x) = x + xA(x)2 . Find a recurrence for the coefficients 𝑏𝑛 .
1
9. Given A(x) = , determine:
1 − 2x − 𝑥 2
(a) The recurrence
(b) The closed form
(c) The asymptotic growth rate of 𝑎𝑛 .
Note: Text and figures have been used from Rosen and other online sources where needed