## Tuesday, 18 October 2011

### Permutations & Combinations - All possible selections

All possible selections (dissimilar things)

In this case there is no bar on ‘r’ term. Out of all given ‘n’ things, we can select 1 thing or 2 things or 3 things.... up to ‘n’ things at a time.
Number of ways of selecting 1 thing from n things = nC1
Number of ways of selecting 2 things from n things = nC2
and so on and so on......
Number of ways of selecting n things from n things = nCn
Total number of selections     = nC1 + nC2 + nC3 + .... + nCn
From binomial theorem, nC0 + nC1 + nC2 + nC3 + .... + nCn = 2n
nC1 + nC2 + nC3 + .... + nCn = 2n - nC= 2n – 1
Number of all possible selections from given ‘n’ things = 2n – 1

All possible selections (similar things)

If p things are alike of one kind, q things are alike of second kind and r things are alike of third kind,
then the number of ways of selecting any number of things out of these is
(p+1) (q+1) (r+1) – 1
Explanation:
As similar things exist in each set, we can not simply apply nPr or nCr.
From the first set of p similar things, all possible selections are:
selecting nothing, selecting 1 thing, selecting 2 things, etc., etc., selecting p things ------   (p+1) ways.
Similarly for the second set    --------  (q+1) ways
and for the third set               --------   (r+1) ways
Fundamental principle says that, if one work can be performed in m ways and second work in n ways, then two works can be performed in m*n ways. Applying that,
the total number of ways becomes: (p+1) (q+1) (r+1)
But this includes a combination of no selections at all. If we remove that particular combination, the answer becomes:  (p+1) (q+1) (r+1) - 1

Selection of consecutive things:

Consider the following things which are in a row
A B C D E F G
Select two consecutive things from the above row:
The possibilities are: AB, BC, CD, DE, EF, FG - total 6 ways. Analysing this in reverse-calculation method,
6 = 7 – 2 + 1 = (number of things given) – (number of things to be selected) + 1 = n- r + 1
Number of ways of selecting ‘r’ consecutive things from ‘n’ things in a row = n-r+1