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,B | 1 | (A,B) |

3 - A,B,C | 3 | (A,B);(B,C);(C,A) |

4 - A,B,C,D | 6 | (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