Thursday, September 17, 2009

combination formula and recursion

Today, while solving some problems in counting I tried to relate the combination formula and recursion.
The idea is, can we derive combination formula using recursion?

Let us start with a particular case.

How many ways can we make groups of 2 out of n people?

Let T(n) be the answer for n people.
Let us think wishfully and see if we can get to solution for n when solution for n-1 is known.

[n][# of pairs][pairs]
2 - A,B1(A,B)
3 - A,B,C3(A,B);(B,C);(C,A)
4 - A,B,C,D6(A,B);(B,C);(C,D);(D,A);(A,C);(B,D)

From above table, it is easy to observe that
T(n) = T(n-1) + (n-1)
We can solve this recurrence using substitution and see that
T(n) = n(n-1)/2
which is indeed (n combination 2).

How many ways can we make group of k ppl out of n ppl?

Let it be denoted by T(n,k).
Clearly, T(k,k) = 1
We can apply the process as in above case by solving for T(n,3), T(n,4) etc and easily see that
T(n,k) = T(n-1, k) + T(n-1, k-1)

No comments:

Post a Comment