Page 81 - DMTH404_STATISTICS

Unit 6: Probability

6.2 Counting Techniques Notes

Counting techniques or combinatorial methods are often helpful in the enumeration of total
number of outcomes of a random experiment and the number of cases favourable to the
occurrence of an event.

6.2.1 Fundamental Principle of Counting

If the first operation can be performed in any one of the m ways and then a second operation can
be performed in any one of the n ways, then both can be performed together in any one of the m
 n ways.
This rule can be generalised. If first operation can be performed in any one of the n ways, second
1
operation in any one of the n ways, ...... kth operation in any one of the n ways, then together
2 k
these can be performed in any one of the n ´ n × ...... × n ways.
1 2 k
6.2.2 Permutation

A permutation is an arrangement of a given set of objects in a definite order. Thus composition
and order both are important in a permutation.
(a) Permutations of n objects
The total number of permutations of n distinct objects is n!. Using symbols, we can write
n
P = n!, (where n denotes the permutations of n objects, all taken together).
n
Let us assume there are n persons to be seated on n chairs. The first chair can be occupied
by any one of the n persons and hence, there are n ways in which it can be occupied.
Similarly, the second chair can be occupied in n - 1 ways and so on. Using the fundamental
principle of counting, the total number of ways in which n chairs can be occupied by n
persons or the permutations of n objects taking all at a time is given by:
n
P = n(n - 1)(n - 2) ...... 3.2.1 = n!
n
(b) Permutations of n objects taking r at a time
In terms of the example, considered above, now we have n persons to be seated on r chairs,
where r £ n.
n
Thus, P = n(n - 1)(n - 2) ...... [n - (r - 1)] = n(n - 1)(n - 2) ...... (n - r + 1).
r
On multiplication and division of the R.H.S. by (n - r)!, we get

( n n - 1 )(n - ) 2 .... (n r- + 1 )(n r- )! ! n
n
P = =
r
-
(n r- )! (n r )!
(c) Permutations of n objects taking r at a time when any object may be repeated any number of times
Here, each of the r places can be filled in n ways. Therefore, total number of permutations
is n .
r
(d) Permutations of n objects in a circular order
Suppose that there are three persons A, B and C, to be seated on the three chairs 1, 2 and 3,
in a circular order. Then, the following three arrangements are identical:

LOVELY PROFESSIONAL UNIVERSITY 73