The intuition behind computing combinations recursively (N choose K)

Note: I have rewritten this article to make it more straightforward, and also I have corrected a lot of grammatical errors.

With this article, I plan to explain the intuition behind the following “recursive” formula.

{N \choose k}={N-1 \choose k-1}+{N-1 \choose k}
or
C(N,k) = C(N-1,k-1) + C(N-1,k)

Let’s start by building a mental model, imagine that you have two baskets with you. Let’s call the first as B_1, has a capacity of N and is full. The second, B_2 has a capacity k (for clarity, k \leq N) and empty. For simplicity, let’s assume that all items are distinct and distinguishable.

The idea of choosing k items from N is nothing but counting the number of ways you can pick k items from B_1 and put it in B_2.

Another critical thing to note is that, while computing combinations, the order of how you choose those k items is unimportant, the only thing that matters is what items you choose. Choosing k items from N is mathematically denoted as {N \choose k} and I shall be using this notation from now on.

One way to approach a problem recursively is to see if it makes sense to decrease the problem size by one and delegate the problem to someone else. Let’s do just that, and pick an item out of B_1. Now you can either put it in B_2 or keep it aside. Each choice leads to interesting consequences:

Case 1: The item was placed in B_2, so now B_1 has N-1 items in it, and you can only put k-1 items in B_2. So now you have to choose k-1 items from N-1 items or in other words {N-1 \choose k-1}.

Case 2: The item was placed aside (not in B_2), consequently B_1 has N-1 items in it, but B_2 is still empty and you can still put k items in it. This translates to you having to choose k items from N-1 items or in other words {N-1 \choose k}.

We can conclude that the number of ways of choosing k items from N is the sum of:

  • Number of ways of choosing k-1 items from N-1
  • Number of ways of choosing k items from N-1.

Thus we have derived the recursive equation, {N \choose k}={N-1 \choose k-1}+{N-1 \choose k}.

Are we done? No, not yet. We still haven’t discussed another crucial thing when it comes to recursion, the base cases. Base cases are how the recursive formulae yield an outcome.

Q1) What is {N \choose N}?

A: We have only one way of choosing all the items from B_1 and putting them into B_2. Hence, we can also conclude that {1 \choose 1} is 1.

Q2) What is {N \choose 1}?

A: We have N choices, hence N ways of choosing one item from N items.

Let us make how we stop our recursion a bit smarter by considering the following case:

Q3) What is {N \choose N-k}?

A: Choosing k items out of N is the same as not choosing N-k items out of N. Hence, you have {N \choose k} = {N \choose N-k}. You can derive some interesting results out of this, here are a few

  • {N \choose 0} = {N \choose N} = 1
  • {N \choose N-1} = {N \choose 1} = N

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s