We have solved example 11 about permutations of letters of the word PENCIL containing no repeated letters. Now consider the word KEENNESS. It has 8
letters consisting of one K, three E's, two N's and two S's. We want to determine the number of permutations of these letters. It can be regarded as determining
the number of ways to place these letters in 8 defferent places such that each letter occupies exactly one place.
Firstly, we need to decide which place is to be occupied by the letter K, and this can be done in 8C1 ways. Then there are 7 places left,
among them, we need to decide which places are to be occupied by 3 E's and this can be done in 7C3 ways. After that, the places of 2 N's
can be chosen in 4C2 ways. Finally, there are 2C2 ways to place 2 S's. By the multiplication principle,
the number of permutations of all the letters is 8C1 ⋅ 7C3 ⋅ 4C2 ⋅ 2C2
$$\small{= \dfrac{8!}{1! \cdot \cancel{7!}} \cdot \dfrac{\cancel{7!}}{3! \cdot \cancel{4!}} \cdot \dfrac{\cancel{4!}}{2! \cdot 2!} \cdot 1}$$
= 8!⁄1! 3! 2! 2!.
We can generallize the above result as follows.
Suppose we are given n objects, in which n1 objects are of the first kind, n2 objects are of the second kind,
n3 objects are of the third kind, ..., and nr objects are of the rth kind, such that
n1 + n2 + ... + nr = n. Then the number of permutations of all these n objects is n1!⁄n1 ! n2! ... nr!
Example 20.
In how many ways can a permutation of all the letters of the word EXCELLENCE be formed? Solution
In the word EXCELLENCE, there are 10 letters consisting of four E's, one X, two C's, two L's and one N. So, number of ways is 10!⁄4! 1! 2! 2! 1!.
= 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4!⁄4! ⋅ 1 ⋅(2 ⋅ 1)
⋅ (2 ⋅ 1) ⋅ 1
= 10 ⋅ 9 ⋅ 2 ⋅ 7 ⋅ 6 ⋅ 5
= 37800
The Exclusion Principle
The exclusion principle is a way to count what you are interested in by first counting what you are not interested in. This is often needed for counting where
a certain property is prohibited (not allowed).
The Exclusion Principle
Count what you are not interested in and subtract it from the total.
Consider 5-digit codes containing each of the digits 1, 2, 3, 4, 5 exactly once. We have known that the codes can be formed in 5! ways. Suppose we want to know
the number of those codes, not ending in 25. On contrary, we count the number of the codes ending in 25. The number of these codes is 3!, since
the last two digits is neglected. The resulting number 5! - 3! = 114 is the number of codes not ending in 25.
Example 21.
How many permutations are there of the letters of the word PROGRAM, if they do not end in:
(a) 2R's? (b) MAP? Solution
In the word PROGRAM, there are 7 letters consisting of one P, two R's, one O, one G, one A and one M, so the number of permutations of the letter is 7!⁄2! =
7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2!⁄2!
= 2520.
(Hereafter the factor 1! may be omitted in the denominators of such fractions.)
(a) The number of permutations ending in two R's is 5! = 120,
since the two R's are fixed at the end.
The number of permutations not ending in two R's = 2520 - 120 = 2400.
(b) The number of permutations ending in MAP is 4!⁄2! =
4 ⋅ 3 ⋅ 2!⁄2!
= 12,
since MAP is fixed at the end, and there are two R's in the remaining 4 letters.
The number of permutations not ending in two R's = 2520 - 12 = 2508.
Counting the Subsets of a Finite Set
Consider a set X = {a, b, c, d, e}. A subset containing r elements, with 0 ≤ r ≤ 5, can be regarded as a combination of 5
elements taking r at a time. Thus there are 5Cr subsets containing r elements. For example, there are
5C4 = 5 subsets containing 4 elements, as listed below.
{a, b, c, d, {a, b, c, e}, {a, b, d, e}, {a, c, d, e}, {b, c, d, e}
So, by the addition principle, the number of all the subsets of X is given by 5C0 + 5C1 + 5C2 + ... + 5C5.
On the other hand, to form a subset, we have to decide which elements of X should be included in that subset. There are two choices for each element of X.
By the multiplication principle, the number ways to form a subset of X is
2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 25.
This means that the set X has 25 subsets.
We have demonstrated the two different techniques for counting the subsets of the set X, and notices that 5C0 + 5C1 + 5C2 + ... + 5C5 = 25.
We can generalize the above result as follows.
If a finite set contains n elements, then it has 2n subsets.
If n is an integer with n ≥ 0, then nC0 + nC1 + nC2 + ...
+ nCn = 2n.
Example 22.
If A is a set containing 9 distinct elements, how many subsets of A contain
(a) at most 2 elements?
(b) at least 3 elements? Solution
(a) The number of permutations containing no element, 1 element and 2 elements are
9C0, 9C1 and
9C2 respectively.
So the number of sets containing at most 2 elements is 9C0 + 9C1 +
9C2 = 1 + 9 + 9 ⋅ 8 ⁄ 2 ⋅ 1
= 1 + 9 + 36
= 46 .
(b) The number of all subsets of S is 29 = 512.
The number of subsets containing at least 3 elements = 512 - 46 = 466.
Miscellaneous Counting Problems
Example 23.
How many 4-digit even numbers, greater than 4000, can be formed using the digits 1, 2, 3, 4 and 5, without repeating any digit? Solution
Since the numbers are greater than 4000, the first digit must be 4 or 5. Case 1. If the first digit is 4 and the last digit is 2,
The number can be formed in 1 ⋅ 3 ⋅ 2 ⋅ 1 = 6 ways.
Case 2. If the first digit is 5 and the last digit is 2 or 4,
the number can be formed in 1 ⋅ 3 ⋅ 2 ⋅ 2 = 12 ways.
So the number of 4-digit even numbers greater than 4000 is 6 + 12 = 18.
Example 24.
In how many ways can 2 different chemistry books, 4 different mathematics books and 3 different physics books be arranged in a line on a shelf if
(a) 2 chemistry books are to be placed on the left, 4 mathematics books in the middle and 3 physics books on the right?
(b) books of the same subjects are together? Solution
(a) The number of ways to place chemistry books in the left part is 2! = 2 ⋅ 1 = 2.
The number of ways to place 3 physics books in the right part is 3! = 3 ⋅ 2 ⋅ 1 = 6.
The number of ways to place 4 mathematics books in the middle part is
4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24.
The required number of ways = 2 ⋅ 24 ⋅ 6 = 288.
(b) The 3 subject wise groups can be placed in 3! = 6 ways, and in each such arrangement the books can be placed in 288 ways (as in part (a)).
The required number of ways to arrange books of the same subject together
= 6 ⋅ 288 = 1728.
Example 25.
How many permutations of the letters S, U, N, D, A, Y are there if the two vowels are placed together? Solution
If the two vowels U an A unite to form a new single letter, then the number of permutations of the letters is 5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120.
Again, U and A can be arranged in 2 different ways as UA and AU in each such permutation.
So the required number of permutations is 120 ⋅ 2 = 240.
Example 26.
Find the number of permutations of all the letters of the word INTERNET in such a way that there are exactly 4 letters between the two T's.
Solution
The letter must be arranged in one of the three forms:
T ★ ★ ★ ★ T ★ ★ ★ T ★ ★ ★ ★ T ★
★ ★ T ★ ★ ★ ★ T
in which the 6 letters (2 N's, 2 E's, 1 I and 1 R) other than 2 T's are to be put in star (★) positions. For each such form, the number of ways to put
the six letters in star (★) positions is 6! ⁄2! ⋅ 2! =
6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2! ⁄2! ⋅ 2 ⋅ 1
= 180.
So the required number of permutations is 3 ⋅ 180 = 540.
Exercise 5.4
1. Find the number of permutations of the letters of each of the following words.
(i)INFINITY (ii) PINEAPPLE (iii) ACCEPTABLE Solution
(i)INFINITY has 8 letters. (3 I's, 2 N's are repeated letters)
The number of permutations = 8! ⁄3! ⋅ 2!
= 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3! ⁄3! ⋅ 2 ⋅ 1
= 3360.
(ii) PINEAPPLE has 9 letters. (3 P's, 2 E's are repeated letters)
The number of permutations = 9! ⁄3! ⋅ 2!
= 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3! ⁄3! ⋅ 2 ⋅ 1
= 30240.
(iii) ACCEPTABLE has 10 letters. (2 A's, 2 C's, 2 E's are repeated letters)
The number of permutations = 10! ⁄2! ⋅ 2! ⋅ 2!
= 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2! ⁄2! ⋅ 1 ⋅ 2 ⋅ 1 ⋅ 2
= 453600.
2. Password for a mobile payment system are to consist of 6 digits from a set of digits 0, 1, 2, ... , 9 and assume that there is no other restriction.
How many such passwords have repeated digits?
Solution
The number of possible passwords = 10 × 10 × 10 × 10 × 10 × 10
= 1 000 000
The number of passwords without any repeated digit = 10P6
= 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5
= 151 200
The number of passwords with repeated digit = 1 000 000 - 151 200
= 848 800
3. A building has 10 windows in front. What is the number of signals that can be given, by having one or more of the windows open? Solution
Number of windows = 10
Each window can either be open or closed.
There are two possible states for each window.
The number of signals = 210 = 1024
The number of signals with all windows closed = 1.
The number of signals that can be given, by having one or more of the windows open is = 1024 - 1
= 1023
4. At a burger shop, 3 different types of buns, 7 types of cheeses and 5 types of vegetables are available. Assume that a burger may contain no cheese or no
vegetable. In how many ways can different types of burgers be ordered if a person must have a bun, and may have at most 2 types of cheeses and any number of
types vegetables. Solution
The number of ways for bun = 3C1 = 3
The number of ways for vegetables = 5C0 + 5C1 + 5C2 +
5C3 + 5C4 + 5C5 or 25
= 32 Case (1) If no cheeses is used,
the number of ways = 3 × 32 = 96 Case (2) If one type of cheeses is used,
the number of ways = 3 × 7 × 32 = 672 Case (3) If two types of the cheeses is used,
the number of ways = 3 × 7C2 × 32
= 3 × 7! ⁄2! ⋅ (7-2)! × 32
= 3 × 7 ⋅ 6 ⋅ 5! ⁄1 ⋅ 2 ⋅ 5! × 32
= 3 × 21 × 32
= 2016
The required number of ways = 96 + 672 + 2016
= 2784.
5. How many different 4-digit codes can be formed using all the digits 0, 1, 2, 3 if
(i) There is no restriction?
(ii) repetation is not allowed?
(iii) repetation is not allowed, and 0 is either the first or the last digit? Solution
(i) The number of different 4 digit codes = 4 × 4 × 4 × 4 = 44 = 256
(ii) The number of different 4 digit codes if repeatition is not allowed
= 4 × 3 × 2 × 1 = 24
(iii) Case (1) If the first digit is 0,
The numbers can be formed in
1 ⋅ 3 ⋅ 2 ⋅ 1 = 6 ways
case (2) If the last digit is 0,
The number can be formed in 3 ⋅ 2 ⋅ 1 ⋅ 1 = 6 ways
The number of different 4 digit codes is 6 + 6 = 12
6. Using the letters of the word EQUATION without repetations, how many 4-letter codes can be formed:
(i) Starting with T and ending with N?
(ii) starting and ending with a consonant?
(iii) with vowels only?
(iv) if it contains 3 consonants? Solution
Number of letters = 8
Type of code = 4-letter codes
Number of 4-letter codes can be formed = 6 × 5 = 30
(ii) Starting and ending with a consonant
Number of 4-letter codes can be formed = 3 × 6 × 5 × 2 = 180.
(iii) with vowel only,
Number of 4-letter codes can be formed = 5 × 4 × 3 × 2 = 120
(iv) If it contains 3 consonants,
Number of 4-letter codes can be formed = 3 × 2 × 1 × 5 = 30
The required number of codes = 4 × 30 = 120.
7. Three brothers and three sisters are lining up to be photographed. How many arrangements are there
(i) with three sisters standing together?
(ii) if brothers and sisters are in alternating positions? Solution
(i) with 3 sisters standing together
The number of arrangements = 4!
= 4 ⋅ 3 ⋅ 2 ⋅ 1
= 24
The required number of arrangements = 6 × 24
= 144
(ii) If brothers and sisters are in alternating position,
The number of arrangements = 3 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 ⋅ 1
= 36
The required number of arrangements = 2 × 36
= 72
8. How many permutations of the letters H, E, X, A, G, O, N are there if
(i) the 3 vowels are placed together?
(ii) the 3 vowels are not placed together?
(iii) consonatns and vowels do not appear alternately? Solution
(i) If the three vowels are placed together,
number of permutations = 5!
= 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1
= 120
number of arrangement of 3 vowels = 3!
= 3 ⋅ 2 ⋅ 1
= 6
The required number of permutations = 120 × 6
= 720
(ii) If the 3 vowels are not placed together,
number of permutations = 7!
= 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 5040
The required number of permutations = 5040 - 720
= 4320
(iii) If consonants and vowels do not appear alternately,
= 4!
= 3!
Number of ways consonants and vowels appear alternately = 4! × 3!
= 4 ⋅ 3 ⋅ 2 ⋅ 1 × 3 ⋅ 2 ⋅ 1
= 24 × 6
= 144
Number of ways consonants and vowels do not appear alternately = 5040 - 144
= 4896
9. Find the number of permutations of all the letters of the word PENGUIN in such a way that there are exactly 3 letters between 2 N's. Solution Case (1)
10. Find the number of permutations of all the letters of the word STRESSLESS in such a way that there are exactly 5 letters between:
(i) 2 E's. (ii) 2 S's.
Solution
(i) The letter must be arranged in one of the four forms.
E ★ ★ ★ ★ ★ E ★ ★ ★
★ E ★ ★ ★ ★ ★ E ★ ★
★ ★ E ★ ★ ★ ★ ★ E ★
★ ★ ★ E ★ ★ ★ ★ ★ E
in which 8 letters (5 S's, 1 T, 1 R, 1 L) other than 2 E's are to be put in star (★) position.
For each such form, the number of ways to put the 8 letters in star (★) positions is
8!⁄5! = 336
The required number of permutations = 4 ⋅ 336
= 1344
(ii) The letter must be arranged in one of the four forms.
S ★ ★ ★ ★ ★ S ★ ★ ★
★ S ★ ★ ★ ★ ★ S ★ ★
★ ★ ★ S ★ ★ ★ ★ ★ S
Each case, we consider 3 S's, T, R, L and 2 E's.
The number of ways to put the 8 letters in star (★) positions is 8!⁄3! 2!
= ⋅ 7 ⋅ 6 ⋅5 4 ⋅ 3!⁄3! 2 ⋅ 1
= 3360
The required number of permutations = 4 × 3360
= 13440