PERMUTATION AND COMBINATION

Permutation and Combination

In this chapter, we shall learn about some basic counting techniques which will be useful in determining the number of different ways of arranging and selecting objects without actually listing them.

Multiplication principle- Suppose student Mohan has 3 pants and 2 shirts. How many different pairs of a pant and shirt can he dress up with?

There are three ways in which a pant can be chosen.

For 1st pant————-any of the two shirts can be chosen———2 ways

For 2nd pant————-any of the two shirts can be chosen———2 ways

For 3rdpant————–any of the two shirts can be chosen———-2 ways

For every pant, there are two shirts, therefore, he can dress up with 3×2 = 6.

Let the three pants be P1, P2 and P3 and two shirts be S1, S2 and S3. Above can be easily understood by using this diagram:

For every pant, there are two shirts, therefore, he can dress up in 3×2 = 6 ways.

Number of pair of pants and shirts he can choose = (No. of pants he can choose) x (No. of shirts he can choose)

Problems of above type are solved by using multiplication principle or fundamental principle of multiplication which states that:

If an event can occur in p ways and another event can occur in n ways, number of ways in which both events p & q can be performed is equal to p x q.

Addition principle- If an event can occur in p different ways and another event can occur in q different ways, number of ways in which event p or q can be performed is equal to p + q.

  1. Q) In a debate competition, there are 5 candidates from science side, 4 from commerce side and 3 from humanities side. In how many ways a winner of competition can be selected?

Ans) A winner out of science students can be selected in 5 ways.

A winner out of commerce students can be selected in 4 ways.

A winner out of humanities students can be selected in 3 ways.

An overall winner of competition can be selected in 5 + 4 + 3 = 12 ways.

  1. Q) In a shop, there are 10 shirts and there are 10 pants
  • In how many ways can a pair of pant and a pair of shirt can be selected.
  • In how many ways can a pair of cloth (pant or shirt) can be selected.

Ans) Number of ways in which a pair of pant and a pair of shirt can be selected = 10 x 10 = 100

Number of ways in which a pair of cloth (pant or shirt) can be selected = 10 + 10 = 20

Factorial notation- The notation n! (factorial n) represents the product of first n natural numbers. Factorial of only natural numbers is defined.

For example, 5! = 1 x 2 x 3 x 4 x 5

0! = 1

n! = n (n – 1)! = n (n-1) (n-2)! = n (n-1) (n-2) (n-3)! (provided n ≥ 3)

n! tool for arrangement- Number of ways in which, we can palace N things in N places = N!

or No. of ways in which we can arrange n things = N!

  1. Q) How many 4-digits numbers can be formed from digits 1, 2, 3 and 4? (Repetition is not allowed)

Ans) Number of 4-digits numbers that can be formed from digits 1, 2, 3 and 4 = 4! = 24

  1. Q) How many 7 letter words with or without meaning can be formed from letters M, N, O, P, Q, R and S?

Ans) Number of 7 letter words with or without meaning formed from letters M,N,O,P,Q, R and S = 7!

  1. Q) Of the different words that can be formed from the letters of the word BEGINS how many words begins with B and end with S?

Ans) Number of words beginning with B and ending with S formed from letters of word BEGINS = 4! (Number of arrangements of letters E, G, I, N)

Question based on combination of fundamental principle of multiplication and n! principle

  1. Q) In how many ways can the 7 letters M, N, O, P, Q, R and S be arranged so that P and Q occupy continuous position?

Ans) We should assume PQ as a single word. No. of arrangements of words M, N, O, PQ, R and S = 6!

PQ may act as a single word and QP may also act as a single word.

No. of ways in which letters M, N, O, P, Q, R and S can be arranged so that P and Q occupy continuous position = 6! X 2! = 1440

Combination (nCr) tool for arrangement- This tool is used for specific situation of counting, the number of ways of selecting r things out of n distinct things = [ nCr].

The number of ways of selecting r things out of n identical things = 1.

nCr = n! /r! x (n-r)!

important points regarding nCr

  • nCr + nCr – 1 = n + 1Cr
  • nCx = nCy

It implies that (x = y) or (x + y = n)

  • When n is constant and r is variable, for nCr to be greatest
  1. If n is even, r = n/2
  2. If n is odd, r = (n + 1)/2 or (n-1)/2
  3. Q) A committee of 5 members is to be formed from group of 8 members. In how many ways can this be done?

Ans) 5 members out of 8 members can be selected in 8C5ways. Number of ways in which 5 members out of 8 members can be selected = 8C5 = 56

  1. Q) How many chords can be drawn through 21 points on a circle?

Ans) Drawing a chord is equivalent to selecting two specific points. Number of chords that can be drawn through 21 points = 21C2

  1. Q) In how many ways can a student choose a program of 5 courses if 9 courses are available and 2 specific courses are compulsory for every student?

Ans) 2 specific courses are compulsory. Therefore, student has to choose 3 courses out of 7 courses. Number of ways in which a student can choose a program of 5 courses if 9 courses are available and 2 specific courses are compulsory = 7C3

Question based on combination of fundamental principle of multiplication and Combination

  1. Q) A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how many ways can this be done? How many of these committees would consist of 1 man and 2 women?

Ans) We have to select 1 man out of 3 men and 2 women out of 3 women. No. of ways in which this can be done = 2C1 X 3C2

  1. Q) In how many ways can one select a cricket team of eleven from 17 players in which only 5 players can bowl if each cricket team of 11 must include exactly 4 bowlers?

Ans) We have to select 4 bowlers out of 5 bowlers and we have to select 7 players out of remaining 12 players. This can be done in 5C4 X 12C7

  1. Q) A bag contains 5 black and 6 red balls. Determine the number of ways in which 2 black and 3 red balls can be selected?
  • If balls of same color are distinct.
  • If balls of same color are identical.

Ans) If balls of same color are distinct. No. of ways in which 2 black ball out of 5 black ball can be selected = 5C2 X 6C3

If balls of same color are same. No. of ways in which 2 black ball out of 5 black ball can be selected = 1

Permutation (arrangement) nPr

Number of ways in which r things out of N distinct things can be selected and can be arranged at r different places = NCr x r! = NPr

  1. Q) In how many ways 5 fruits out of group of 8 fruits can be selected and arranged at 5 different places?

Ans) Number of ways in which 5 fruits out of 8 fruits can be selected and arranged at 5 different places =  8C5 x 5 = 56

Arrangement of objects not all distinct

Number of arrangements of N things out of which P1 are of one type, P2 are of second type, P3 are of third type and the rest are all different = (N! / (P1! P2! P3!))

  1. Q) How many words with or without meaning can be formed with the letters of following words: –

1) ALLAHABAD

2) MISSISSIPPI

3) APPLE

Ans 1) Number of words that can be formed with the letters of word ALLAHABAD = (9!)/ (4!2!) = 7560

Ans 2) Number of words that can be formed with the letters of word MISSISSIPPI = (11!)/ (4!4!2!) = 34650

Ans 3) Number of words that can be formed with the letters of word APPLE = (5!)/ (2!) = 60.

Circular permutations

There are three objects A, B and C. We can linearly arrange these three objects in 3! = 6 possible ways. There are following linear arrangements of these three objects: – ABC, ACB, CAB, CBA, BAC, BCA.

A

 

 

 

 

 

                            B                       C                      Figure 1           ACB, CBA and BAC are same.

 

A

 

 

 

 

 

                            C                       B                      Figure 2          ABC, BCA and CAB are same

 

If we talk about circular arrangements, we can observe from figure 1 that three arrangements ACB, CBA and BAC are same. We can observe from figure 2 that three arrangements ABC, BCA and CAB are same.

We conclude that there are two ways of circular arrangements of these three objects. This happens because there is no point of a starting point on a circular arrangement. Three objects can be arranged in ((3!)/3) ways = 2! Ways.

Generalizing the whole concept, on circular table, N objects can be arranged in (N – 1)! Ways or (N!)/N.

  1. Q) In how many ways five guests can sit on a round table?

Ans) If we talk about necklace or garland, where we can turn necklace or garland and clockwise and anti-clockwise arrangements are not different.

No. of circular arrangements of N different beads of necklace = (N – 1)! /2.

  1. Q) How many different garlands can be formed from eight different beads?

Ans) Number of garlands formed from eight different beads = 7!/2 = 2520.

Selection of any number of things out of N distinct things

If there are N distinct things, 1 thing out of N distinct thing can be chosen in NC1.

m things out of N distinct things can be chosen in NCm ways.

Any number (0 or 1 or 2) of things out of N can be chosen in

  (NC0 + NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN) ways. (By using combination and fundamental principle of addition)

NC0 + NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN = 2N

The number of selections of 1 or more things out of N different things =

NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN = 2N– 1

  1. Q) A boy has gone to a library and there are 200 different books in library. In how many ways he can pick one or more books from library?

Number of diagonals of N sided polygon

Number of diagonals of N sided polygon = (Number of straight lines formed by joining N points) – (Number of sides) = NC2 – N

Number of straight lines formed by N points of which l are collinear

NC2 straight lines are formed by joining N points which are not collinear and only 1 straight line is formed by joining R collinear points. Therefore, number of straight lines formed by joining N points of which l are collinear =

NC2 –  lC2 + 1

Number of Triangles formed by N points of which l are collinear

NC3 triangles are formed by joining N points which are not collinear and no triangle is formed by joining R collinear points. Therefore, number of triangles formed by joining N points of which l are collinear =

NC3 –  lC3

Number of parallelograms formed by intersection of m parallel lines with n parallel lines

Two lines out of m parallel lines can be selected in mC2 ways and two lines out of n parallel lines can be selected in nC2 ways. Therefore, parallelogram is formed by selecting two lines out of m parallel lines and two lines out of n parallel lines. Number of parallelograms formed by intersection of m parallel lines with n parallel lines =

mC2 x nC2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Let your friend know that you are preparing for GRE like a bossShare on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn