1.9 Permutations and Combinations:

1.9.1 Permutations

Problem : A team has 10 players. Only six can fit into one photo frame. Manager has to be in each of the photo session. A photographer was asked to give an estimate for all the different combinations of photos. A photo with frame costs Rs.22. Find out the estimate given by photographer to the Manager.

Problem : In a hexagon how many triangles can be formed?

Is it not interesting to solve the above problems?

Introduction:

We have learnt that the sum of 1^st ‘n’ natural numbers is given by

= 1+2+3+4 …..+n =

What if we multiply these natural numbers instead of adding them?

1*2=2

1*2*3 =6

1*2*3*4 = 24…

We use the notation n!( called ‘n factorial’) to denote the product of ‘n; consecutive natural number from 1.

n!= 1*2*3*4….*n

What do we observe?

1! =1

2!= 1*2=2=2*1!

3!=1*2*3=6 =3*2!

4! =1*2*3*4 = 24= 4*3!

n! = n*(n-1)*(n-2)*(n-3)*…………3*2*1=n*(n-1)!

n! = n*(n-1)! Or n =

1.9.1 Example1 : Let A , B and C be students of your class . You are asked to arrange them in rows as follows:

1. with rows of 2 students

2. with rows of 3 students

How many arrangements can you make in each of the case?

Working:

1.9.1.1: Arrange 2 rows with two students in each row

1.Let us ask A to stand first. We are left with B and C. We can ask B or C to stand behind A ( so we have 2 arrangements AB and AC)

2.Let us ask B to stand first. We are left with A and C. We can will ask A or C to stand behind B (so we have 2 arrangements BA and BC)

3.Let us ask C to stand first. We are left with A and B. We can ask A or B to stand behind C (so we have 2 arrangements CA and CB)

I position	A		B		C
II position	B	C	C	A	A	B

In all we have 6(=3*2) ways of arrangements: (AB, AC), (BA, BC), (CA, CB)

1.9.1.2: Arrange 3 rows with 3 students in each row:

1.Let us ask A to stand first. We are left with B and C. We can ask B or C to stand behind A( so we have 2 arrangements ABC and ACB)

2.Next let us ask B to stand first. We are left with A and C. We can ask A or C to stand behind B(so we have 2 arrangements BAC and BCA)

3.Next let us ask C to stand first. We are left with B and A. We can ask A or B to stand behind C (so we have 2 arrangements CAB and CBA)

I position	A		B		C
II position	B	C	A	B	C	A
III position	C	B	C	C	B	C

In all we have 6(=3*2) ways of arrangements: (ABC, ACB), (BAC, BCA), (CAB, CBA)

1.9.1 Example 2: Let us take the case of 4 students A, B, C and D in the above example. How many different Queues can you form?

1. With Queues of 2 students

2. With Queues of 3 students

How many arrangements can you make in each of the case?

Working:

1.9.1.2.1: Arrange Queues of 2 students

I position

II position

Totally we have 12(=4*3) ways of arrangements (AB, AC, AD),( BA, BC, BD),( CA, CB, CD),( DA, DB, DC

1.9.1.2.2: Arrange Queues of 3 students:

I position

II position

III position

We have:

6(=3*2) Queues with A in the front (ABC, ABD, ACB ACD, ADB, ADC )

6 Queues with B in the front (BAC, BAD, BCA, BCA, BDA, BDC)

6 Queues with C in the front (CAB, CAD, CBA, CBD, CDA, CDB)

6 Queues with D in the front (DAB, DAC, DBA, DBC, DCA, DCB)

Totally we have 24(=4*3*2) ways arrangements

The number of arrangements (‘permutations’) of ‘n’ things taken ‘r’ things at a time is denoted by _nP_r

Let us analyse our workings:

Examples	Total Number of students(n)	Number of students in the row(r)	Number of arrangements	Notation	Meaning
Example 1.1	3	2	6	₃P₂	Permutation of 3 objects taken 2 at a time
Example 1.2	3	3	6	₃P₃	Permutation of 3 objects taken 3 at a time
Example 2.1	4	2	12	₄P₂	Permutation of 4 objects taken 2 at a time
Example 2.1	4	3	24	₄P₃	Permutation of 4objects taken 3 at a time

Permutation is a way of arranging objects in an orderly way.

1.9.2 Fundamental Principles of counting:

Assume that you and your friend go to school together. Assume that there are 4 routes to go to your friend’s house from your house and 3 routes from your friend’s house to the school. Also, Assume that you have a pet dog ‘Jony’ which some times follows you.

Find out how many different routes, ‘Jony’ can take to reach your house from the school, via your friend’s house?

Note: There are 4 routes to reach your friend’s house from your house and there are 3 routes to reach school from your friend’s house.

‘Jony’ can take any of the three routes (A or B or C) from the school to reach your friends house. From your friend’ house it can reach your house in four ways (1 or 2 or 3 or 4).

The following table lists the different ways that ‘Jony’ can take to reach your house from the school via your friend’s house.

No	From School to friend’s house	From friend’s house to your house	Route
1	A	1	A-1
2		2	A-2
3		3	A-3
4		4	A-4
5	B	1	B-1
6		2	B-2
7		3	B-3
8		4	B-4
9	C	1	C-1
10		2	C-2
11		3	C-3
12		4	C-4

‘Jony’ can chose 12(=3*4) ways of reaching your house from the school.

Similarly there are 12 (=4*3) ways of reaching school from your house.

In summary, if an activity can be done in ‘m’ ways and another activity is done in ’n’ ways then the 2 activities together can be done in (m*n) ways.

To find the formula for number of arrangements (Permutations) possible among ‘n’ things with ‘r’ things taken at a time.

Method:

Let us assume that we have ‘n’ number of objects and ‘r’ number of boxes.

Let boxes be numbered as 1,2,3,….(r-1),r.

Our task is to fill these boxes by taking ‘r’ objects at a time from ‘n’ number of objects.

Box No.	1	2	3	……	(r-1)	r
No of ways	n	(n-1)	(n-2)		n-(r-2)	n-(r-1)

1. First box can be filled in n different ways.

2. Second box can be filled in (n-1) different ways.

3. Third box can be filled in (n-2) different ways.

…

r. r’th box can be filled in (n-r+1) different ways.

By fundamental principle, r boxes can be filled in

n*(n-1)*(n-2)*(n-3)…..(n-r+1) ways

This is the number of permutations of ‘n’ things taken ‘r’ at a time and is denoted by _nP_r

_nP_r = n*(n-1)*(n-2)*(n-3)…..(n-r+1) =======è(1)

By substituting r=n in the above equation we get

_nP_n = n*(n-1)*(n-2)*(n-3)…..(n-n+1)

= n*(n-1)*(n-2)*(n-3)…..*1

_nP_n =n!

Let us multiply and divide RHS of equation (1) by the same term (n-r)*(n-r-1)*…..3*2*1 we get

_nP_r = {n*(n-1)*(n-2)*(n-3)…..(n-r+1)* (n-r)*(n-r-1)*…..3*2*1}/{(n-r)*(n-r-1)*…..3*2*1}

= {n!= 1*2*3……*n and (n-r)! = 1*2*3….*(n-r)}

Since _nP_r= ,

Note:

_nP₁=

= n

_nP₁ =n

_nP₍_n-1)

= (Substitute r = (n-1) in _nP_r)

= n! (1!= 1)

_nP₍_n-1)= n!= _nP_n

(n-r)! = n!/_nPr{ _nP_r= n!/(n-r)! }

By substituting r=n in the above equation we get

= n!/_nPn

= n!/n! ( _nP_n= n! )

0! =1

We summarise the following:

n = n!/(n-1)!

_nP_n =n!

_nP₁ =n

_nP_(n-1)= n!= _nP_n

0! =1

1.9.2 Problem 1 : In how many ways the letters of the word COMPUTER can be arranged? How many of these begin with M?

Solution:

Since the number of letters in the word = 8, we can form 8!=40320 different words of 8 letters.

Position	1	2	3	4	5	6	7	8
Letters	M	Fill from letters among C,O,P,U,T,E,R

If M is fixed in the first place then we are left with (n=7) letters to fill the other 7 places.

Then, the number of possibilities are = 7! =5040 words

1.9.2 Problem 2: How many 3 digit numbers can be formed using the digits2,3,4,5and 6 without repetitions? How many of these are even numbers?

Solution:

We know _nP_r= : It is given that n=5(2,3,4,5,6) and r=3

Hundred	Ten	Unit
Choose From (2,3,4,5,6)

Number of 3 digit numbers which can be formed = ₅P₃ = = =60

Among these, even numbers are those ending with 2,4 and 6(unit place is 2 or 4 or 6)

Let us find out how many 3 digit numbers can be formed that ends with 2.

Hundred

Ten

Unit

Choose From (3,4,5,6)

Even numbers:

Since the unit place is already taken by 2, we can only have 3, 4,5and 6 in hundredth and tenth places.

Since 2 will always be in the units place, we only need to find all the 2 digit numbers possible with 3,4,5 and 6(r=2).

The number of 2 digit numbers that can be formed using (n=4) digits (3,4,5,6) are =₄P₂= = 4*3 = 12

So with 2 in units place we can have 12 3-digit numbers.

Similarly with 4 in units place we can have 12 3-digit numbers.

Similarly with 6 in units place we can have 12 3-digit numbers.

In all we can have 36(=12+12+12) even numbers.

1.9.2 Problem 3: How many 3 digit numbers can be formed using 0,1,2,3?

Solution:

Here n=4 and r=3.

The number of 3 digit numbers that can be formed are ₄P₃ = = 4!=24

However, in case of 3 digit numbers, a number starting with 0 can not be considered as a 3 digit number (012 is not a 3 digit number but it is a 2 digit number).

Hence from the result we need to subtract the number of 3-digit numbers starting with 0.

Let us find out the number of 3-digit numbers starting with 0 .So we have n=3( 1,2,3) and r=2

With 0 as the first digit, number of 3-digit numbers we can make=₃P₂ = 3! =6.

Thus we can make 18(=24-6) 3-digit numbers from 0,1,2,3.

1.9.2 Problem 4: In how many ways can 7 different books be arranged in a shelf? In how many ways can we arrange three particular books so that they are always together?

Solution:

Here n=7. So the number of ways these books can be arranged is 7! = 5040.

Let the books be A,B,C,D,E,F,G. It is said that three books need to be together. Let they be B, C and D. For easy understanding we can tie these 3 books together and call this bundle as H. So we are left with A,H,E,F,G(5 objects). These can be arranged in 5!=120 ways.

Since H is bundle of 3 books (B,C,D). The books in the bundle H themselves can be arranged in 3!=6 ways.

Thus we have 6*120=720 ways of arranging 7 books such that 3 books are always together.

1.9.3 Combinations:

1.9.3 Example 1 : Let A , B and C be students of your class. A photographer was asked to take photos such that:

1. Different combinations of 2 students in one snap shot

2. Different combinations of 3 students in a snap shot

How many shots does he need to take?

Working:

Example 1.1: Photo session for group of 2 students

It can be seen from the example 1.9.1.1.1 that, the following arrangements are possible

I position	A		B		C
II position	B	C	A	B	C	A

But for a photo session we notice that AB = BA, BC = CB, and CA=AC.

Though there are 6 arrangements possible, we only have 3 unique combinations (AB, BC, CA).

Example 1.2: Photo session for group of 3 students

It can be seen from the example 1.9.1.1.2 that, the following arrangements are possible

I position	A		B		C
II position	B	C	A	B	C	A
III position	C	B	C	C	B	C

But for a photo session all the 6 combinations are same.

Though there are 6 arrangements possible, there is only one unique combination (ABC).

1.9.3 Example 2: Let A B C D be 4 students in your class . A photographer was asked to take photos such that:

1. Different combinations of 2 students in one snap shot

2. Different combinations of 3 students in one snap shot

How many snap shots does he need to take?

Working:

Example 2.1: It can be seen from the example 1.9.1.2.1 that, the following 12 arrangements are possible

I position

II position

Notice that for a photo session AB=BA, AC=CA, AD=DA, BC=CB, BD=DB and CD=DC.

Though 12 arrangements are possible , we only have 6(=3*2) unique combinations (AB, AC, AD, BC, BD, CD).

Example 2.2: It can be seen from the example 1.9.1.2.2 that, the following 24 arrangements are possible

I position

II position

III position

Note for a photo session

ABC=BAC=ACB=BCA=CAB=CBA

ABD=ADB=BAD=DAB=DBA=BDA

ACD=ADC=CAD=DAC=DCA=CDA

BCD=BDC=CBD=CDB=DBC=DCB

are all same.

Though 24 combinations are possible, there are only 4 unique combinations. (ABC, ABD, ACD, BCD)

The number of combinations of ’n’ things taken ‘r’ things at a time is denoted by _nC_r

Let us analyse our results

Examples	Total Number of students(n)	Number of students Per shot	Number of combinations	Notation
Example 1.1	3	2	3	₃C₂
Example 1.2	3	3	1	₃C₃
Example 2.1	4	2	6	₄C₂
Example 2.2	4	3	4	₄C₃

Let us find the relationship between permutations(1.9.1) and combinations(1.9.3) using the examples 1 and 2 of Permutations and Combinations.

Examples	Number of students(n)	Number of students taken at a time(r)	Number of Permutations_nPr) (1.9.1)	Number of Combinations(_nC_r) (1.9.3)	_nP_r/_nC_r =
Example 1.1	3	2	6= ₃P₂	3=₃C₂	2=2!
Example 1.2	3	3	6= ₃P₃	1=₃C₃	6=3!
Example 2.1	4	2	12= ₄P₂	6=₄C₂	2=2!
Example 2.2	4	3	24= ₄P₃	4=₄C₃	6=3!

We notice that _nP_r= _nC_r* r! _nC_r=_nPr÷r!

Formula for number of combinations of ‘n’ things taken ‘r’ at a time:

In the example 2.1 discussed above we notice the following

(Permutations of ‘n’ things taken ‘r’ at a time)= (Selection (Combination) of ‘n’ things taken ‘r’ at a time)*(Arrangement of ‘r’ things)

_nP_r= _nC_r*_rPr

1.9.3 Problem 1: If _nP_r = 336 and _nC_r=56 find n and r

Solution:

We know _nP_r÷_nC_r= r!

r!= = 6=3*2*1=3!

r=3

Substitute r=3 in _nC_r=_nPr÷r! = {n! ÷ (n-r)} ÷r!

= {n*(n-1)*(n-2)*(n-3)! ÷ (n-3)! }÷3!

56 = n*(n-1)*(n-2) ÷6

I.e. 56*6 =336 = n*(n-1)*(n-2) = 8*7*6

n=8

1.9.3 Problem 1: A king has 8 different types of ornamental jars in his courtyard. Tell me the number of different combinations in which theses can be arranged?

(Lilavati Shloka 116)

Solution:

Total number of jars(n) =8

No	Type of arrangement	Nos
1	No of arrangements with 1 jar at a time	₈C₁
2	No of arrangements with 2 jars at a time	₈C₂
3	No of arrangements with 3 jars at a time	₈C₃
4,5,6	------------------
7	No of arrangements with 7 jars at a time	₈C₇
8	No of arrangements with 8 jars at a time	₈C₈

Total number of arrangements = ₈C₁+ ₈C₂ + . . . + ₈C₇ + ₈C₈ =255 = 2⁸-1

1.9.3 Problem 3 : A Marriage bureau is in the business of identifying girls for boys and boys for girls. They are having 5 girls and 4 boys in their register looking for a match. In how many ways they can make proposals with 2 boys and 2 girls?

Solution:

1. There are 4 boys. The number of ways in which 2 boys can be grouped are₄C₂=4*3*2!/2!*2!=6

2. There are 5 girls. The number of ways in which 2 girls can be grouped are ₅C₂=5*4*3!/3!*2! = 10

For every group of 2 boys selected out of 6 groups, we can match with every group of 2 girls selected out of 10 groups.

Total number of proposals possible = 6*10=60

1.9.3 Problem 4 : A team has 10 players. Only six can fit into one photo frame. Manager has to be in each of the photo session. A photographer was asked to give an estimate for all the different combinations of photos. A photo with frame costs Rs.22. Find out the estimate given by photographer to the Manager

Solution:

Here n =10, r=5( manager has to be in every photo)

The number of 5-member groups teams that can be formed from 10 members are

= ₁₀C₅

= 10!/5!*5!

= (10*9*8*7*6*5!)/(5!*5!)

= 10*9*8*7*6/120( 5! gets cancelled)

= 9*4*7 =252 photos

Total cost = 252*22= Rs.5, 544

1.9.3 Problem 5 : Your school has one teacher for each of the subjects : Mathematics, Social science, General Science, Moral science, English, Hindi, Local Language, Physical Training. One of them is a headmaster.

(a) How many committees of 5 members can be formed?

(b) How many of them will not have Headmaster in them?

Solution:

Number of teachers (n) = 8

Number of teachers in the committee (r) =5

Number of committees that can be formed is

= ₈C₅= 8!/(8-5)!*5!= 8*7*6*5!/3!*5!= 8*7*6/6 = 56

If we are to have Headmaster in the committee, then we are left with only 7 teachers for selection. In such a case

The number of teachers (n) = 7.

Since headmaster is already a member of the committee, we only need to form a committee of 4 members (r) =4.

Number of committees with head master is

= ₇C₄= 7!/(7-4)!*4!= 7*6*5*4!/3!*4!= 7*6*5/6 = 35

No of committees without headmaster = total number of committees – Number of committees with head master = 56-35 =21

1.9.3 Problem 6 : There are 20 non collinear points on a plane. How many (a) straight lines (b) triangles can be formed by joining these points?

Solution:

The number of non collinear points (n=20)

Since straight line has 2 points (r=2),

Total number of straight lines that can be formed are

= ₂₀C₂= 20!/(20-2)!*2!= 20*19*18!/18!*2!

= 20*19/2 = 190

Since triangles are formed with 3 points(r=3),

Total number of triangles that can be formed are

= ₂₀C₃= 20!/(20-3)!*3!= 20*19*18*17!/17!*3!

= 20*19*18/6 = 1140

Solution:

1.9.3 Problem 6 : In a hexagon how many triangles can be formed?

Solution:

The number of vertices in a hexagon (n)=6

The number of points required for a triangle(r) =3

Number of triangles that can be formed in a hexagon are

= ₆C₃= 6!/(6-3)!*3!= 6*5*4*3!/3!*3!= 20

1.9.3 Problem 7: A country had selected a team of 8 batsmen and 7 bowlers to play a cricket match in India. The pitch where it is to be played is likely to help bowlers. The team captain decides to have 5 or 6 bowlers in the team of 11. How many ways he can form the team?

Solution:

If he chooses to have 5 bowlers then he can only have 6 batsmen out of 8.

If he chooses to have 6 bowlers then he can have 5 batsmen out of 8.

For every group of bowlers the captain chooses, he has several choices of groups of batsmen and hence total choice available for a particular option is product of these two choices.

Possibilities	Total bowlers available =7	Total batsmen available =8	No of combinations
1	5 (r=5)	6 (r=6)	=₇C₅*₈C₆	21*28=588
2	6 (r=6)	5 (r=5)	=₇C₆*₈C₅	7* 56=392

The captain has a choice of 980(588+392) choices!!!

1.9.3 Problem 8: Indian parliament has selected 8 members to form a 5-member Social Welfare Committee. The Health Minister and Women Welfare Ministers are among these 8 members. The committee’s role is to give recommendations for improvement of Welfare of Citizens. There is a rule that the committee should be headed by a Minister and there can not be more than one minister in the same committee. Find out how many committees can be formed as per the rule?

Solution:

Since the committee has to be headed by a minister, one of the ministers has to be in the committee. With one minister being a member of committee and two ministers can not be in the same committee,

Number of members available for selection is (n=6)(=8-2)

Since one minister is always in the committee, we need to select only 4 members for the committee (r=4)(=5-1)

The no of ways committee can be formed =₆C₄= 15

1.9 Summary of learning

Properties	Permutations	Combinations
Meaning ====>	Arrangement of things in an orderly manner	Selection of different objects
Example ====>	How many different words can be formed from the letters of the word ‘MATHS’	How many 10 member hockey team be formed from a list of 20 players
Definition ====>	No of ways of arranging ‘n’ things taken ‘r’ things at a time	No of combinations of ‘n things taken ‘r’ things at a time
Formula ====>	_nP_r = n(n-1)(n-2)…(n-r+1)=	_nC_r= _nP_r /r!
Relationship ===>	_nP_r= _nC_r* r!

Their Name:
Their Email:
Your Email:
Your Name:
Your message to your friend: