Mathematics : Permutation and Combinations

Permutation and Combination: Notes & Important Questions

Permutation and combination

Permutations and combinations are the basic ways of counting from a given set, generally without replacement, to form subsets.

Permutation

Permutation of an object means the arrangement of the object in some sequence or order.

Theorem 1

 The total number of permutations of a set of n objects taken r at a time is given by

P( n,r)  =  n (n- 1)(n- 2)….….(n- r+1)     (n ≥ r)

Proof:

The number of permutations of a set of `n’objects taken r at a time is equivalent to the number of ways in which r positions can be filled up by those n objects . When first object is filled then we have (n-1) choices to fill up the second position. Similarly, there are (n- 2) choices fill up the third position and so on.

Therefore, P(n,r)  =  n (n- 1) (n- 2) …….. (n – r +1)

                             =n(n−1)(n−2)…….(n−r+1)(n−r)…3.2.1(n−r)……3.2.1n(n−1)(n−2)…….(n−r+1)(n−r)…3.2.1(n−r)……3.2.1

                           =  n!(n−r)!n!(n−r)!

Permutation of objects not all different

The permutation of objects taken all at a time when P of the objects are of the first kind, q of them are of the second kind, of them are of the third kind and the rest all are different.

The total number of permutations =n!p!q!r!n!p!q!r!

Circular permutation

Circular Permutation: The number of ways to arrange distinct objects along a fixed line 

The total number of permutation of a set of n objects arranged in a circle is P = (n -1)!

Permutation of repeated things

The permutation of the n objects taken r at a time when each occurs a number of times and it is given  by  P = n^r

Example 1

How many numbers of three digits can be formed from the integers 2,3, 4,5,6? How many of them will be divisible by 5?

Soln:

For the three digits numbers, there are 5 ways to fill in the 1^st place, there are 4 ways to fill in the 2^nd place and there are 3 ways to fill in the 3^rd place. By the basic principle of counting, number of three digits numbers = 5 * 4 * 3 = 60.

Again, for three-digit numbers which are divisible by 5, the number in the unit place must be 5. So, the unit place can be filled up in 1 way. After filling up the unit place 4 numbers are left. Ten’s place can be filled up in 4 ways and hundredths place can be filled up in 3 ways. Then by the basic principle of counting, no.of 3 digits numbers which are divisible by 5 = 1 * 4 * 3 = 12.

Example 2

How many numbers of at least three different digits can be formed the integers 1, 2, 34, 5, 6,?

Soln

Numbers formed should be of at least 3 digits means they may be of 3 digits, 4 digits, 5 digits or 6 digits.

There are 6 choices for the digit in the units place. There are 5 and 4 choices for digits in ten and hundred’s place respectively.

So, the total number of ways by which 3 digits numbers can be formed = 6.5.4 = 120

Similarly, the total no.of ways by which 4 digits numbers can be formed = 6.5.4.3 = 360.

the total no. of ways by which 5 digits numbers can be formed = 6.5.4.3.2 = 720.

The total no.of ways by which 4 digits numbers can be formed = 6.5.4.3.2.1 = 720.

So, total no.of ways by which the numbers of at least 3 digits can be formed = 120 + 360 + 720 + 720 = 1920

Example 3

In how many ways can four boys and three girls be seated in a row containing seven seats

1. if they may sit anywhere
2. if the boys and girls must alternate
3. if all three girls are together?

a.

Soln:

If the boys and girls may sit anywhere, then there are 7 persons and 7 seats. 7 persons in 7 seats can be arranged in P(7,7) ways.

= 7!(7−7)!7!(7−7)! = 7!0!7!0! = 7∗6∗5∗4∗3∗2∗117∗6∗5∗4∗3∗2∗11 = 5,040 ways.

b.

Soln:

If the boys and girls must sit alternately, there are 4 seats for boys and 3 for girls.

Here, for boys n = 4, r = 4

4 boys in 4 seats can be arranged in P(4,4) ways

= 4!(4−4)!4!(4−4)! = 4∗3∗2∗114∗3∗2∗11 = 24 ways.

Again. For girls n = 3, r = 3

3 girls in 3 seats can be arranged in P(n,r) i.e. P(3,3) ways.

= 3!0!3!0! = 3∗2∗113∗2∗11 = 6ways.

So, total no.of arrangement = 24 * 6 = 144 ways.

c.

Suppose 3 girls = 1 object, then total number of student (n) = 4 + 1= 5.

Then the permutation of 5 objects taken 5 at a time.

= P(5,5) = 5!(5−5)!5!(5−5)! = 5∗4∗3∗2∗115∗4∗3∗2∗11 = 120.

We know, 3 girls can be arranged themselves in P(3,3) different ways,

i.e. P(3,3) = 3!(3−3)!3!(3−3)! = 3 * 2 * 1 = 6 different ways.

Therefore, required of arrangements = 120 * 6 = 720.

Examples 4

In how many ways can eight people be seated in a round table if two people insisting sitting next to each other?

a.

Total number of objects = 4 + 4 = 8.

If they may sit anywhere, then it is the circular arrangements of 8 objects taken 8 at a time. So, the total number of permutation.

= (8 – 1)! = 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040.

b.

Art and Science students have to sit alternately in a round table. So, there are 4 seats for Art students and 4 for Science students.

4 art students at a round table can be arranged in 4 – 1! ways.

= 3! = 3 * 2 * 1 = 6 ways.

Again. 4 science students can be arranged in P(4,4) ways, i.e. 4! Ways = 4 * 3 * 2 * 1 = 24 ways.

So, total no.of arrangement = 6 * 24 = 144 ways.

 Combinations

The combination means a collection of an object without regarding the order of arrangement. The total number of combinations of n objects taken r at a time C(n,r ) is given by C(n,r) =  n!(n−r)!r!n!(n−r)!r!

Examples 5

From 4 mathematician, 6 statisticians and 5 economists, how many committees consisting of 3 men and 2 women are possible?

Soln:

2 members can be selected from 4 mathematicians in C(4,2) in different ways.

2 members can be selected from 6 statisticians in C(6,2) in different ways.

2 members can be selected from 5 economics in C(5,2) in different ways.

Therefore, total number of committees = C(4,2) * C(6,2) * C(5,2) = 6 * 15 * 10 = 900.

Examples 6

1. If C(20, r+ 5) = C (20, 2r  -7) find  C( 15,r)
2. if  C(n, 10)  +  C(n,9)  =  C( 20,10)  find n and C(n, 17)
3. solve for  n the equation C(n+ 2,4) = 6 C(n, 2)

a.

Given C(20,r + 5) = C(20,2r – 7)

Then r + 5 = 2r – 7      [if C(n,r) = C(n,r’) then r = r’]

Or, r = 12.

So, C(15,r) = C(15,12) = 15!(15−12)!.12!15!(15−12)!.12! = 455.

b.

Given. C(n,10) + C(n,9) = C(20,10)

Or, C(n + 1,10) = C(20,10)     [if C(n,r)+ C(n,r – 1) = C(n + 1, r)]

So, n + 1 = 20

So, n = 19.

Again, C(n,17) = C(19,17) = 19!(19−17)!.17!19!(19−17)!.17! = 171.

c.

C(n + 2,4) = 6 C(n,2)

Or, (n+2)!(n−2)!.4!(n+2)!(n−2)!.4! = 6. n!(n−2)!.2!n!(n−2)!.2!à(n+2).(n+1).n!(n−2)!.4!(n+2).(n+1).n!(n−2)!.4! = 6n!(n−2)!.26n!(n−2)!.2.

Or, (n+2)(n+1)4∗3∗2∗1(n+2)(n+1)4∗3∗2∗1 = 3

Or, n2 + 3n + 2 = 72

Or, n2 + 3n – 70 = 0

Or, (n + 10)(n – 7) = 0

Either, n = - 10 or, n = 7.

n = - 10 is not possible.

So, n = 7.