C(N,k) = C(N-1,k-1) + C(N-1,k)
How did this formula come into existence? What is the intuition behind this recursive formula?
Here's my shot at explaining this equation:
Suppose you have a BIG basket of size N and has N items in it and another smaller basket of size 'k' in which you are supposed to put k items from the big basket. C(N,k) now just means the number of ways you can choose 'k' items from the BIG basket and put it in your smaller basket.
Before we delve into approaching the problem let's look at the trivial case of choosing things.
How many ways can you choose one item if you have only one item? You guessed it, it's just one.
Similarly how many ways can you choose N items from N items? You guessed it again, there's just one way of choosing them.
So now we can say C(z,z) = 1, also implying C(1,1) = 1
The other smaller piece of the puzzle you need to think about is not choosing any items when I have 'm' items with me. So how many ways can I do this? The answer is obvious you can only do this one way (just sit idle!)
So we can say C(m,0) = 1, also implying C(1,0) = 1
So now we'll look at another piece of the puzzle: By looking at the two intuitions we developed above. What can you say about you smartly stopping to pick items a particular way?
You stop picking items in the case where there are Z items to pick and there are only Z items left. This includes leaving only one item and picking that one.
Now armed with this background we can go about solving the complete puzzle.
We humans are brilliant, we always try to break up problems into manageable pieces and try to solve them. This is how recursion works. We divide the problem into a readily solvable part (for which we know the answer) and a part which needs further computation
So what I do is approach the problem solving for one item at a time.
I pick an item from the N items in the BIG basket and then I ask myself what can I do with this item in my hand. We can do a lot of things like throw it, eat it.. etc. but I can do one of the two things which are of interest to me in this problem:
I can place it my smaller basket
I can not place it my smaller basket, just place it beside my BIG basket
In the first case as I have placed that item in the smaller basket, I just have to choose 'k-1' items of the 'N-1' items present. So now I should worry about computing the number of ways I can do that.
In the the second case as I have not placed that item in the smaller basket I still have to choose 'k' items from 'N-1' items in the BIG basket. I have to worry about the number of ways I can go about doing this.
So solving this big puzzle now becomes: Summing up these two ways. I note this down in a book. I have two problems to solve now. I go about solving them one after another and go deeper and deeper into trying to solve a smaller problem
I keep track of all the things I did till now and I keep going deep over and over again until I reach one of trivial cases:
Compute the number of ways of choosing Z items of Z items in the BIG basket
Compute the number of ways of choosing no items of the Z items in the BIG basket
Both these are one and I propagate this result to the previous equation which had a dependency on this.
Finally when I finish solving all these problems and finish adding up all the way from bottom to top I've solved the complete puzzle.
A trivial C code explaining N choose K using recursion: I love writing code and can't stop myself from not writing one.
int C(int n, int k)
if(n == k || k == 0) return(1);
else return(C(n-1,k-1) + C(n-1,k));
Hope this cleared up things for you. Leave comments if you've got any questions or doubts or if you spot any typos and errors.