In this chapter, the concepts of "permutation" and "combination" are described in accordance with some counting principles. Counting techniques are indispensable
to apply probability when the sample space is finite and outcomes are equally likely. They are also beneficial and applicable to many areas of Mathematics,
Statistics, Science and Engineering.
5.1 Counting Principles
Suppose a coffee shop offers 2 choices of drinks (Tea and Coffee) and 3 choices of snacks (Cake, Doughnut and Sandwich). How many different choices are possible to
have a drink and a snack? We can see the complete list of all possible choices in the three diagram shown below.
In this problem, there are 2 ways to choose the type of drink. For each such choice, there are 3 ways to choose the type of snack. The number of ways to have a drink
and a snack is 6, which can be computed as 2 × 3 = 6.
Now, let us have a look at another example. Suppose a list of 5 topics is given in an essay contest. A student must select one of the topics on which to write a short
essay, and then select a different topic from the list for a long essay. How many ways can the topics be chosen for the two essays? In this example, there are 5 ways
to choose a topic for a short essay. After choosing one for the short essay, a long essay can be written on one of the remaining 4 topics. So the number of ways
to choose the topics is 5 × 4 = 20.
The two examples illustrates the following multiplication principle.
The Multiplication Principle
Suppose a task can be performed in m ways, and no matter how the task has been performed another task can then be performed in n ways. Then the number of
ways to perform these two tasks in succession is mn.
The principle can be extended to any finite number of such successive tasks.
Example 1.
Suppose that there are 6 roads between town A and town B, and that 4 roads between town B and town C. Find the number of ways a person can drive from A to C by passing
through B? Solution
There are 6 ways to drive from A to B, and for each such way there are 4 ways to drive from B to C.
So, the number of ways to drive from A to C through B is 6 × 4 = 24.
Example 2.
There are four blood types, namely A, B, AB and O. Blood can also be RH(+ve) or RH(-ve). A blood donor can be classified as either male or female. How many different
possible ways can a donor have his or her blood labeled? Solution
There are four possibilities for the blood type, 2 possibilities for the FH factor and 2 possibilities for the gender of donor.
So, the number of ways to label is 4 × 2 × 2 = 16.
Example 3.
There are 3 pictures nails on a wall. If there are 5 different pictures and each nail can hold only one picture, in how many different ways can the pictures be
hung on all the nails? Solution
Any one of the 5 pictures can be chosen for the first nail, then any one from the remaining four for the second, and finally any one from the remaining three
for the third.
The number of ways to choose the pictres for individual nails are 5, 4 and 3 respectively.
So, The number of ways to hang the pictures is 5 × 4 × 3 = 60.
Multiplication principle has been applied in solving counting problems in above examples. To introduce another counting principle, consider the following example.
Suppose a manufacturer makes shirts in 5 different sizes S, M, L, XL and XXL. Shirts having sizes S, M and L are made in 4 different designs, while those having sizes
XL and XXL are in 3 different designs. If each design has 5 different color schemes, how many different types of shirts are possible to make?
We need to consider the two cases as follows:
(i) Shirts have sizes S, M or L.
(ii) Shirts have sizes XL or XXL.
For the first case, the number of types is 3 × 4 × 5 = 60.
For the second case, the number of types is 2 × 3 × 5 = 30.
So the total number of types must be 60 + 30 = 90.
Notice that the two cases we mentioned above have no arrangement falls into some of these cases. The principle we applied above generally be stated as follows:
The Addition Principle
Suppose there are k pairwise disjoint cases, into which the elements in a counting problem fall. If there are n1 elements in the first case,
n2 elements in the second case, n3 elements in the third case, ..., and nk elements in the kth
case, then the number of elements in the problem is n1 + n2 + n3 + ... + nk.
Example 4.
How many different numbers can be formed using the digits 3, 5, 6, 8 and 9 in such a way that the numbers contain two or three digits without any repetition ? Solution
The two-digit numbers can be formed in 5 × 4 = 20 ways.
The three-digit numbers can be formed in 5 × 4 × 3 = 60 ways.
So, there are 20 + 60 = 80 different numbers.
Example 5.
How many integers, having digit 5 only once, are there between 0 and 100 ? Solution
The integers, that we want to form, must be one of the followings:
(i) One-digit integer, namely 5
(ii) Two-digit integers having 5 as tens' digit ( ones' digit may be anyone except 5)
(iii) Two-digit integers having 5 as ones' digit ( tens' digit may be anyone except 0 and 5)
For the first case, the number of integers = 1.
For the second case, the number of integers = 1 × 9 = 9.
For the third case, the number of integers = 8 × 1 = 8.
The required number of integers = 1 + 9 + 8 = 18.
Factorial Notation
The problem in example 3 can be modified as follows, to introduce a notation. There are 7 picture nails on a wall. If there are 7 different pictures and each nail can hold only one picture, how many different ways can the pictures be hung
on all the nails?
By the multiplication principle, the picture can be hung in 7 × 6 × 5 × 4 × 3 × 2 × 1 different ways. The number is the
product of the first seven positive integers and can be expressed as 7!. In general, n! ( n factorial or factorial n) stands for
the product of the first n positive integers n, (n - 1), (n - 2), ..., 1 if n is a positive integer. We defined 0! to be 1.
If n is a positive integer, n! = n(n - 1) (n - 2) ... 1.
0! = 1.
Notice that n! = n ⋅ (n - 1)! n! = n ⋅ (n - 1) ⋅ (n - 2)!
and so on.
For examples, 4! = 4 ⋅ 3 ⋅ 2 ⋅ 1
$$\small{= \underbrace{4 \cdot (3 \cdot 2 \cdot 1)}_{= 4 \cdot 3!} = \underbrace{4 \cdot 3 \cdot (2 \cdot 1).}_{= 4 \cdot 3 \cdot 2!} }$$
1. A store sells men's wear. It has 6 kinds of shirts, 4 kinds of pants and 3 kinds of coats. If a man wants to buy a shirt, a pant and a coat,
how many ways can this be done? (Assume that any choice meets his requirement.) Solution
Number of ways = 6 × 4 × 3 = 72
Therefore, there are 72 ways a man can buy a shirt, a pant and a coat from the store.
2. A television news director wishes to use three of the 7 news stories on an evening show. How many possible ways can the program be set up, if the
three stories are to be classified as the lead story, the second story and the closing story? Solution
The lead story = 7 ways
The second story = 6 ways
The closing story = 5 ways
The required number of ways = 7 × 6 × 5 = 210 ways
3. If a garage door opener has a 10-digit keypad, containing 0, 1, 2, ..., 9, and the code to open the door must be a 4-ditit code, how many codes are
possible to create? Solution
The code to open the carage door is 4-digit code.
10 options for the first digit.
10 options for the second digit.
10 options for the third digit.
10 options for the fourth digit.
∴ The total number of possible codes is: 10 × 10 × 10 × 10 = 10000
4. There are 3 restaurants X, Y and Z, we can go for lunch, in a certain area. Suppose that no two restaurants have the same menu, and the numbers
of choices for appetizer, main dish and dessert available are shown in the table. Find the number of ways to have a lunch, consisting of an appetizer,
a main dish and a dessert.
Restaurants
No. of Appetizers
No. of Main dishes
No. of Desserts
X
4
10
2
Y
3
8
5
Z
5
12
3
Solution
The number of ways to have lunch for restaurant X = 4 × 10 × 2 = 80
The number of ways to have lunch for restaurant Y = 3 × 8 × 5 = 120
The number of ways to have lunch for restaurant Z = 5 × 12 × 3 = 180
The required number of ways = 80 + 120 + 180 = 380
5. A registeration code consists of two of the 12 different capital letters A, B, C, ..., L, followed by one of the ten digits 0, 1, 2, ..., 9, for example
ID5. How many codes are possible to generate:
(a) if the repetition of the letters is allowed?
(b) if the repetition of the letter is not allowed?
(c) if two letters in the codes must be the same?
(d) if two letters are different, but must be both vowels or both consonants? Solution
If repetition of letter is allowed, there are 12 option for the first letter, 12 options for the second letter and 10 options for the digit.
∴ the number of ways = 12 × 12 × 10 = 1440 codes.
If repetition of letter is not allowed, there are 12 options for the first letter and 11 options for the second letter, and 10 options for the digit.
∴ The number of ways = 12 × 11 × 10 = 1320 codes
If two letters in the code must be the same, then 12 options for the repeted letter and 10 options for the non-repeted digit.
∴ The number of ways = 12 × 10 = 120 codes.
There are two cases to consider : the first letter is a vowel and the second letter is a vowel, or the first letter is a
consonant and the second letter is a consonant.
If the first letter is a vowel and the second letter is a vowel, the possilility is 3 × 2 × 10 = 60 codes
If the first letter is a consonant and the second letter is a consonant, the possibility is 9 × 8 × 10 = 720
The required number of ways = 60 + 720 = 780 codes
6. (a) Express
1⁄5⋅4⋅3 in the factor form.
(b) Evaluate 2 ⋅ 9! + 82⋅8!. Solution