Chapter 16: PERMUTATION AND COMBINATION


Introduction


Factorial: Product of all numbers from 1 to n is n!. i.e. 5! = 1*2*3*4*5.
Special case: 0! = 1



Counting:
How many different ways are there doing a task.

Permutation:
An ordered arrangement of objects. Each of the different arrangements which can be made by taking some or all of a number of things called a permutation.

Combination: An un ordered selection of elements.

Sum Rule: If you have to do two tasks at the same time and task 1 can be done in n1 ways and task 2 can be done in n2 ways then total ways of doing the task is n1+n2.

Product rule: If two tasks can be done one after another. First is done in n1 ways and second in n2 ways then there are n1.n2 ways of doing the procedures.



Permutation formula:
 
P(n,r)=n!(nr)!

P ( n , n ) = n! ; P ( n , 0 ) = 1 ; P ( n , r ) = 0 where r > n;



Combination formula:

C(n,r)=n!(nr)!r!



E.g:
7P3 = 7*6*5 ( Thus to calculate permutation take the number on the left and multiply it with its previous 'n-1' values in this case 2.)

7C3  = (7*6*5) / (3*2*1) ( Thus to calculate combination take the number on the left and multiply it with its previous 'n-1' values and take denominator as n!)

C (n,r) = C (n, n-r) so C (7,6) = 7C6 = 7C7-6 = 7C1
 C ( n , n ) = 1 ; C ( n , 0 ) = 1

Problems and Answers


Q. How many words can be formed from all letter of word JAILER

A. Word has 6 letters so 6P6 = 6!


Q. How many ways of arranging word FATHERS so that vowels always come together.

A. Treat A,E as single entity so we get 6 alphabets so 6P6 ways and 2 vowels can be arranged in 2P2 ways so total = 6P6 * 2P2 = 720 * 2 = 1440




Q. Number of ways of arranging MALAYALAM such that vowels are never together.

A. Total ways = 5 letters and 4 vowels; Vowels can be treated as single entity giving us 6 alphabets; So 6P6 = 6! but M and L are repeated twice so removing duplicate entries we get 6!/(2!*2!) ways.

Total ways in which 9 letters can be arranged are = 9!/(2!*2!*4!) ways removing duplicates for 2 M's, 2 L's and 4 A's

Total ways vowels are never together = Total ways - Total ways were they are together


Q. How many ways can a cricket team of 11 be chosen out of batch of 15 players.

A. ways = 15C11 = 15C4


Q. How many ways to select a committee of 3 men and 2 ladies from 6 men and 5 ladies.

A. Men can be chosen in 6C3 ways and women in 5C2 ways.

Total ways are = 6C3 * 5C2.

Q. There are 6 boxes numbered 1,2,… 6. Each box is to be filled up either with a red or a green ball in such a way that at least 1 box contains a green ball and the boxes containing green balls are consecutively numbered. The total number of ways in which this can be done is


  1. 5

  2. 21

  3. 33

  4. 60


Ans . B


  1. GRRRRR, RGRRRR, RRGRRR, RRRGRR, RRRRGR, RRRRRG GGRRRR, RGGRRR, RRGGRR, RRRGGR, RRRRGG GGGRRR, RGGGRR, RRGGGR, RRRGGG GGGGRR, RGGGGR, RRGGGG GGGGGR, RGGGGG GGGGGG

  2. Hence 21 ways.


Q. Let T be the set of integers {3, 11, 19, 27, …, 451, 459, 467} and S be a subset of T such that the sum of no two elements of S is 470. The maximum possible number of elements in S is


  1. 32

  2. 28

  3. 29

  4. 30


Ans . D


  1. Tn = a + (n-1)d

  2. 467 = 3 + (n – 1)8 ⇒ n = 59

  3. Half of n = 29 terms 29th term is 227 and 30 th term is 235 and when these two terms are added the sum is less than 470. Hence the maximum possible values the set S can have is 30.


Q. The number of positive integers n in the range 12 ≤ n ≤ 40 such that the product (n - 1)(n - 2).. 3.2.1 is not divisible by n is


  1. 5

  2. 7

  3. 13

  4. 14


Ans . B


  1. From 12 to 40, there are 7 prime numbers, i.e., 13, 17, 19, 23, 29, 31 and 37 such that (n – 1)! is not divisible by any of them.


Q. A graph may be defined as a set of points connected by lines called edges. Every edge connects a pair of points. Thus, a triangle is a graph with 3 edges and 3 points. The degree of a point is the number of edges connected to it. For example, a triangle is a graph with three points of degree 2 each. Consider a graph with 12 points. It is possible to reach any point from any point through a sequence of edges. The number of edges, e, in the graph must satisfy the condition


  1. 11 ≤ e ≤ 66

  2. 10 ≤ e ≤ 66

  3. 11 ≤ e ≤ 65

  4. 0 ≤ e ≤ 11


Ans . A


  1. The least number of edges will be when one point is connected to each of the other 11 points, giving a total of 11 lines. One can move from any point to any other point via the common point. The maximum edges will be when a line exists between any two points. Two points can be selected from 12 points in

  2. 12C2i.e. 66 lines


Q. In a certain examination paper, there are n questions. For j = 1,2 …n, there are 2n-j students who answered j or more questions wrongly. If the total number of wrong answers is 4095, then the value of n is


  1. 12

  2. 11

  3. 10

  4. 9


Ans . A


  1. Let us say there are only 3 questions. Then, there are

  2. 23-1 = 4 students who have done 1 or more questions wrongly, 23-2 = 2 students who have done 2 or more questions wrongly and 23-3 = 1 student who must have done all 3 wrongly. Thus, total number of wrong answers = 4 + 2 + 1 = 7 = 23 – 1 = 2n – 1.

  3. = 4095 = 212 – 1. Thus n = 12


CAT solved problems


Q. If there are 10 positive real numbers n1 < n2< n3 <... < n10 , how many triplets of these numbers (n1 , n2, n3) and (n2 , n3, n4) can be generated such that in each triplet the first number is always less than the second number, and the second number is always less than the third number?


  1. 45

  2. 90

  3. 120

  4. 180


Ans . 120

  1. Total possible arrangements = 10 × 9 × 8 Now 3 numbers can be arranged among themselves in 3! ways = 6 ways Given condition is satisfied by only 1 out of 6 ways. Hence, the required number of arrangements

  2. = 10*9*8 / 6

  3. = 120



CAT Questions


Q.There were x pigeons and y mynahs in a cage. One fine morning p of them escaped to freedom. If the bird keeper, knowing only that p = 7, was able to figure out without looking into the cage that at least one pigeon had escaped, then which of the following does not represent a possible (x,y) pair?


  1. (10,8)
  2. (7,2)
  3. (25,6)
  4. (12,4)

Ans.a




Q.There are six boxes numbered 1, 2, 3, 4, 5, 6. Each box is to be filled up either with a white ball or a black ball in such a manner that at least one box contains a black ball and all the boxes containing black balls are consecutively numbered. The total number of ways in which this can be done equals.


  1. 15
  2. 21
  3. 63
  4. 64

Ans.b


Q.116 people participated in a singles tennis tournament of knock out format. The players are paired up in the first round, the winners of the first round are paired up in second round, and so on till the final is played between two players. If after any round, there is odd number of players, one player is given a bye, i.e. he skips that round and plays the next round with the winners. Find the total number of matches played in the tournament.


  1. 115
  2. 53
  3. 232
  4. 116

Ans.a



Q.139 persons have signed up for an elimination tournament. All players are to be paired up for the first round, but because 139 is an odd number one player gets a bye, which promotes him to the second round, without actually playing in the first round. The pairing continues on the next round, with a bye to any player left over. If the schedule is planned so that a minimum number of matches is required to determine the champion, the number of matches which must be played is


  1. 136
  2. 137
  3. 138
  4. 139

Ans.c



Q.A box contains 6 red balls, 7 green balls and 5 blue balls. Each ball is of a different size. The probability that the red ball selected is the smallest red ball, is


  1. 1/18
  2. 1/3
  3. 1/6
  4. 2/3

Ans.c



Q.A five digit number is formed using digits 1, 3, 5, 7 and 9 without repeating any one of them. What is the sum of all such possible numbers?


  1. 6666600
  2. 6666660
  3. 6666666
  4. None of these

Ans.a


Q.A man has 9 friends: 4 boys and 5 girls. In how many ways can he invite them, if there have to be exactly 3 girls in the invitees?


  1. 320

  2. 160

  3. 80

  4. 200


Ans.b


Q.Out of two-thirds of the total number of basketball matches, a team has won 17 matches and lost 3 of them. What is the maximum number of matches that the team can lose and still win more than threefourths of the total number of matches, if it is true that no match can end in a tie?


  1. 4

  2. 6

  3. 5

  4. 3


Ans.a


Q.In how many ways can eight directors, the vice chairman and chairman of a firm be seated at a round table, if the chairman has to sit between the vice chairman and a director?


  1. 9! * 2

  2. 2 * 8!

  3. 2 * 7!

  4. none


Ans.b


Q. A, B, C, D, ..., X, Y, Z are the players who participated in a tournament. Everyone played with every other player exactly once. A win scores 2 points, a draw scores 1 point and a loss scores 0 point. None of the matches ended in a draw. No two players scored the same score. At the end of the tournament, by ranking list is published which is in accordance with the alphabetical order. Then


  1. M wins over N

  2. N wins over M

  3. M does not play with N

  4. None of these


Ans . A


Q. Number of students who have opted for subjects A, B and C are 60, 84 and 108 respectively. The examination is to be conducted for these students such that only the students of the same subject are allowed in one room. Also the number of students in each room must be same. What is the minimum number of rooms that should be arranged to meet all these conditions?


  1. 28

  2. 60

  3. 12

  4. 21


Ans . D


Read and Answer


A, B, C and D collected one-rupee coins following the given pattern. Together they collected 100 coins.
Each one of them collected even number of coins.
Each one of them collected at least 10 coins.
No two of them collected the same number of coins.


Q. The maximum number of coins collected by any one of them cannot exceed


  1. 64

  2. 36

  3. 54

  4. None of these


Ans . A


Q. If A collected 54 coins, then the difference in the number of coins between the one who collected maximum number of coins and the one who collected the second highest number of coins must be at least


  1. 12

  2. 24

  3. 30

  4. None of these


Ans . C


Q. If A collected 54 coins and B collected two more coins than twice the number of coins collected by C, then the number of coins collected by B could be


  1. 28

  2. 20

  3. 26

  4. 22


Ans . D


Q. Five-digit numbers are formed using only 0, 1, 2, 3, 4 exactly once. What is the difference between the maximum and minimum number that can be formed?


  1. 19800

  2. 41976

  3. 32976

  4. None of these


Ans . C


Q. How many numbers can be formed from 1, 2, 3, 4, 5, without repetition, when the digit at the unit’s place must be greater than that in the ten’s place?


  1. 54

  2. 60

  3. 17

  4. 2 × 4!


Ans . B


Q. Three labelled boxes containing red and white cricket balls are all mislabelled. It is known that one of the boxes contains only white balls and another one contains only red balls. The third contains a mixture of red and white balls. You are required to correctly label the boxes with the labels red, white and red and white by picking a sample of one ball from only one box. What is the label on the box you should sample?


  1. white

  2. red

  3. red and white

  4. Not possible to determine from a sample of one ball


Ans . C


Q. For a scholarship, at the most n candidates out of 2n + 1 can be selected. If the number of different ways of selection of at least one candidate is 63, the maximum number of candidates that can be selected for the scholarship is


  1. 3

  2. 4

  3. 6

  4. 5


Ans . A


Quiz

Score more than 80% marks and move ahead else stay back and read again!