Study Notes for CAT 2021: Permutation and Combination

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.

Factorial

The product of the numbers starting from 1 up to a number ‘n’ is known as the factorial of number ‘n’.

It means n! = 1x2x3x4x5x6……..x(n-2)x(n-1)xn

1! = 1

2! = 1x2 = 2

3! = 1x2x3 = 6

4! = 1x2x3x4 = 24

5! = 1x2x3x4x5 = 120

Key points related to Factorial:

0! & 1! are equal to 1.

We can’t find factorial of a negative number.

Application of factorial:

Factorial has the most common application in an arrangement. Let us understand how factorial helps in arranging things.

Suppose we have 5 persons and we want to arrange them in 5 vacant places. Then we will start with the first place. We can choose 1 person out of 5 for the first place. We can do that in 5 ways.

Now only 4 seats are vacant and 4 persons are left. We will choose 1 person out of 4 for second place now. We can do that in 4 ways.

In the same manner, for the third place, 3 ways, for the fourth place, 2 ways, and for the last vacant place only 1 way of selection is possible. As we know that we have to do all of these activities, so we will multiply all these ways to get the final answer for getting the different ways of arrangement.

So total ways = 5x4x3x2x1 which is 5!

         = 120

Or we can say that whenever we have to arrange ‘n’ things at ‘n’ places then total arrangements that can be made will always be equal to n!

Q.1) In how many ways can the letters of the word PATNA be rearranged?

Solution: PATNA has total 5 words. So we will arrange 5 letters at 5 places in 5! = 120 ways.

But in this question, A is coming twice. Whenever any letter is more than once in the word, then we have to divide by the number of repetitions of the word. So we have to divide the total 120 ways by 2!= 2.

So total different words that can be made will be 120/2 = 60.

Direct answer: 5!/2! = 60

Q.2) How many different words can be made using letters of PATNA starting with P?

Solution: PATNA has total 5 words. According to the question, P is fixed at first place, so we will arrange remaining 4 letters at 4 places in 4! = 24 ways. But in this question, A is coming twice, so we have to divide the total 24 ways by 2!= 2. So total different words starting from P will be 24/2 = 12.

Direct answer: 4!/2! = 4*3 = 12

• Whenever we have to choose certain things from a group and no arrangement is done. In that case combination comes into picture. So let us see concept of combination.

Combination

In combination, we select the things at random & check out the different possible ways of selection. So this is a one step process. Combination is also known as collection. The formula used for combination is ⁿC_r

ⁿC­_r = n! / [r! x (n-r)!]

ⁿC­_r = [n x (n-1) x (n-2) x (n-3) x…...x(n-r+1) x (n-r) X…....x 1] / [1x 2 x 3….. x r] X [(n-r) x……..3 x 2 x 1]

ⁿC­_r = [n x (n-1) x (n-2) x (n-3)….. x (n-r+1)] / [1x 2 x 3….. x r]

For example: ¹²C­₂  = 12!/ [2! X (12-2)!] = 12!/ (2! X 10!) = [12 x 11] / [1 x 2] = 66

                                  ⁵C₂ = [5 x 4] / [1 x 2] = 10

ⁿC_r = ⁿC_(n-r)

For example:  ⁵C₃ = [5 x 4 x 3] / [1 x 2 x 3] = [5 x 4]/[1 x 2] = ⁵C₂ = 10

                                   ¹⁰C₇ = ¹⁰C₃ = [10 x 9 x 8]/[1 x 2 x 3] = 120

Q.3) In a class there are 4 boys and 5 girls. In how many different ways a class monitor can be chosen?

Solution: As we can clearly see that we have to choose a student from total 9. So we will use combination concept here which will give us the answer as ⁹C₁ = 9/1 = 9

Q.4) In a class there are 4 boys and 5 girls. In how many different ways a boy and a girl can be selected for group leaders of two groups?

Solutions: We have to choose a boy from 4 boys and a girl from 5 girls for two groups.

So total ways of selection = ⁴C₁x⁵C₁ = 4x5 = 20

Q.5) In how many different ways a cricket team can be selected from total 16 players?

Solution: We need to select 11 players from total 16 players.

So the answer will be ¹⁶C₁₁ = 16!/5!*(16-5)! = 16!/5!*11! = (16*15*14*13*12)/(1*2*3*4*5) = 4368

Q.6) An urn contains 5 red and 3 blue balls. In how many different ways, 2 red and 1 blue balls can be drawn?

Solution: The urn contains 5 red and we want 2 red balls. So ways of selecting red balls =⁵C₂ = 10

Similarly ways of selecting 1 blue ball from 3 blue balls = ³C₁ = 3

So total ways to select 2 red and 1 blue ball will be = 10*3 = 30

Q.7) In how many different ways a team of 11 can be selected from 15 players if 2 particular players are never selected?

Solution: It is given that 2 particular players are never selected. So we will do selection from rest of the players which means we will select 11 players out of 13 players.

So total ways of selection = ^(15-2)C₁₁ = ¹³C₁₁ = ¹³C₂ = (13*12)/(1*2) = 78

Q.8) In how many different ways a team of 11 can be selected from 15 players if 2 particular players are always selected?

Solution: It is given that we have to select two particular players always which means that we have choice of selection only for remaining 9 players and the possible options are only 13.

So total ways of selection = ^(15-2)C_(11-2) = ¹³C₉ = ¹³C₄ = (13*12*11*10)/(1*2*3*4) = 715

• Whenever we have to choose certain things from a group and arrangement of those chosen things is to be done. In that case permutation comes into picture. So let us see concept of permutation.

Permutation

In permutation, we select the things and then arrange them to check out different possible ways of arrangement. So basically permutation is a two-step process.

The formula used for permutation is ⁿP_r = n!/(n-r)!

Suppose we have 5 persons and we have to arrange them on 3 vacant places. Then first of all, we will choose 3 persons from 5. We can do that in ⁵C₃ different ways. After choosing 3 persons, we will have to arrange them on the 3 vacant places, for that we will use factorial concept. The total ways to arrange 3 persons on 3 places are 3!

So total ways to arrange 3 persons from total 5 on 3 vacant places will be:

 ⁵C₃*3! = ⁵C₂*3! = 5!/(2!*3!) * 3! = 5!/2! = 60 ways.

Q.9) A wicket-keeper and a bowler are to be chosen out of a team having 11 players. In how many different ways we can do this?

Solution: First of all, we will select 2 players from total 11 players. The ways of selection are ¹¹C₂ = (11*10)/(1*2) = 55. After doing selection, we can arrange 2 players on 2 different positions in 2! = 2 ways. So total ways of selecting a wicket-keeper and a bowler = ¹¹C₂ *2! = 55*2 = 110

Direct answer: ¹¹P₂ = 110

Q.10) In how many ways can the letters of the word EQUATION be arranged so that all the vowels come together?

Solution: In word ‘EQUATION’, we have 5 vowels (E,U,A,I,O) and 3 consonants (Q,T,N). According to question, all five vowels should come together so we will assume these 5 vowels to take one place and other 3 consonants will be arranged on 3 places, so total 4 places.

So ways to arrange these on 4 places will be 4! = 24

One important thing is that we can arrange the vowels order as well and we can do that in 5!= 120 ways.

So total ways = 24*120 = 2880

Direct answer: 4!*5! = 24*120 = 2880

Q.11) There are 7 candidates for 4 different posts. In how many ways we can fill the posts?

Solution: First of all, we will select 4 candidates out of total 7 candidates. The ways of selection are,

⁷C₄ = ⁷C₃ = (7*6*5)/(1*2*3) = 35

After doing selection, we can arrange 4 candidates for 4 different posts in 4! ways = 24 ways.

So total possible number of ways to fill the posts = 35*24 = 840

Direct answer: ⁷P₄ = (7*6*5*4) = 840

Q.12) Twenty students are participating in a race. In how many ways can the first three prizes be won?

Solution: First of all, we will select 3 candidates from total 20 candidates. The ways of selection are,

 ²⁰C₃ = (20*19*18)/(1*2*3) = 1140

After doing selection, we can arrange 3 candidates on 3 positions in 3! = 6 ways.

So total possible number of ways in which the first three prizes can be won = 1140*6 = 6840.

Direct answer: ²⁰P₃ = (20*19*18) = 6840 ways

Key points related to Permutation & Combination:

• Whenever we want to arrange n things at n places, we have total n! ways of arrangement.
• Whenever we have to select r things out of n, we have total ⁿC_r ways of selection.
• Whenever we have to select r things from n and then arrange those r things at r places, we have total ⁿP_r ways.
• ⁿC_r = n! / [r! x (n-r)!] 
• ⁿC_r = nC_(n-r)
• ⁿP_r = n!/(n-r)!

=======================

 Subscribe NOW to Online Classroom Program and get:

The benefits of subscribing Online Classroom Program are:

• Structured Live Courses with a daily study plan
• Complete Access to all the running and upcoming courses of all CAT & other MBA Entrance Exams (IIFT, XAT, SNAP, TISSNET, MICAT, MH-CET-MBA, CMAT, NMAT etc.)
• NO NEED to purchase separate courses for different MBA exams
• Prepare with India's best Faculty with a proven track record (7 faculties with decades of experience)
• Complete Doubt Resolution by Mentors and Experts 
• Performance analysis and Report card to track improvement

To SPEAK to our counsellors, please call us on 9650052904

Sahi Prep Hai Toh Life Set Hai!