Permutations and Combinations

June 06, 2019 2 minutes

Before we look into various mathematical formulas, the first thing is to understand the difference between permutation and combination. Consider the following two scenarios:

  1. Selecting 2 students from a class of 30 students to collect notebooks from rest of the students.
  2. Entering the unlock code on your cell phone.

As you notice, in the first case the order does not matter; i.e. the students (say a,b) can be selected in any order {a,b} or {b,a}, the end result remains same. But in the second scenario, the order does matter as entering the code (even if the individual numbers are correct) out of order will NOT unlock the phone. If the unlock code is 1234, it can not be opened with any other order like 1243 or 3214 etc.

If we can ignore the order, the result is a combination whereas a permutation strictly follows an order.

Mathematical Representations

  1. Permutation of n objects taken r at a time is given by: $P(n,r) = \frac{n!}{(n-r)!}$
  2. Permutation of n objects with repititions (x items of type1; y items of type2 and say z items of type3) = $\frac{(x+y+x)!}{x! * y! * z!} = \frac{n!}{x! * y! * z!}$ (as $x+y+z = n$)
  3. Combination of n objects taken r at a time is given by: $C(n,r) = \frac{n!}{r!(n-r)!}$

In other words, we can say that $C(n,r) = \frac{P(n,r)}{r!}$

Examples

How many words can be formed with the letters of the words “COMPUTER”?

As there are only unique characters in the word COMPUTER:

  1. Starting from the first character, it can take 8 of the available positions.
  2. The next can take any one of the remaining 7 positions.

then 6,5 and so-on.

So the total possible words that can be made by re-arranging the characters of the word COMPUTER is: $8*7*6*…2*1 = 40320$. Now as we can clearly see, the order of the characters does matter in the various outcomes, this is equivalent of selecting $n$ items out of $n$ available with the order maintained i.e. $P(n,n)$ which is actually equal to $n!$.

How many words can be formed with the letters of the words “KRAKATOA”?

In this example, we have $n=8$ with K and A repeating $2$ and $3$ times respectively. The total permutations of this can be calculated as $\frac{8!}{2! * 3!} = 3360$

comments powered by Disqus