DISCRETE STRUCTURES

Permutation,
Combination,
Combination with Unlimited Repetition,
Pigeonhole Principle
 What is combinatorics?
• A branch of mathematics that deals with
the counting, combination, and permutations of
elements in a set is known as combinatorics. We
use the term combinatorics to describe the
humungous subset of discrete mathematics that
also encompasses graph theory. Combinatorics is
all about counting, therefore while solving the
problems related to combinatorics we will deal
with the enumeration of things. In other words,
we can say that it deals with the counting of the
number of arrangements in which something can
happen.
Dr. Shipra Jain
 Contin….
• There are two main concepts of combinatorics -
combination, and permutation. Both these
concepts are used to enumerate the number of
orders in which the things can happen. However,
there is one difference between the two terms
and that is the combination deals with counting
the number of arrangements in which an event
can occur, given that the order of arrangements
does not matter. Whereas, the order of
arrangements matters in the permutation.

Dr. Shipra Jain

Fundamental counting of principle
• The fundamental counting principle states
that if one event can occur in A different
ways and a second event can occur
in B different ways then the total number of
ways in which both events can occur is A×B.

Dr. Shipra Jain

Dr. Shipra Jain
 Two Fundamental principles of counting

• 1. Sum Rule Principle (Addition Rule)

• 2. Product Rule Principle (Multiplication Rule)

Dr. Shipra Jain

 Sum Rule Principle
Sum Rule Principle- Suppose an event E can occur in n1 ways
and a second event F can occur in n2 ways and if both event can
not occur simultaneously . Then E or F can occur in n1+n2 ways.
General format- Suppose an event E1 can occur in n1 ways , a
second event E2 can occur in n2 ways, a third event E3 can occur
in n3 ways ….. And suppose no two of the event can occur at the
same time. Then one of the event can occur in
n1+n2+n3…….ways.
Example- Suppose there are 8 male professor and 5 female
professor teaching a calculus class. A student can choose a
calculus professor in 8+5 =13 ways.

Dr. Shipra Jain

 Product Rule Principle
Product Rule Principle- If an event E can occur
in m ways and, independent of this event there
is a second event F which can occur in n ways.
Then combination of E and F can occur in m. n
ways. (the product rule applies when a
procedure is made up of separate task).
For Example- If there are ways to do Task 1,
ways to then do Task 2, and ways to then do
Task 3, then there are (m ⋅ n ⋅ p) ways to do
first Task 1, then Task 2, then Task 3.

Dr. Shipra Jain

Product Rule

Dr. Shipra Jain

 Product Rule
• If one event can occur in m ways, a second
event in n ways and a third event in r, then the
three events can occur in m × n × r ways.

Dr. Shipra Jain

 Example
• Erin has 5 tops, 6 skirts and 4 caps from which
to choose an outfit. In how many ways can she
select one top, one skirt and one cap?
• Solution:
Ways = 5 × 6 × 4

Dr. Shipra Jain

Dr. Shipra Jain
 Example
James has to go to a party and he has three different shirts and two different
pants to choose from. Shirts are red, black and white in color while pants are
blue and green in color. How many possible outfits can James choose from?
James can wear either of the two pants with each shirt.

So, James can wear Red shirt with either Blue or Green pants. Similarly, Black and
White shirts can be selected with either Blue or Green pants. We had 3 different
options for shirts and two different options for pants so, 3×2=6 possible outfits.

Dr. Shipra Jain

 Example
• Harry went to a food restaurant and he wants
to order a combo deal that includes a pizza,
drink, and dessert in it. The following choices
are available:
• Pizza: Chicken Fajita and Vegetable
• Drink: Pepsi and 7-Up
• Dessert: Ice-cream and Pie

Dr. Shipra Jain

Dr. Shipra Jain
Dr. Shipra Jain
 Example
• Steve has to dress for a presentation. He
has 3 different shirts,2 different pants,
and3 different shoes available in his closet.
Wearing the Tie is optional. Calculate the total
number of possible outfits.
• Solution:
There are three types of shirts, two types of
pants and three types of shoes. While the tie is
optional so the tie has two options either “Yes”
or “No”.
• Total number of possible outfits =3×2×3×2=36.

Dr. Shipra Jain

Sum Rule

Dr. Shipra Jain

 Definition
• The rule of sum states that if event A can
occur in n different ways and event B can
occur in m different ways while both
events A and B are mutually exclusive then
the total number of possible outcomes can be
given as n+m.

Dr. Shipra Jain

Example-Jessica has a jar of cookies. It
has 3 chocolate and 3 peanut cookies in it.
Jessica only wants to eat one cookie. How many
possible options does Jessica have?
Solution- Since Jessica only wants each one
cookie so, she has to choose only one cookie
from 3 chocolate or 3 peanut cookies. The
choices are mutually exclusives so by applying
the rule of sum we have 3+3=6 possible
options.

Dr. Shipra Jain

Example 4: Ellie went to a dress shop to purchase a single blue
dress. The shop has 14 plain blue dresses, 13 plain red dresses,
10 blue embroidered dresses, and 5 red embroidered dresses .
How many options does Ellie have?

Solution-
Since Ellie wants to choose a blue dress so, we
will eliminate all red dresses. She can choose
from 14 plain blue dresses or 10 blue
embroidered dresses. So, the total numbers of
option are

Dr. Shipra Jain

The Counting Principle and Rule of Sum
We have discussed the problems related to the fundamental counting
principle and the rule of sum. What if a problem has to be solved using
both the rules?

Dr. Shipra Jain

• Example- Harris went to a shop to buy some items of
clothing. He can choose a shirt from 3 different colors
or a T-shirt from 2 different colors. Also, he can either
get a pair of pants from 3 available colors or a pair of
jeans from 3 available colors. How many possible
outfits can Harris have?
• Solution-
• Harris can take one shirt from given 3 colors or a T-
shirts from the available 2 colors. So number of
available shirts =3+2=5.
• Similarly, he can choose a pair of pants from either 3
options or a pair of jeans from three options. The
number of available pairs of jeans/pants 3+3=6.
• So, we have 5 different shirts and 6 different pants and
a total number of possible outfits will be 5×6=30.

Dr. Shipra Jain

• Example - Steve wants to go to a job interview in another
city. He can choose from 4 local bus services or 3 taxi
services to reach the other city. From there he can choose
from 3 local bus services or 2 taxi services to reach the
place of his interview. How many possible routes/ways
Steve can travel to his destination?
• Solution-
• Steve can choose to take either a local bus or a taxi to reach
the other city. So, the possible numbers of vehicles that can
be used to reach the city are 4+3=7.
• Similarly,
• Steve can either choose from 3 local bus services or 2 taxi
services to reach the location of the interview from the city.
Number of possible option 3+2=5.
• Now, the total number of ways/vehicles Steve can use to
reach his interview destination is 7×5=35.

Dr. Shipra Jain

Applications of the Counting Principle
• Suppose 5 boys A, B, C, D, and E are to be seated on a
couch in a row. Then in how many possible ways they can
be seated? Suppose that Boy A=event A, Boy B=event B and
so on. So, for event A, we have five possible options, for the
event B, we have four possible options, for the event C we
have three possible options, for the event D we have two
possible options and one option for the event E.
• By the rule of counting principle to calculate the total
number of ways, we multiply the possibilities of each event.
In this case the total number of possible outcomes
is 5×4×3×2×1=120. This is also known as permutation and it
is an application of the counting principle.

Dr. Shipra Jain

Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
• Example- Calculate the number of ways in which
digits from 0−9 can be arranged.
• Solution:
• There are total numbers of 10 digits. The number
of ways in which the first digits can be arranged is
10. Similarly, for the second digit, we have 9
available options and so on for the rest of the
digits. The total numbers of possible ways to
arrange the digits
• 10!=10×9×8×7×6×5×4×3×2×1=3628800.

Dr. Shipra Jain

• Example- Calculate the number of ways in
which four digits can be selected from 0−9.
• Solution:
• There are total numbers of 10 digits and we
have to select only four from the available 10
digits. Here n=10 while r=4.

Dr. Shipra Jain

Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
 Problem
• Quest: Consider a word ‘YOURSELEVES’. In how
many ways the letter can be arranged if U and S
always come together and ‘U’ always precedes ‘S’?
• Solution: The word ‘YOURSELVES’ has 11 letters
out of which ‘S’ repeats two times and ‘E’ repeats
three times. The rest are all different.
• If the letter ‘U’ and ‘S’ come together, they are
considered as one letter. The remaining 10 letters
can rearrange themselves in 10! ⁄ (2! 3!) = 302400
ways.
Dr. Shipra Jain
 Problem:

• Find the number of ways in which five persons

A, B, C, D, and E sit around a round table such
that
• There is no restriction.
• A and D must always sit together.
• C and E must not sit together.

Dr. Shipra Jain

Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Dr. Shipra Jain
Example - In how many ways a committee consisting of 5 men and 3 women, can
be chosen from 9 men and 12 women?

Solution-

Choose 5 men out of 9 men = 9C5 ways = 126 ways

Choose 3 women out of 12 women = 12C3 ways = 220 ways
The committee can be chosen in 27720 ways.

Dr. Shipra Jain

Example - Out of 7 consonants and 4 vowels, how many words of 3
consonants and 2 vowels can be formed?
Solution-
Number of ways of selecting 3 consonants from 7= 7C3
Number of ways of selecting 2 vowels from 4= 4C2

Number of ways of selecting 3 consonants from 7 and 2 vowels from 4

= 7C3 × 4C2
=(7×6×53×2×1)×(4×32×1)=210=(7×6×53×2×1)×(4×32×1)=210

It means we can have 210 groups where each group contains total 5 letters
(3 consonants and 2 vowels).

Number of ways of arranging 5 letters among themselves

=5!=5×4×3×2×1=120=5!=5×4×3×2×1=120
Hence, required number of ways =210×120=25200

Dr. Shipra Jain

Example -In a group of 6 boys and 4 girls, four children are to
be selected. In how many different ways can they be selected
such that at least one boy should be there?
Solution- In a group of 6 boys and 4 girls, four children are to
be selected such that at least one boy should be there.

Hence we have 4 options as given below

We can select 4 boys ...(option 1)

Number of ways to this = 6C4

We can select 3 boys and 1 girl ...(option 2)

Number of ways to this = 6C3 × 4C1

Dr. Shipra Jain

We can select 2 boys and 2 girls ...(option 3)
Number of ways to this = 6C2 × 4C2

We can select 1 boy and 3 girls ...(option 4)

Number of ways to this = 6C1 × 4C3

Total number of ways

= 6C4 + 6C3 × 4C1 + 6C2 × 4C2 + 6C1 × 4C3
= 6C2 + 6C3 × 4C1 + 6C2 × 4C2 + 6C1 × 4C1 [∵ nCr = nC(n-r)]
=6×52×1+6×5×43×2×1×4=6×52×1+6×5×43×2×1×4 +6×52×1×4×32×1+6×4+6×52×1
×4×32×1+6×4
=15+80+90+24=209

Dr. Shipra Jain

Example - From a group of 7 men and 6 women, five persons
are to be selected to form a committee so that at least 3 men
are there in the committee. In how many ways can it be done?

Dr. Shipra Jain

Solution- Hence we have the following 3 options.

We can select 5 men ...(option 1)

Number of ways to do this = 7C5

We can select 4 men and 1 woman ...(option 2)

Number of ways to do this = 7C4 × 6C1

We can select 3 men and 2 women ...(option 3)

Number of ways to do this = 7C3 × 6C2

Total number of ways

= 7C5 + (7C4 × 6C1) + (7C3 × 6C2)
= 7C2 + (7C3 × 6C1) + (7C3 × 6C2)[∵ nCr = nC(n - r) ]
• =7×62×1+7×6×53×2×1×6=7×62×1+7×6×53×2×1×6 +7×6×53×2×1×6×5
2×1+7×6×53×2×1×6×52×1
• =21+210+525=756

Dr. Shipra Jain

Example 6- In how many different ways can the letters of the word
'OPTICAL' be arranged so that the vowels always come together?
Solution- The word 'OPTICAL' has 7 letters. It has the vowels 'O','I','A' in it
and these 3 vowels should always come together. Hence these three vowels
can be grouped and considered as a single letter. That is,
PTCL(OIA).
Hence we can assume total letters as 5 and all these letters are different.
Number of ways to arrange these letters
=5!=5×4×3×2×1=120=5!=5×4×3×2×1=120

All the 3 vowels (OIA) are different

Number of ways to arrange these vowels among themselves
=3!=3×2×1=6=3!=3×2×1=6

Hence, required number of ways

=120×6=720

Dr. Shipra Jain

Example 7-In how many different ways can the letters of the word
'CORPORATION' be arranged so that the vowels always come together?
Solution-The word 'CORPORATION' has 11 letters. It has the vowels
'O','O','A','I','O' in it and these 5 vowels should always come together. Hence these 5
vowels can be grouped and considered as a single letter. that is, CRPRTN(OOAIO).

Hence we can assume total letters as 7. But in these 7 letters, 'R' occurs 2 times and
rest of the letters are different.

Number of ways to arrange these letters

=7!2!=7×6×5×4×3×2×12×1=2520=7!2!=7×6×5×4×3×2×12×1=2520

In the 5 vowels (OOAIO), 'O' occurs 3 and rest of the vowels are different.

Number of ways to arrange these vowels among

themselves =5!3!=5×4×3×2×13×2×1=20=5!3!=5×4×3×2×13×2×1=20

Hence, required number of ways

=2520×20=50400=2520×20=50400

Dr. Shipra Jain

Combination is of two types:
• Combination with repetition
• Combination without repetition

Dr. Shipra Jain

 Combination With Repetition
• Let suppose there are p elements in a set A. We
are asked to select q elements from this set, given
that each element can be selected multiple times.
This is known as a combination with repetition.
For instance, we can make combinations of three
elements of the set {p, q, r, s} in this way:

• ppp, ppq, ppr, pps, pqq, pqr, pqs, prr, prs, pss,
qqq, qqr, qqs, qrr, qrs, qss, rrr, rrs,rss, sss
• You can see that most of the alphabets are
repeated more than once.
Dr. Shipra Jain
 Example
• Three flavors of ice-cream are available in an ice-
cream cafe. These flavors are chocolate, vanilla,
and pineapple. A person can have only two scoops
of ice cream. What will be the variations in this
case?
• Well, if the person can select two scoops at a time,
then he can have one flavor two times. In this
case, the examples of variations can be:
• chocolate, chocolate, vanilla chocolate, chocolate
pineapple, etc.
• The order does not matter, and flavors can be
repeated.

Dr. Shipra Jain

Combinations with Repetitions Formula

Dr. Shipra Jain

Example 1-There are five colored balls in a
pool. All balls are of different colors. In how
many ways can we choose four pool balls?
Solution
The order in which the balls can be selected
does not matter in this case. The selection of
balls can be repeated.
Total number of balls in the pool= n = 5
The number of balls to be selected = r = 4

Dr. Shipra Jain

Dr. Shipra Jain
Example 2-There are eight different ice-cream flavors in
the ice-cream shop. In how many ways can we choose five
flavors out of these eight flavors?
Solution
The order in which the flavors can be selected does not
matter in this case. One ice-cream flavor can be selected
multiple times.
Total number of ice-cream flavors = n = 8
The number of ice-cream flavors to be selected = r = 5
Use the following formula to get the number of
arrangements in which the five ice-cream flavors can be
chosen.

Dr. Shipra Jain

Dr. Shipra Jain
Example 3-Harry has six different colored
shirts. In how many ways can he hang the four
shirts in the cupboard?
Example 4-Alice has seven different
chocolates. How many ways can five
chocolates be selected?
Example 5-Sam has five colored pencils. In
how many ways can he select three pencils?
Example 6-Mariah has ten different candies.
How many ways can six candies be selected?

Dr. Shipra Jain

 Restricted – Combinations
• (a) Number of combinations of ‘n’ different
things taken ‘r’ at a time, when ‘p’ particular
things are always included = n-pCr-p.
• (b) Number of combination of ‘n’ different
things, taken ‘r’ at a time, when ‘p’ particular
things are always to be excluded = n-pCr
• In how many ways can a cricket- 11player be chosen out of 15
players? if
• (i) A particular player is always chosen,
• (ii) A particular is never chosen.

Dr. Shipra Jain

 Example
• In how many ways can a cricket- 11player be
chosen out of 15 players? if
• (i) A particular player is always chosen,
• (ii) A particular is never chosen.

Dr. Shipra Jain

 Solution
• (i) A particular player is always chosen, it
means that 10 players are selected out of the
remaining 14 players.
• =. Required number of ways = 14C10 = 14C4
• = 14!/4!x19! = 1365
• (ii) A particular players is never chosen, it means
that 11 players are selected out of 14 players.
• => Required number of ways = 14C11
• = 14!/11!x3! = 364

Dr. Shipra Jain

 Number of ways of selecting zero or more things from
‘n’ different things is given by:- 2n-1

• Proof: Number of ways of selecting one thing, out of n-

things = nC1
• Number of selecting two things, out of n-things =nC2
• Number of ways of selecting three things, out of n-things
=nC3
• Number of ways of selecting ‘n’ things out of ‘n’ things
= nCn
• =>Total number of ways of selecting one or more things out
of n different things
• = nC1 + nC2 + nC3 + ------------- + nCn
• = (nC0 + nC1 + -----------------nCn) - nC0
• = 2n – 1 [ nC0=1]

Dr. Shipra Jain

 Example
• John has 8 friends. In how many ways can he
invite one or more of them to dinner?
• Ans. John can select one or more than one
of his 8 friends.
• => Required number of ways = 28 – 1= 255.

Dr. Shipra Jain

 Number of ways of selecting zero or more things from
‘n’ identical things is given by :- n+1

• In how many ways, can zero or more letters be

selected form the letters AAAAA?
• Ans. Number of ways of :
• Selecting zero 'A's = 1
• Selecting one 'A's = 1
• Selecting two 'A's = 1
• Selecting three 'A's = 1
• Selecting four 'A's = 1
• Selecting five 'A's = 1
• => Required number of ways = 6 [5+1]
Dr. Shipra Jain
Dr. Shipra Jain
 Pigeonhole Principle

Pigeonhole principle also known as Drichlet drawer principle

states that if there are more pigeons then pigeonholes ,then
there must be at least one pigeonhole with at least two pigeons
in it.
Means
If n pigeonholes are occupied by n+1 or more pigeons ,then at
least one pigeonhole is occupied by more then one pigeon.

Example-
Suppose a department contain 13 professor . Then two of the
professor are born in same month.

Dr. Shipra Jain

 GENERALIZED PIGEONHOLE PRINCIPLE

GENERALIZED PIGEONHOLE PRINCIPLE

Ifn pigeonholes are occupied by kn+1 or more
pigeons , where k is a positive integer ,then at
least one pigeonhole is occupied by k+1 or more
pigeons.

Q. Find the minimum no of students in a class to be

sure that three of them are born in the same
month.

Dr. Shipra Jain

 Extended Pigeonhole Principle

The extended version of the Pigeonhole Principle states that if

objects are placed in boxes then at least one box must hold at
least

Dr. Shipra Jain

Pigeonhole principle is one of the simplest but most useful ideas
in mathematics. We will see more applications that proof of this
theorem.

Example – 1: If (Kn+1) pigeons are kept in n pigeon holes

where K is a positive integer, what is the average no. of pigeons
per pigeon hole?
Solution: average number of pigeons per hole = (Kn+1)/n
= K + 1/n
Therefore there will be at least one pigeonhole which will contain
at least (K+1) pigeons i.e., ceil[K +1/n] and remaining will contain
at most K i.e., floor[k+1/n] pigeons.
i.e., the minimum number of pigeons required to ensure that at
least one pigeon hole contains (K+1) pigeons is (Kn+1).

Dr. Shipra Jain

Example – 2: Suppose a laundry bag contains many
red, white and blue stocks of socks. Then one need
only grab four socks to be sure of getting a pair with
same color.
Solution – M items & N containers
If M > N then at least one container with
[M/N]
items.
4 grab
2 same
3 different

Dr. Shipra Jain

Example – 2: A bag contains 10 red marbles, 10 white
marbles, and 10 blue marbles. What is the minimum no. of
marbles you have to choose randomly from the bag to ensure
that we get 4 marbles of same color?
Solution: Apply pigeonhole principle.
No. of colors (pigeonholes) n = 3
No. of marbles (pigeons) K+1 = 4
Therefore the minimum no. of marbles required = Kn+1
By simplifying we get Kn+1 = 10.
Verification: ceil[Average] is [Kn+1/n] = 4
[Kn+1/3] = 4
Kn+1 = 10
i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

Dr. Shipra Jain

Pigeonhole principle strong form –
Theorem: Let q1, q2, . . . , qn be positive
integers.
If q1+ q2+ . . . + qn – n + 1 objects are put
into n boxes, then either the 1st box
contains at least q1 objects, or the 2nd box
contains at least q2 objects, . . ., the nth box
contains at least qn objects.

Dr. Shipra Jain

Example – 1: In a computer science department, a
student club can be formed with either 10 members
from first year or 8 members from second year or 6
from third year or 4 from final year. What is the
minimum no. of students we have to choose
randomly from department to ensure that a student
club is formed?
Solution: we can directly apply from the above
formula where,
q1 =10, q2 =8, q3 =6, q4 =4 and n=4
Therefore the minimum number of students required
to ensure department club to be formed is
10 + 8 + 6 + 4 – 4 + 1 = 25
Dr. Shipra Jain
Example – 2: A box contains 6 red, 8 green, 10 blue, 12 yellow and 15
white balls. What is the minimum no. of balls we have to choose randomly
from the box to ensure that we get 9 balls of same color?
Solution: Here in this we cannot blindly apply pigeon principle. First we
will see what happens if we apply above formula directly.
From the above formula we have get answer 47 because
6 + 8 + 10 + 12 + 15- 5 + 1 = 47
But it is not correct.
In order to get the correct answer we need to include only blue, yellow and
white balls because red and green balls are less than 9. But we are picking
randomly so we include after we apply pigeon principle.
i.e., 9 blue + 9 yellow + 9 white – 3 + 1 = 25

Since we are picking randomly so we can get all the red and green balls
before the above 25 balls. Therefore we add 6 red + 8 green + 25 = 39
We can conclude that in order to pick 9 balls of same color randomly, one
has to pick 39 balls from a box.

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain

Pigeonhole Principle

Dr. Shipra Jain