GRE: 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.

Problem: 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?

Sol. 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.

 

Problem 1) 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.

Sol.  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!

 

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

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

 

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

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

 

Problem 3) 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?

Sol.  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

Problem 4) 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?

Sol.  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

 

Problem 5) A committee of 5 members is to be formed from group of 8 members. In how many ways can this be done?

Sol.  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

 

Problem 6) How many chords can be drawn through 21 points on a circle?

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

 

Problem 7) 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?

Sol.  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

 

Problem 8) 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?

Sol.  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

 

Problem 9) 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?

Sol.  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

 

Problem 10) 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.

Sol.  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

 

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

Sol.  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!))

 

Problem 12) How many words with or without meaning can be formed with the letters of following words: –

1) ALLAHABAD

2) MISSISSIPPI

3) APPLE

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

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

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.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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.

 

Problem 13) In how many ways five guests can sit on a round table?

Sol.  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.

 

Problem 14) How many different garlands can be formed from eight different beads?

Sol.  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

 

Problem 15) 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?

Sol.  Number of ways in which he can pick one or more book =

\({ 2 }^{ 200 }-1\)

 

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

 

 

Problem 16)   Find the number of diagonals & triangles formed in a decagon?

a) 35, 130

b) 25, 120

c) 35, 120

d) 45, 120

Sol.  No. of diagonals formed by decagon =

\({ _{ }^{ 10 }{ C } }_{ 2 }-10\\ =\frac { 9\times 10 }{ 2 } -10\\ ={ (35) }^{ Ans }\)

No. of triangles formed in a decagon =

\(=_{ }^{ 10 }{ { C }_{ 3 } }\\ =\frac { 8\times 9\times 10 }{ 2\times 3 } \\ ={ (120) }^{ Ans }\)

 

Problem 17) Out of 18 points in a plane, no three are in a straight line except 5 which are collinear. How many straight lines can be formed.

a) \(_{ }^{ 18 }{ { C }_{ 2 } }\)

b) \(_{ }^{ 18 }{ { C }_{ 2 } }-_{ }^{ 5 }{ { C }_{ 2 } }\)

c) \(_{ }^{ 18 }{ { C }_{ 2 }-_{ }^{ 5 }{ { C }_{ 2 }+1 } }\)

d) \(_{ }^{ 18 }{ { C }_{ 2 }-_{ }^{ 5 }{ { C }_{ 2 }-1 } }\)

e) \(_{ }^{ 18 }{ { C }_{ 2 }-_{ }^{ 5 }{ { C }_{ 2 }+2 } }\)

Sol.  No. of straight lines that can be formed =

\(=_{ }^{ 18 }{ { C }_{ 2 }-_{ }^{ 5 }{ { C }_{ 2 }+1 } }\)

 

Problem 18) How many numbers of 3-digits can be formed with the digits 1, 2, 3, 4, 5 (repetition of digits not allowed)

a) 125

b) 120

c) 60

d) 180

Sol.  The number of numbers formed would be given by

\(=5\times 4\times 3=60\)

(First digit can be filled in 5 ways, second can be filled in 4 ways & third can be formed in 3 ways.)

 

Problem 19)   How many nos. between 2000 & 3000 can be formed with the digits 0, 1, 2, 3, 4, 5, 6, 7 (repetition of digits not allowed)?

a) 42

b) 210

c) 336

d) 440

Sol.  The first digit can only be 2 (1 way), 2nd digit can filled only in 7 ways, 3rd digit can be filled only in 6 ways & 4th digit can be filled only in 5 ways.

No. of object =

\(=7\times 6\times 5=210\quad ways\)

 

Problem 20) In how many ways can a person send invitation cards to 6 of his friends if he has four servants to distribute the cards?

a) 42

b) 210

c) 24

d) 120

Sol.  Each invitation can be sent in 4 ways.ways.

Thus

\(4\times 4\times 4\times 4\times 4\times 4={ (4) }^{ 6 }\)

 

Problem 21) In how many ways can 7 Indians, 5 Pakistanis & 6 Dutch be seated in a row so that all persons of the same nationality sit together?

a) 3!

b) 7!5!6!

c) 3!7!5!6!

d) 182

Sol.  We should assume 7 Indians as one person, 5 Pakistanis as one person, 6 Dutch as one person. 5 Pakistanis can be arranged in 5! Ways. 7 Indians can be arranged in 7! Ways & 6 Dutch can be arranged in 6! Ways Pakistanis, Dutch & Indians can be arranged in 5! Ways.

Therefore, 7 Indians, 5 Pakistanis and 6 Dutch can sit in (7!×5!×6!×3!) ways.

 

Problem 22) In how many ways five chocolates can be chosen from an unlimited number of dairy milk, five-star & perk chocolates?

a) 81

b) 243

c) 21

d) 31

Sol. We have to choose five chocolates. We can choose first chocolate in three ways (either dairy milk or five-star or perk). Similarly, we can choose another chocolate in three way.

Therefore, five chocolates can be choosen in \(3\times 3\times 3\times 3\times 3={ (3) }^{ 5 }\) ways.

 

Problem 23) There are 6 pups & 4 cats. In how many ways can they be seated in a row so that no cats sit together?

Sol.  1st arrange 6 pups in 6 places in 6! ways. This will leave us with 7 places for 4 cats.

Assume = \( _{ }^{ 7 }{ { P }_{ 4 }(6!) }\) ways

 

Problem 24) A state issues automobile license plates that begin with two letters selected from a 26-letter alphabet, followed by four numerals selected from the digits 0 through 9 inclusive. Repeats are permitted. For example, one possible license plate combination is GF3352.

Quantity A:       The number of possible unique license plate combinations.

Quantity B:       60,00,000

a) Quantity A is greater

b) Quantity B is greater

c) The two quantities are equal

d) The relationship cannot be determined from the information given.

Sol.  The license plate have 2 letters followed by 4 numbers.

No. of possible license plate = \(26\times 26\times { 10 }^{ 4 }={ (6760000) }^{ Ans }\)

 There are 26 letters in the alphabet and 10 digits to pick from.

 

Problem 25) A 10-student class is to choose a president, vice president & security from the group. If no person can occupy more than one post, in how many ways can this be accomplished?

Sol.  There are 10 students from whom president can be chosen & after that there are 9 students from which vice president can be chosen, 8 students from which secretary can be chosen.

Whole process can be accomplished in = (8×9×10) = 720 ways.

 

Problem 26) A history exam features five questions. There of the questions are multiple-choice with four options each. The other two questions are true or false. If Caroline selects one answer for every question, how many ways can she/he answer the exam?

Sol.  No. of ways in ways she/he answer the question

\(=4\times 4\times 4\times 2\times 2=64\times 4={ (256) }^{ Ans }\)

 

Problem 27) In a school of 150 students, 75 study Latin, 110 study Spanish & 11 study neither.

Quantity   A:     The no. of students who study only Latin

Quantity   B:     46

a) Quantity A is greater

b) Quantity B is greater

c) The two quantities are equal

d) The relationship cannot be determined from the information given.

Sol.

Let A be the no. of students who study only Latin. Let B the no. of students who study both Latin & Spanish. Let C be the no. of students who study only Spanish. Let D be the no. of students who studies neither.

\(A+B+C+D=150\\ A+B=75\\ B+C=110\\ D=11\\ A=29,\quad B=46,\quad C=64\)

No. of students who study only Latin = 29

Quantity B is greater.

 

Problem 28) Mario’s pizza has two choices of crust. The restaurant also has 5 choices of toppings. Finally Mario’s offers every pizza in extra-cheese as well as regular. If Linda’s volleyball team decides to order a pizza with four different toppings, how many different choices do the teammates have at Mario’s pizza?

Sol. Consider the topics first, four the toppings are on the pizza & one isn’t. Four out of five can be chosen in \(_{ }^{ 5 }{ { C }_{ 4 } }\) ways.

If each of these pizzas can be offered in 2 choices of crust, 2 choices of cheese & 5 choices of toppings. Total no. of choices do the teammates have at Mario’s pizza = 5×2×2 = 20 ways

 

Problem 29) Country X has a four-digit postal code assigned to each town & none of the digits is repeated.

Quantity A:       The numbers of possible portal codes in country X

Quantity B:       4536

a) Quantity A is greater

b) Quantity B is greater

c) The two quantities are equal

d) The relationship cannot be determined from the information given.

Sol.  No. of possible postal code in country X = 10×9×8×7 = 5040

Quantity A is bigger.

 

Problem 30) 8 athletes compete in a race in which gold, silver & a bronze medal will be awarded to the top three finishers, in that order.

Quantity A: The number of ways in which the medals can be awarded.

Quantity B:       8×3!

a) Quantity A is greater

b) Quantity B is greater

c) The two quantities are equal

d) The relationship cannot be determined from the information given.

Sol.  No. of ways in which the medals can be awarded

[/latex]=8\times 7\times 6=336\quad ways\(\)

Quantity A is bigger.

(Gold medal winner can be selected in 8 ways, silver medal winner can be selected in 7 ways & bronze medal winner can be selected in 6 ways.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Let your friend know that you are preparing for GRE like a bossShare on Facebook
Facebook
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Share on LinkedIn
Linkedin