FORMULAE: Permutation and Combination

Introduction

    • Factorial Notation -> ! ; n! = n(n – 1) (n – 2) … 3.2.1 = Product of n consecutive integers starting from 1.

    • 0! = 1

    • Factorials of only Natural numbers are defined. n! is defined only for n ≥ 0 n! is not defined for n < 0

    • nCr = 1 when n = r.

    • Combinations (represented by nCr) can be defined as the number of ways in which r things at a time can be SELECTED from amongst n things available for selection. The key word here is SELECTION.

    • Understand here that the order in which the r things are selected has no importance in the counting of combinations.

    • nCr = Number of combinations (selections) of n things taken r at a time. nCr = n! /[r! (n–r)!] ; where n ≥ r (n is greater than or equal to r).

    • Some typical situations where selection/combination is used:

      1. Selection of people for a team, a party, a job, an office etc. (e.g. Selection of a cricket team of 11 from 16 members)

      1. Selection of a set of objects (like letters, hats, points pants, shirts, etc) from amongst another set available for selection.

    •  
    • In other words any selection in which the order of selection holds no importance is counted by using combinations.

    • Permutations (represented by nPr) can be defined as the number of ways in which r things at a time can be SELECTED & ARRANGED at a time from amongst n things.

    • The key word here is ARRANGEMENT. Hence please understand here that the order in which the r things are arranged has critical importance in the counting of permutations.

    • In other words permutations can also be referred to as an ORDERED SELECTION. nPr = number of permutations (arrangements) of n things taken r at a time.

    • nPr = n!/ (n – r)!; n ≥ r

    • Some typical situations where ordered selection/ permutations are used

      • Making words and numbers from a set of available letters and digits respectively

      • Filling posts with people

      • Selection of batting order of a cricket team of 11 from 16 members

      • Putting distinct objects/people in distinct places, e.g. making people sit, putting letters in envelopes, finishing order in horse race, etc.)

    • Selection : Suppose we have three men A, B and C out of which 2 men have to be selected to two posts. This can be done in the following ways: AB, AC or BC (These three represent the basic selections of 2 people out of three which are possible. Physically they can be counted as 3 distinct selections. This value can also be got by using 3C2. Note here that we are counting AB and BA as one single selection. So also AC and CA and BC and CB are considered to be the same instances of selection since the order of selection is not important.

    • Arrangement : Suppose we have three men A, B and C out of which 2 men have to be selected to the post of captain and vice captain of a team. In this case we have to take AB and BA as two different instances since the order of the arrangement makes a difference in who is the captain and who is the vice captain. Similarly, we have BC and CB and AC and CA as 4 more instances. Thus in all there could be 6 arrangements of 2 things out of three. This is given by 3P2 = 6.

    • When we look at the formulae for Permutations and Combinations and compare the two we see that, nPr = r! × nCr = nCr × rPr

    • This in words can be said as: The permutation or arrangement of r things out of n is nothing but the selection of r things out of n followed by the arrangement of the r selected things amongst themselves

    • MNP Rule : If there are three things to do and there are M ways of doing the first thing, N ways of doing the second thing and P ways of doing the third thing then there will be M × N × P ways of doing all the three things together.The works are mutually inclusive.

    • This is used to for situations like: The numbers 1, 2, 3, 4 and 5 are to be used for forming 3 digit numbers without repetition. In how many ways can this be done?

    • Using the MNP rule you can visualise this as: There are three things to doÆ The first digit can be selected in 5 distinct ways, the second can be selected in 4 ways and the third can be selected in 3 different ways. Hence, the total number of 3 digit numbers that can be formed are 5 × 4 × 3 = 60

    • When the pieces of work are mutually exclusive, there are M+N+P ways of doing the complete work.

    • Number of permutations (or arrangements) of n different things taken all at a time = n!

    • Number of permutations of n things out of which P1 are alike and are of one type, P2 are alike and are of a second type and P3 are alike and are of a third type and the rest are all different = n!P1!P2!P3!

    • Illustration: The number of words formed with the letters of the word Allahabad. Solution: Total number of Letters = 9 of which A occurs four times, L occurs twice and the rest are all different. Total number of words formed = 9! / (4! 2! 1! )

    • Number of permutations of n different things taken r at a time when repetition is allowed = n × n × n × … (r times) = nr .

    • Illustration: In how many ways can 4 rings be worn in the index, ring finger and middle finger if there is no restriction of the number of rings to be worn on any finger? Solution: Each of the 4 rings could be worn in 3 ways either on the index, ring or middle finger. So, four rings could be worn in 3 × 3 × 3 × 3 = 34 ways.

    • Number of selections of r things out of n identical things = 1 Illustration: In how many ways 5 marbles can be chosen out of 100 identical marbles? Solution: Since, all the 100 marbles are identical Hence, Number of ways to select 5 marbles = 1

    • Total number of selections of zero or more things out of k identical things = k + 1. This includes the case when zero articles are selected.

    • Total number of selections of zero or more things out of n different things =nC0+nC1+...+nCn=2n

    • Corollary: The number of selections of 1 or more things out of n different things = =nC1+...+nCn=2n1

    • Number of ways of distributing n identical things among r persons when each person may get any number of things = n + r – 1Cr–1

    • Imagine a situation where 27 marbles have to be distributed amongst 4 people such that each one of them can get any number of marbles (including zero marbles). Then for this situation we have, n = 27(no. of identical objects), r = 4 (no. of people) and the answer of the number of ways this can be achieved is given by: n + r – 1Cr–1 = 30C3

    • Corollary: No. of ways of dividing n non distinct things to r distinct groups are: n–1Cr–1 so For non-empty groups only Also, the number of ways in which n distinct things can be distributed to r different persons: = rn

    • Number of ways of dividing m + n different things in two groups containing m and n things respectively = m + nCn × mCm = = (m + n)! /m! n! Or, m+nCm × nCn = (m + n)! / n! m!

    • Number of ways of dividing 2n different things in two groups containing n things = 2n! / n! n! 2!

    • nCr + nCr – 1 = n + 1Cr

    • nCx = nCy so x = y or x + y = n

    • nCr = nCn – r

    • r . nCr = n . n – 1Cr – 1

    • nCr / (r + 1) = n + 1Cr + 1/( n + 1)

    • For nCr to be greatest,

      1. if n is even, r = n/2

      1. if n is odd, r = (n + 1)/2 or (n – 1)/2

    • Number of selections of r things out of n different things

      1. When k particular things are always included = n – kCr – k

      1. When k particular things are excluded = n – kCr

      1. When all the k particular things are not together in any selection = nCr – n – kCr – k

    • No. of ways of doing a work with given restriction = total no. of ways of doing it — no. of ways of doing the same work with opposite restriction.

    • The total number of ways in which 0 to n things can be selected out of n things such that p are of one type, q are of another type and the balance r of different types is given by: (p + 1)(q + 1)(2r– 1).

    • Total number of ways of taking some or all out of p + q + r things such that p are of one type and q are of another type and r of a third type = (p + 1)(q + 1)(r + 1) – 1 [Only non-empty sets]

    • nCrnCr1=nr+1r

  • Number of selections of k consecutive things out of n things in a row = n – k + 1

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

Quiz

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

Q1: How many 4 letter words can be formed from UPSC
1.P(4,4)
2.P(4,1)
3.P(2,2)
4.P(1,4)

ANS.1

Q2: How many ways can EUROPE be rearranged so vowels are together
1.3P3*4P4 / 2!
2.3P3*4P4
3.6!
4.6!/2!

ANS.1

Q3: In a bag of 3 white and 4 blue balls , how many ways of picking 2 white balls
1.3P2
2.3!
3.2!
4.3!/7!

ANS.1

Q4: P ( n , n ) =
1.n
2.1
3.0
4.n!

ANS.4

Q5: C ( n , n ) =
1.1
2.0
3.n
4.n!

ANS.1