Thursday, March 1, 2012

Number of k-combinations for all k

This is an equations that comes up quite commonly in algorithm analysis:

here is an intuitive understanding for this.

Assume we have 10 items.
And we need to find sum of all possible combinations of these
i.e. 0C10 + 1C10 + 2C10 .....

What we are doing is basically we have 10 positions and in that we have 10 elements (since its a combination order does not matter). And in each position we have a choice for the item to be included or Not-included. So its a binary choice for each position and since we have 10 positions its 2x2 10 times i.e. 2^10.

So for n positions we have 2^n possible ways we can select these items.


If you still want a further rephrasing of the same information you can read this : http://www.themathpage.com/aprecalc/permutations-combinations-2.htm#sum

Enjoy!