PERMUTATIONS & COMBINATIONS

Factorial Notation

The continued product of first n natural numbers is called n factorial or factorial n.
It is denoted by | n or n!

Thus, | n or n! = 1. 2. 3. 4. .... (n -1) . n
                       = n (n -1)(n -2). .... 3.2.1          (in reverse order)

Meaning of zero factorial

According to the above definition, makes no sense. However we define 0! = 1

Note. When n is a negative integer or a fraction, n factorial is not defined.

Permutations and Combinations

Combination

Each of the groups or selections which can be made by taking some or all of a number of things without reference to the order of things in each group is called acombination.
For example, choosing two fruits out of a basket containing 4 oranges and 5 bananas - three combinations are possible - two oranges, two bananas or one orange and one banana.

Permutation

Each of the arrangements which can be made by taking some or all of a number of things is called permutation.
For example, the letters of word CAT can be arranged in six different ways
     CAT, CTA, ACT, ATC, TAC, TCA

Sometimes, students may be confused whether combination or permutation is being talked about. Certain key words/phrases can be helpful in deciding.
Combinations: Selection, choose, make group, distribute, committee, geometric problems.
Permutations: Arrangements, standing in a line, seated around a table, problems on digits or letters of a word.

Fundamental Theorem

1. Multiplication Principle (Principle of Association).

If a certain thing can be done in m ways, and if when it has been done, a second thing can be done in n ways, then the total number of ways in which two things can be done is mn.
For example, if there are eight top heroes and 4 top heroines, a film producer can choose from 8 x 4 = 32 pairs.

2. Addition Principle:

If there are two jobs which can be done in m and n ways respectively, then either of two jobs can be done in m + n ways.
For example, if the film producer has limited budget and he can afford either a top hero or a top heroine but not both, then he can choose in 8 +4 = 12 ways.

Example

Three persons enter a railway carriage, where there are 5 vacant seats. In how many ways can they seat themselves?

Solution

First man can sit on any of 5 vacant seats. Then the second can sit on any of 4 vacant seats left. And the third can sit on any of 3 vacant seats left. Hence by fundamental principle of counting, the required number of ways is 5 x 4 x 3 = 60.

Formula for P(n,r)

The number of permutations of n different things taken r at a time is given by

P(n, r) = n. (n -1). (n -2) ... (n -r +1) = n! / (n -r)!

Note. ⁿ P_n = n (n -1) ... (n - n +1) = n (n -1) ... 1 = n!

Example

^1)  5P₅ = 5. 4. 3. 2. 1 = 120

2) In how many ways can the letters of the word WONDERFUL be arranged?

    SOLUTION: 

                Since there are 9 distinct letters in WONDERFUL, the required number of permutations is

                ⁹P₉ = 9! = 9. 8. 7. 6. 5. 4. 3. 2. 1 = 362880

3) Find the number of divisors of the number 36000.

    Solution: Factorising the given number, we find 36000 = 2⁵ . 3². 5³. This means that any divisor of 36000 is of the type 2^a. 3^b. 5^c where a can take values 0, 1, 2, 3, 4, 5; b can take values 0, 1, 2; c can take values 0, 1,2, 3. Hence number of divisors is 6 x 3 x 4 = 72. Note that both 1 and 36000 are counted among 72 divisors.

Permutations under restrictions

• Number of permutations of n distinct objects when a particular object is not taken in any arrangement is ^n-1P_r
• Number of permutations of n distinct objects when a particular object is always included in any arrangement is r.^n-1P_r-1.

Example

In how many ways can 4 books on Mathematics and 3 books on English be placed on a shelf so that books on the same subject always remain together?

Solution

Consider the 4 books on Mathematics as one big book and 3 books on English as another big book. These two can be arranged in 2! ways. In each of these arrangements, 4 books on Mathematics can be arranged among themselves in 4! ways and 3 books on English can be arranged among themselves in 3! ways.
Hence, the required number of ways = 4! 3! 2! = 288.

Permutations of objects which are not all different

• The number of permutations of n things taken all together, when p of the things are alike of one kind, q of them alike of another kind, r of them alike of a third kind and the remaining all different is n! / [p! q! r!]
• The number of permutations of n objects, of which m are of one kind and the rest n -m of another kind, taken all at a time is n! / [m! (n-m)!]

Example

In how many ways can the letters of the word permutations be arranged such that

1. there is no restriction
2. P comes before S
3. words start with P and end with S
4. T's are together
5. vowels are together
6. order of vowels remains unchanged?

Solution

The given word has 12 letters -two Ts and 10 different letters.

1. Total number of arrangements is12!/2! = 6. 11!
2. Out of above, P comes before S in half the arrangements. Hence required number of arrangements = 3. 11!
3. As position of P and S is fixed, remaining 10 letters (that is, two T's and eight other different letters) can be arranged in 10!/2! = 5. 9! ways.
4. Considering two T's as a block, we have to arrange 11 different things, which can be done in 11! ways.
5. Considering the five vowels in given letter -E, U, A, I, O as a block, we have 8 things having 2 alike things (T's). So this can be arranged in 8!/2! = 4. 7! ways. Now within the block, 5 different vowels can be arranged in 5! ways. Hence required number of arrangements is 4. 7!5! ways.
6. If order of five vowels has to remain unchanged, we can consider them like five alike things, so only one ordering is possible. Thus we have 12 things of which 2 are alike and 5 are alike. Hence required number of arrangements is 12!/[2! 5!]

Circular Permutations

In general, the number of ways of arranging n objects around a round table is (n-1)!

An easier way of thinking is that we "fix" the position of a particular person at the table. Then the remaining n -1 persons can be seated in (n-1)! ways. Done!

Thus the number of ways of arranging n persons along a round table so that no person has the same two neighbours is(n-1)!/2

Similarly in forming a necklace or a garland there is no distinction between a clockwise and anti clockwise direction because we can simply turn it over so that clockwise becomes anti clockwise and vice versa. Hence the number of necklaces formed with n beads of different colours = (n-1)!/2

Example

1. A cat invites 3 rats and 4 cockroaches for dinner. How many seating arrangements are possible along a round table? 

1. SOLUTION: "Fix" the position of the cat. Now remaining 3 rats and 4 cockroaches can be seated in 7!/(3! 4!) = 35 ways.

Combinations - Formula for ⁿC_r

The number of combinations of n different things taken r at a time is
                   ⁿC_r = n!/[ r! (n -r)!]

Corollaries:

1. ⁿC_r = [n (n -1)(n -2).....upto r factors]/r!
2. ⁿC_n = 1
3. ⁿC₀ = 1
4. ⁿC_r = ⁿC_{n -r}

Combinations - Some important results

1. If out of n different things, any number of items can be chosen, it can be done inⁿC₀ +ⁿC₁ +ⁿC₂ +... +ⁿC_n ways. Alternatively, any of n items may or may not be chosen. Hence number of selections = 2×2×...n times = 2ⁿ
   => ⁿC₀ +ⁿC₁ +... +ⁿC_n = 2ⁿ.
   It can be shown that ⁿC₀ +ⁿC₂ +ⁿC₄ +... = ⁿC₁ +ⁿC₃ +ⁿC₄ +... = 2^n-1.
2. Out of n different things, at least one (or more) can be chosen in 2ⁿ -1 ways.
3. Number of combinations of n different things taken r at a time when p particular things always occur is ^{n -p}C_{r -p}. Number of permutations of these is ^{n -p}C_{r -p}.r!
4. Number of combinations of n different things taken r at a time when p particular things never occur is ^n-pC_r. Number of permutations of these is ^{n -p}C_r.r!
5. The number of ways in which m +n different things can be divided into two groups containing m and n things respectively is (m +n)!/[m!n!]. The reason is that whenever you choose a group of m out of m +n, a group of n is automatically left behind. Number of combinations of m +n things taken m at a time is
             ^{n +m}C_m = (m +n)!/[m! (m +n -1)!] = (m + n)!/[m! n!]
6. If subgroups are equal i.e. n = m, then 2m things can be divided into two groups of m each in (2m)!/(m!)² ways. If you distribute things to two persons, then this formula gives number of subdivisions. If it is possible to interchange the two groups then number of divisions is (2m)!/[(m!)².2!]
7. Number of division of m +n +p things into groups of m, n, p things respectively is (m +n +p)!/[m!.n!.p!]
8. If 3m things are divided into 3 equal groups, then number of divisions is (3m)!/(m!)³ and if the groups are interchangeable, the number of divisions is (3m)!/[(m!)³.3!]
9. If there are p +q +r things, where p things are alike, q things are alike and r things are alike, a non-empty selection can be made in (p +1)(q +1)(r +1) -1 ways as 0, 1, 2, ..., p items of p may be chosen; 0, 1, 2, ..., q items of q may be chosen etc.
10. If there are p +q +r things, where p things are alike, q things are alike and remaining r are all different, then a non-empty selection can be made in (p +1)(q +1). 2r -1 ways. (Prove it!)

Example

In how many ways can final eleven be selected from 15 cricket players if

1. there is no restriction
2. one of them must be included
3. one of them, who is in bad form, must always be excluded
4. two of them being leg spinners, one and only one leg spinner must be included?

Solution

1. 11 players can be selected out of 15 in ¹⁵C₁₁ ways
   = ¹⁵C₄ = (15.14.13.12) / (1.2.3.4) = 1365 ways.
2. Since a particular player must be included, we have to select 10 more out of remaining 14 players. This can be done in
   ¹⁴C₁₀ = ¹⁴C₄ = (14.13.12.11)/(1.2.3.4) = 1001 ways.
3. Since a particular player must be always excluded, we have to choose 11 players out of remaining 14. This can be done in
   ¹⁴C₁₁ ways = ¹⁴C₃ = (14.13.12)/(1.2.3) = 364 ways.
4. One leg spinner can be chosen out of 2 in² C₁ = 2 ways. Then we have to select 10 more players out of 13 (because second leg spinner can't be included). This can be done in
   ¹³C₁₀ ways = ¹³C₃ = (13.12.11)/(1.2.3) = 286 ways.
   Thus required number of combinations = 2×286 = 572