Permutations and Combinations

Fundamental principle of counting

If a job can be done in n ways and corresponding to each way of performing the job another job can be performed by m ways then they both together can be performed in n X m ways. Let us give an example to clear things up a bit:

suppose a student has to choose a letter each from 5 vowels and 21 consonants then in how many ways can he do it? He can choose a vowel in 5 ways and corresponding to each vowels he can choose 21 different consonants so the total comes to 1 X 21 + 1 X 21 + 1 X 21 +1 X 21 +1 X 21  = 5 X 21.

here the key word is and , next suppose a student has to choose a letter either from 5 vowels or 21 consonants then in how many ways can he do it? it is 5 + 21 = 26. Here the key word was or .

Next moving on to permutations and combinations:

Permutations and combinations is simply the number of possibilities of that satisfy a specific criteria.

So each of the different arrangements that could be made from a given number of things taking some or all at a time is called permutations & combinations. In permutation order matters. So ab and ba are different. A Permutation is an ordered Combination. In combination ab and ba are taken as the same.

Permutations:

• Permutations of n different things, taking r at a time: nPr = n!/(n - r)!
• Permutations of n different things, taking n at a time, where repetition is not allowed: nPn = n!
• Permutations of n different things, taking r at a time, where repetition is allowed: nPn = nr
  The logic of this is simple suppose we are to arrange n objects taking n at a time where no repetitions are allowed, the answer becomes n * (n-1) * (n-2) *.. 1 or which we write in the short as n!. Now if repetitions are allowed the answer becomes n * n * n.... = n^n and by similar logic nr.
  
  
• Permutations of n different things, taking r at a time, where a particular thing always happens = r.n-1Pr-1
  
  
  If the particular object is placed at first place, remaining r – 1 places can be filled from
  n – 1 distinct objects in n-1Pr-1 ways. Similarly, by placing the particular object in 2nd, 3rd, .....,
  rth place, we find that in each case the number of permutations is n-1Pr-1
  This the total number of arrangements in which a particular object always occurs is r.n-1Pr-1
  
  
• Permutations of n different things, taking r at a time, where a particular thing never happens = n-1Pr-1
• Permutations of n different things, taking n at a time, where p are alike of one kind, q are alike of one kind and r are alike of one kind: n!/(p! . q! . r!)
• All the above formulas were for linear permutations, we will next move on to the circular permutations. In circular permutations 
  
  the endpoints do not matter like in the above image abcd, dabc, cdab, bcda permutations which would have had separate identity in case of linear permutations are exactly same in case of circular permutations. In short n linear permutation = 1 circular permutation. Hence total number of circular permutation = nPn / n = n!/n = (n - 1)!
  
  
• If the clockwise and anticlockwise orders are indistinguishable then the number of ways are  1/2((n-1)!). This is usually the case in case for a necklace or garland.
  
  
  

  Now to find the rank of any given word in dictionary (Without Repeating Alphabets) –

  Example – “MOTHER” 
  1) Arrange all the alphabets in alphabetical order like (E, H, M, O, R, T)
  2) Now in dictionary words will appear in alphabetical order, so first words will appear starting alphabet “E“. When E is fixed at first position, rest 5 alphabets can be arranged in 5! = 120 ways.
  3) Next starting alphabet will be “H” and again there will be 5! = 120 words starting with “H“.
  4) Now starting with “M“, and next alphabet as “E” we will have 4!=24 words.
  5) Similarly starting with “M“, and next alphabet as “H” we will have 4!=24 words.
  6) Next will be starting with “M“, and next alphabet as “O” and next as “E” we’ll have 3!=6 words.
  7) Similarly starting with “M“, and next alphabet as “O” and next as (“H” or “R”) we’ll have 3!*2=12 words.
  8) Next will be starting with “M“, and next alphabet as “O” and next as “T” and next as “E” we’ll have 2!=4 words.
  9) Next will be starting with “M“, and next alphabet as “O” and next as “T” and next as “H” will have 2! = 4 words but the first word will be M>O>T>H>E>R which is the desired word.
  

  So the rank of word MOTHER in dictionary will be 5! + 5! + 4! +4! + 3! + 3! + 3! + 2! +1 which equals 309.

  
  

  If the alphabets are repeated then we have:

  
  

  like INDIA…
  Start with A,
  A = 4! / 2! = 12 (because there are 2 I’s)
  D = 4! / 2! = 12 (becausethere are 2 I’s)
  [I]A = 3! = 6
  [I]D = 3! = 6
  [I]I = 3! = 6
  [IN]A = 2! =2
  [IND]AI = 1
  [IND]IA = 1.
  Summing it up gives you the rank
  12 + 12 + 6 + 6 + 6 + 2 + 1 + 1 = 46.

   
  
  

Combinations:

• Combinations of n different things, taking r at a time, where repetition is not allowed: nCr = n!/{(n - r)!r!}
• Combinations of n different things, taking r at a time, where repetition is allowed:

nCr = (n + r - 1)!/{(n - 1)!r!}

• nC0 = nCn = 1
• nCr = nCn-r
• nCx = nCy iff x +y = n or x = y
• nCr - 1 + nCr =  n + 1Cr
• If n is even, the greatest value of nCr = nCm where m = n/2
• If n is odd, the greatest value of nCr = nCm where m = (n-1)/2 or (n+2)/2
• rCr + r+1Cr + r+2Cr + …. + nCr = n + 1Cr +1
• nC0 + nC1 + nC3 + …. + nCn = 2n this is also the number of ways of selecting zero or more things from a group of n distinct things
• nC0 + nC2 + nC4 + …. + nCn = 22n
• Combinations of n different things, taking r at a time, where x particular thing always happens = n - xCr - x
• Combinations of n different things, taking r at a time, where x particular thing never happens = n - xCr
• Number of ways of selecting r things out of n identical things, where r <= n, is 1
• Number of ways of selecting 0 or more things out of n identical things is n + 1
• Number of ways of selecting some or all things, i.e at least 1 out of ( p + q + r …) things, in which p things are of one type, q of another and so on.. , is ((p+1)(q+1) ...) - 1
• Number of ways of selecting i or more things out of p things are of one type, q of another and n other  things is ((p+1)(q+1) 2n) - 1
• Number of ways of selecting k consecutive things out of n things in a row, is (n - k +1)
• Number of ways of selecting k consecutive things out of n things in a circle, is n when k < n

                              1 when k = n

• The number of ways in which ( m+ n) different things can be arranged in divided into two groups containing m and n things respectively: (m + n)!/(m! . n!) if m and n are to be distributed among 2 people then the formula becomes {(m + n)!/(m! . n!) } X 2!
• The number of ways in which n distinct things can be distributed to r different persons are rn
• The number of ways in which mn different things can be divided equally into m groups, each group containing n things are [(mn)!/(n!)m] X 1/m!
• The number of ways in which mn different things can be distributed equally into m groups, each group containing n things are [(mn)!/(n!)m]
• The number of ways of dividing n identical things among r persons or groups where each can receive 0 or more things is  n + r -1Cr - 1
• Number of ways in which n identical things among r persons, each one whom receives at least one item is n  -1Cr - 1
• Number of ways in which n identical things among r persons, each one whom receives neither less than m or more than k items (m < k) is the coefficient of xn in the expansion of (xm + xm+1 + … + xk)r

Before we wrap up this long and frankly now on the verge being boring list of formulas, we will give a few related to geometry:

• Number of squares in a square having n columns and n rows = 12 + 22 + … + n2. = n(n + 1)(2n + 1)/6
• Number of rectangles in a square having n columns and n rows = 13+ 23 + … + n3. = [n(n + 1)/2]2
• Number of squares in a rectangle having m columns and n rows = m.n + (m-1)(n-1)+...+0
• Number of rectangles in a rectangle having m columns and n rows = (1+2+3+...+m)(1+2+3+...+n)
• Number of quadrilaterals if m parallel lines intersect with n parallel lines = mC2  X nC2
• Number of terms in (a1 + a2 + …+ an)m is m+n-1Cn-1
• Number of terms in (1 + x2 + …+ an)m is m.n+1

Source of info:

1. https://www.mathsisfun.com/combinatorics/combinations-permutations.html
2. Quantum Cat 
3. https://praty23.wordpress.com/2012/05/15/rank-of-a-word-in-dictionary/