## Sunday, 16 October 2011

### Permutations? Or Combinations? Why Confusion!!!

Combination is for selection where as Permutation is for selection and arrangement (putting in order). Order may be linear like “right to left” or “left to right”, or may be circular like “clockwise” or “anticlockwise”.
We consider one example of selecting 2 persons from A,B,C.
We can select A&B or B&C or A&C – total 3 possibilities. There ends combinations.
If we need to arrange the selected persons, we will get the following possibilities- AB,BA,BC,CB,AC,CA – total 6 possibilities. These are permutations. Here we have observed that permutations include selection and
arrangement. Got the difference between the two? That’s it!
The above concept can be formulised as below:
No. Of way of selecting 2 out of 3 persons = 3C2 = (3!)/ (3-2)! (2!) = (3*2*1)/ (1)(2*1) = 3
No. Of ways of arranging 2 from given 3 persons = 3P2 = (3!)/ (3-2)! = (3*2*1)/ (1) = 6
Number of possibilities of selecting r items out of n items = nCr
Number of possibilities of arranging r items out of n items = nPr
nCr = (n!)/ (n-r)! (r!)
nPr =(n!)/ (n-r)!
Some useful deductions here:
Prior to proceeding for the deductions, I will brief on factorial. Factorial is defined for all whole numbers. ie., n=0,1,2,3,....
n! = n * (n-1) * (n-2) *(n-3) *...3 * 2 * 1
n! = n * (n-1)!
0! = 1; 1! = 1;
nC0 = n!/(n-0)! 0! = 1;  nC1 = n!/(n-1)! 1! = n;  nCn = n!/(n-n)! n! = 1
nCr = nC(n-r)
nPr = nCr * (r!) = nCr * rPr
nPr is generally greater than nCr excepting the case where r=1, in which case nPr becomes equal to nCr

“Repetitions are allowed”:
Up to now we discussed about no-repetitions case. Now we will see the case “if repetitions are allowed”. For that we will take the example of forming different numbers using given digits:
Given numbers are 6, 7, 8. We need to form different 2-digit numbers (here repetitions are allowed).
The possibilities are:
66, 77, 88                  – repetition cases
67, 76, 68, 86,78, 87   – no repetition cases
-   Total possibilities are “9”. Here we are considering permutations (as we have taken care of the order of digits for example 78 and 87). But the earlier nPr formula won’t work here (observe 3P2 =6 but not 9) as repetitions are allowed here. The formula here is nr. (Observe 32 = 9)
Number of possibilities of arranging r items out of n items if repetitions are allowed = nr

Circular Permutations:
Why not “circular combinations”? Its absurd because the word “circular” here hints some arrangement. “Arrangement” indicates permutations only but not it’s counter-part.
Find all possibilities of arranging 3 persons A,B,C around a circular table?

In circular permutations, relative positions only are considered but not exact positions. For that reason, all the three possibilities -ABC,BCA and CAB comes under category-1 and similarly ACB,CBA and BAC comes under category-2.  So we get only two possibilities as mentioned in the diagram.
The formula here is (n-1)!
The number of possibilities of arranging n-different things in circular order = (n-1)!
If the things considered are identical, then clock-wise and anti-clockwise won’t matter. And the number of possibilities gets halved.
The number of possibilities of arranging n-identical things in circular order = (n-1)!/2
The examples for this case are like flowers in a garland, beads in a necklace etc.,etc.