Discrete Mathematics and Linear Algebra

Module-2 Counting Techniques

Dr. G. Saranya
Contents

1. Introduction
2. Basic Counting Principles
3. The Pigeonhole Principle
4. Permutations
5. Combinations
6. Inclusion Exclusion Principle
7. Recurrence Relation
8. Generating Functions
Introduction

Combinatorics, the study of

Introduction

Combinatorics, the study of arrangements of objects, is an

important part of discrete mathematics.
Enumeration,
Introduction

Combinatorics, the study of arrangements of objects, is an

important part of discrete mathematics.
Enumeration, the counting of objects with certain properties, is an
important part of combinatorics.
We must count objects to solve many different types of problems.
For instance, counting is required to determine the complexity of
algorithms, to determine whether there are enough telephone
numbers or Internet protocol addresses to meet the demand, in
mathematical biology in sequencing DNA and also when
probability of events are computed.
Basic Counting Principles

Product Rule
Sum Rule
Subtraction Rule
Product Rule
Problem 1
Problem 1
Problem 2
Problem 2
Problem 3
Problem 3
Problem 4
Problem 4
Problem 4
Sum Rule
Problem 1
Problem 1
Problem 2
Problem 2
Problem 3
Problem 3
Problem 3
Subtraction Rule

Definition
If a task can be done in either n1 ways or n2 ways, then the number of
ways to do the task is n1 + n2 minus the number of ways to do the task
that are common to the two different ways. This rule is also known as
the principle of inclusion-exclusion.
or
|A ∪ B| = |A| + |B| − |A ∩ B|.
Problems
Problems
Problems
Problems
The Pigeonhole Principle

Definition
If there are n − 1 pigeonholes and n pigeons, then there is at least one
pigeonhole which has more than one pigeon.

Example
In any group of 27 English words,there must be at least two words that
begin with the same letter, since there are 26 letters in the English
alphabet.
Generalized Pigeonhole Principle
Generalized Pigeonhole Principle
Generalized Pigeonhole Principle
Problems
Problems
Problems
Permutations and Combinations
Problem:
How many numbers between 10 and 10, 000 can be formed by using the
digits 1, 2, 3, 4, 5 if
(i) no digits is repeated in any number
(ii) digits can be repeated
Solution:
(i) Number of two digit numbers = 5 × 4 = 20
Number of three digit numbers = 5 × 4 × 3 = 60
Number of four digit numbers = 5 × 4 × 3 × 2 = 120
Total number of numbers = 20 + 60 + 120 = 200

(ii) Number of two digit numbers = 5 × 5 = 25

Number of three digit numbers = 5 × 5 × 5 = 125
Number of four digit numbers = 5 × 5 × 5 × 5 = 625
Total number of numbers = 25 + 125 + 625 = 775
Definition (Factorial Notation)
An efficient way of writing a product of several consecutive integers is
the factorial notation. The number n! is defined as follows:
For any positive integer n, n! = n(n − 1)(n − 2) · · · (3)(2)(1).

Example
1. 4! = 4 × 3 × 2 × 1 = 24
2. 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

Note
1. n! = n(n − 1)!
n!
2. n(n − 1) · · · (n − (r − 1)) = (n−r)!
Permutation

Definition
Each of the different arrangements, which can be made by taking some
or all of a number of objects is called permutation. The number of
permutations of n different objects taken r at a time is represented as
nP = n!
r (n−r)! = n(n − 1)(n − 2) · · · (n − (r − 1))(where, 0 ≤ r ≤ n)

Note
1. In permutation, the order of the items plays an important role.
2. The number of all permutations of n distinct objects taken all at a
time is n!.
Problems: 1. If 56 P : 54 Pr+3 = 30800 : 1, find r P2
r+6
Permutation

Definition
Each of the different arrangements, which can be made by taking some
or all of a number of objects is called permutation. The number of
permutations of n different objects taken r at a time is represented as
nP = n!
r (n−r)! = n(n − 1)(n − 2) · · · (n − (r − 1))(where, 0 ≤ r ≤ n)

Note
1. In permutation, the order of the items plays an important role.
2. The number of all permutations of n distinct objects taken all at a
time is n!.
Problems: 1. If 56 Pr+6 : 54 Pr+3 = 30800 : 1, find r P2
Solution: Use the formula for n Pr ,
56
We have, 54 PPr+6
r+3
= 30800
1
56!
= (50−r)! × (51−r)!
54! = 30800
1 ⇒ 56 × 55(51 − r) =
41
30800 ⇒ r = 41. Therefore, P2 = 41 × 40 = 1640.
Problems

2. Three men have 4 coats, 5 waist coats and 6 caps. In how many ways
can they wear them?
Problems

2. Three men have 4 coats, 5 waist coats and 6 caps. In how many ways
can they wear them?
Solution:
The total number of ways in which three men can wear 4 coats is the
number of arrangements of 4 different coats taken 3 at a time. So, three
men can wear 4 coats in 4 P3 ways. Similarly, 5 waist coats and 6 caps
can be worn by three men in 5 P3 and 6 P3 ways respectively.
Problems

2. Three men have 4 coats, 5 waist coats and 6 caps. In how many ways
can they wear them?
Solution:
The total number of ways in which three men can wear 4 coats is the
number of arrangements of 4 different coats taken 3 at a time. So, three
men can wear 4 coats in 4 P3 ways. Similarly, 5 waist coats and 6 caps
can be worn by three men in 5 P3 and 6 P3 ways respectively.
Hence, the required number of ways = 4 P3 × 5 P3 × 6 P3 = (4!) × (5 × 4 ×
3) × (6 × 5 × 4) = 172800.
Steps involved in the solution of a permutation problem
1. Recognizing the objects and the places involved in the problem.
2. Checking whether the repetition of the objects is allowed or not.

Permutations with Repetition

These kinds of problems occur with permutations of different objects in
which some of the objects can be repeated. The number of
permutations of n different objects taken r at a time when each object
may be repeated any number of times is nr .
Problem:
A student appears in an objective test which contains 10 multiple choice
questions. Each question has four choices in which one is the correct
option. What maximum number of different answers can the student
give? How will the answer change if each question may have more than
one correct answers?
Solution:
Use the concept of Permutation with Repetition.
For the first part each question has four possible answers. So, the total
possible answers = 4 × 4 × ....10times = 410 .
For the second part. Suppose the choices for each question are denoted
by A, B, C and D. Now the choice A is either correct or incorrect (two
ways) similarly the other choices are either correct or incorrect.
Thus, this particular question can have 2×2×2×2 = 16 possible answers.
But this includes the case when all the four choices are incorrect.
Thus the total number of answers 15. Now, as there are 10 questions
and each question has 15 possible answers. Therefore the total number
of answers = 1510 .
Permutation with Alike Objects
This kind of problems involve permutations of different objects in
which some of them are similar.
The number of permutations of n objects taken all at a time in which,
p are alike objects of one kind, q are alike objects of second kind and r
are alike objects of a third kind and the rest (n − (p + q + r)) are all
n!
different is p!q!r!

Problem:
Determine the number of permutations of the letters of the word ‘SIM-
PLETION’ taken all at a time
Solution:
In the given word the letter ‘I’ occurs twice and the remaining letters
occur only once. So, the concept of Permutation of Alike Objects is used
to find out the answer.
There are 10 letters in the word ‘SIMPLETION’ and out of these 10
letters two are identical. So, just selecting all 10 objects at a time will
give twice the actual result.
Hence, the number of permutations of taking all the letters at a time
10 P
= 2! 10
= 10!
2! = 181440.
Combination
Definition
Each of the different groups or selection which can be made by some or
all of a number of given objects without reference to the order of the
objects in each group is called a combination.
The number of all combinations of n objects, taken r at a time is
n
n!
generally denoted by C(n, r) or n Cr = r!(n–r)! (0 ≤ r ≤ n) = r!Pr

Note
1. The number of ways of selecting r objects out of n objects, is the
same as the number of ways in which the remaining (n − r) can be
selected and rejected.
2. The combination notation also represents the binomial coefficient.
That is, the binomial coefficient n Cr is the combination of n
elements chosen r at a time.
3. nC = n Cn−r
r
Problems

1. A basketball coach must select two attackers and two defenders

from among three attackers and five defenders. How many
different combinations of attackers and defenders can he select?
2. There are 4 oranges, 5 apples and 6 mangoes in a fruit basket. In
how many ways can a person select fruits from among the fruits in
the basket?
Inclusion-Exclusion Principle
Recurrence Relation
Definition
An equation that expresses an , the general term of the sequence {an }
in terms of one or more of the previous terms of the sequence, namely
a0 , a1 , · · · , an−1 for all integers n with n ≥ n0 , where n0 is a
non-negative integer is called a recurrence relation for {an } or a
difference equation.
If the terms of a sequence satisfy a recurrence relation, then the
sequence is called a solution of the recurrence relation.

Example
Let us consider the famous Fibonacci sequence

0, 1, 1, 2, 3, 5, 8, 13, · · ·

which can be represented by the recurrence relation Fn+2 = Fn+1 + Fn ,

where n ≥ 0 and F0 = 0, F1 = 1.
Definition
Definition
A linear homogeneous recurrence relation degree k with constant
coefficients is a recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k

where c1 , c2 , · · · , ck are real numbers and ck ̸= 0.

Example
1. The recurrence relation fn = fn−1 + fn−2 is a linear homogeneous
recurrence relation of degree two.
2. The recurrence relation an = an−5 is a linear homogeneous
recurrence relation with constant coefficients.
1. The recurrence relation an = an−1 + a2n−2 is not linear.
2. The recurrence relation an = an−1 + a2n−2 + n is not homogeneous.
Solving Recurrence Relations

Let us consider the recurrence relation of the form

c0 an + c1 an−1 + c2 an−2 = 0, n ≥ 2.

Let an = rn (r ̸= 0) be a solution of the above recurrence relation. Then

c0 rn + c1 rn−1 + c2 rn−2 = 0 ⇒ c0 r2 + c1 r + c2 = 0,

The above equation is a quadratic equation in r, which is called the

characteristic equation, whose roots are r1 and r2 are the characteristic
roots of the recurrence relation.
Case:1 r1 and r2 are real and distinct. Then the solution is an =
k1 r1n + k2 r2n , where k1 , k2 are arbitrary constants determined by initial
conditions.
Case:2 r1 and r2 are real and equal.
Then the solution is an = (k1 + k2 n)rn , where r1 = r2 = r.
Case:3 r1 and r2 are complex conjugates. Let r1 = r(cos θ + i sin θ),
then r2 = r(cos θ − i sin θ). Therefore, the solution is an = rn (k1 cos nθ +
k2 sin nθ).
Linear Non-homogeneous recurrence relation
The solution of a linear non-homogeneous recurrence relation with
constant coefficients, viz., a recurrence relation of the form

c0 an + c1 an−1 + c2 an−2 + · · · + ck an−k = f (n),

where f (n) ̸= 0 is of the form

an = a(h) (p)
n + an ,

(p)
where an is the solution of the associated homogeneous recurrence
relation, namely

c0 an + c1 an−1 + c2 an−2 + · · · + ck an−k = 0

(p)
and an is a particular solution of the non-homogeneous equation.
Particular Solutions
Solution of Recurrence Relations by Using Generating
Functions

Definition
The generating function of a sequence a0 , a1 , a2 , · · · , is the expression
∞
X
G(x) = a0 + a1 x + a2 x2 + · · · , ∞ = an xn
n=0

Example
1. The generating function for the sequence 1, 1, 1, · · · is given by
∞
X 1
G(x) = xn = .
1−x
n=0
Example
2. The generating function for the sequence 1, 2, 3, 4, · · · is given by
∞
X 1
G(x) = (n + 1)xn = 1 + 2x + 3x2 + · · · = .
(1 − x)2
n=0

3. The generating function for the sequence 1, a, a2 , a3 , · · · is given by

1
G(x) = 1 + ax + a2 x2 + · · · = ,
1 − ax
for |ax| < 1.