COUNTING
Dr. Subin P. Joseph
Department of Mathematics
Govt. Engg. College, Wayanad
Fundamental Principles of Counting
The rule of sum
If a first task can be performed in m ways, while a second task can be
performed in n ways, and the tasks cannot be performed simultaneously, then
performing either task can be accomplished in any one of m + n ways.
Cailcut
Trivandrum
Total 5 routes from Calicut to Trivandrum
Fundamental Principles of Counting
The rule of product
If a procedure can be broken down into first and second stages, and if there
are m possible outcomes for the first stage and if, for each of these
outcomes, there are n possible outcomes for the second stage, then the
total procedure can be carried out, in the designated order, in m x n ways.
Cailcut Trivandrum
Thrissur
Total 6 ways from Calicut to Trivandrum
Permutations and Combinations
Given the set of three letters, {A, B, C}, how many possibilities are there
for selecting any two letters where order is important?
(AB, AC, BC, BA, CA, CB)
Given the set of three letters, {A, B, C}, how many possibilities are there
for selecting any two letters where order is not important?
(AB, AC, BC).
Permutation: The number of ways in which a subset of
objects can be selected from a given set of objects, where
order is important.
Combination: The number of ways in which a subset of
objects can be selected from a given set of objects, where
order is not important.
Permutations and Combinations
Factorial Formula for Permutations
n!
n Pr .
(n r )!
Factorial Formula for Combinations
n Pr n!
n Cr .
r ! r !(n r )!
Permutations and Combinations
How many ways can you select two letters followed by three
digits for an ID if repeats are not allowed?
Two parts:
1. Determine the set of two letters. 2. Determine the set of three digits.
26P2 10P3
2625 1098
650 720
650720
468,000
Permutations and Combinations
A common form of poker involves hands (sets) of five cards each, dealt
from a deck consisting of 52 different cards. How many different 5-card
hands are possible?
Hint: Repetitions are not allowed and order is not important.
52C5
2,598,960 5-card hands
Permutations and Combinations
Find the number of different Find the number of arrangements
subsets of size 3 in the set: of size 3 in the set:
{m, a, t, h, r, o, c, k, s}. {m, a, t, h, r, o, c, k, s}.
9 C3 9P3
987
504 arrangements
84 Different subsets
Permutations and Combinations
Guidelines on Which Method to Use
Permutations and Combinations
1. In how many ways can you choose 5 out of 10 friends to invite to a dinner
party?
Solution: Does the order of selection matter? If you choose friends in the order
A,B,C,D,E or A,C,B,D,E the same set of 5 was chosen, so we conclude that the order of
selection does not matter. We will use the formula for combinations since we are
concerned with how many subsets of size 5 we can select from a set of 10.
P(10,5) 10(9)(8)(7)(6) 10(9)(8)(7)
C(10,5) = 2(9)(2)(7) 252
5! 5(4)(3)(2)(1) (5)(4)
Permutations and Combinations
How many ways can you arrange 10 books on a bookshelf that has space for only 5
books?
Does order matter? The answer is yes since the arrangement ABCDE is a different
arrangement of books than BACDE. We will use the formula for permutations. We
need to determine the number of arrangements of 10 objects taken 5 at a time.
So we have P(10,5) = 10(9)(8)(7)(6)=30,240
Permutations and Combinations
How many bit strings of length 10 contain:
a) exactly four 1’s?
Find the positions of the four 1’s
Does the order of these positions matter?
Nope!
Positions 2, 3, 5, 7 is the same as positions 7, 5, 3, 2
Thus, the answer is C(10,4) = 210
b) at most four 1’s?
There can be 0, 1, 2, 3, or 4 occurrences of 1
Thus, the answer is:
C(10,0) + C(10,1) + C(10,2) + C(10,3) + C(10,4)
= 1+10+45+120+210
= 386
Permutations and Combinations
How many bit strings of length 10 contain:
c) at least four 1’s?
There can be 4, 5, 6, 7, 8, 9, or 10 occurrences of 1
Thus, the answer is:
C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)
= 210+252+210+120+45+10+1
= 848
Alternative answer: subtract from 210 the number of
strings with 0, 1, 2, or 3 occurrences of 1
d) an equal number of 1’s and 0’s?
Thus, there must be five 0’s and five 1’s
Find the positions of the five 1’s
Thus, the answer is C(10,5) = 252
Permutations and Combinations
a) How many ways can a 3-person subcommittee be selected
from a committee of a seven people?
b) How many ways con a president vice-president, and secretary
be selected from a committee of 7 people?
(A ) The number of ways that a three-person subcommittee can
be selected from a seven member committee is the number of
combinations (since order is not important in selecting a
subcommittee) of 7 objects 3 at a time. This is:
Permutations and Combinations
(B) The number of ways a president, vice-president, and
secretary can be chosen from a committee of 7 people is the
number of permutations (since order is important in
choosing 3 people for the positions) of 7 objects 3 at a time.
This is:
Permutations and Combinations
From a standard 52-card deck, how many 7-card hands
have exactly 5 spades and 3 hearts?
The five spades can be selected in C13,5 ways and the two
hearts can be selected in C13,2 ways. Applying the
Multiplication Principle, we have: Total number of hands
Permutations and Combinations
The English alphabet contains 21 consonants and 5
vowels. How many strings of six lower case letters
of the English alphabet contain:
exactly one vowel?
exactly 2 vowels
at least 1 vowel
at least 2 vowels
Permutations and Combinations
The English alphabet contains 21 consonants and 5 vowels.
How many strings of six lower case letters of the English
alphabet contain:
exactly one vowel?
Note that strings can have repeated letters!
We need to choose the position for the vowel
C(6,1) = 6!/1!5! This can be done 6 ways.
Choose which vowel to use.
This can be done in 5 ways.
Each of the other 5 positions can contain any of the 21
consonants (not distinct).
There are 215 ways to fill the rest of the string.
6*5*215
Permutations and Combinations
The English alphabet contains 21 consonants and 5 vowels.
How many strings of six lower case letters of the English
alphabet contain:
exactly 2 vowels?
Choose position for the vowels.
C(6,2) = 6!/2!4! = 15
Choose the two vowels.
5 choices for each of 2 positions = 52
Each of the other 4 positions can contain any of 21
consonants.
214
15*52*214
Permutations and Combinations
The English alphabet contains 21 consonants and 5 vowels.
How many strings of six lower case letters of the English
alphabet contain:
at least 1 vowel
Count the number of strings with no vowels
and subtract this from the total number of
strings.
266 - 216
Permutations and Combinations
The English alphabet contains 21 consonants and 5 vowels.
How many strings of six lower case letters of the English
alphabet contain:
at least 2 vowels
Compute total number of strings and subtract
number of strings with no vowels and the
number of strings with exactly 1 vowel.
266 - 216 - 6*5*215
Permutations and Combinations
How many committees of 5 people can be chosen from 20 men and 12
women
If exactly 3men must be on each committee?
If at least 4 women must be on each committee?
• If exactly three men must be on each committee?
– We must choose 3 men and 2 women. The choices are not mutually exclusive,
we use the product rule
• If at least 4 women must be on each committee?
– We consider 2 cases: 4 women are chosen and 5 women are chosen. Theses
choices are mutually exclusive, we use the addition rule:
Permutations and Combinations
In how many ways can the English letters be arranged
so that there are exactly 10 letters between a and z?
– The number of ways is P(24,10)
– Since we can choose either a or z to come first, then there
are 2P(24,10) arrangements of the 12-letter block
– For the remaining 14 letters, there are P(15,15)=15!
possible arrangements
– In all there are 2P(24,10).15! arrangements
Permutations and Combinations
How many ways are there for 4 horses to finish if ties are allowed?
Note that order does matter!
Solution by cases
No ties
The number of permutations is P(4,4) = 4! = 24
Two horses tie
There are C(4,2) = 6 ways to choose the two horses that tie
There are P(3,3) = 6 ways for the “groups” to finish
A “group” is either a single horse or the two tying horses
By the product rule, there are 6*6 = 36 possibilities for this case
Two groups of two horses tie
There are C(4,2) = 6 ways to choose the two winning horses
The other two horses tie for second place
Three horses tie with each other
There are C(4,3) = 4 ways to choose the two horses that tie
There are P(2,2) = 2 ways for the “groups” to finish
By the product rule, there are 4*2 = 8 possibilities for this case
All four horses tie
There is only one combination for this
By the sum rule, the total is 24+36+6+8+1 = 75
• Any arrangements of RRRRRUUU, will give a path
Binomial theorem
Multinomial theorem
