N-choose-k is defined to be the number of ways one can select k objects from a pool of n objects. So you might use n-choose-k to figure out how many ways you can seat 7 people in 4 chairs, or draw 3 marbles from 5 different colored marbles.
I received several questions about Dr. Osborne's hint. In cases like this it almost always helps to draw a picture. Let's try to illustrate 5 choose 3.
Here are our five objects:
* * * * *Let's select the first object (the one on the left):
O * * * *Now, once we've selected one object, we can select two more. Here are the different ways we can take the other two:
O O O * * O O * O * O O * * O O * O O * O * O * O O * * O OBut if we ignore the first object (the one we picked), we see:
O O * * O * O * O * * O * O O * * O * O * * O O...which is the illustration for 4 choose 2.
But that was only for the case where we pick the first object. What if we had picked, say, the second or third object first?
Then the picture might look like:
* O O O * | * O O * O for picking the second object first * O * O O | * * O O O for picking the third object firstBut if we cover up the first object again, we get:
O O O * O O * O O * O O * O O O...which is our illustration for 4 choose 3.
So we can actually write
5 choose 3 = (4 choose 3) + (4 choose 2)
or, more generally
n choose k = (n-1 choose k) + (n-1 choose k-1)
So we have defined n-choose-k in terms of itself. Once we've done that,
we are able to write a recursive definition:
* For the recursive case,
n choose k = (n-1 choose k) + (n-1 choose k-1)
But what are our base cases?
Well, let's suppose n == k. If this is the case, there's clearly only one way to take n-choose-k.
Or how about if k == 1? If this is the case, then there're n different ways to take n-choose-k.
So, we might complete the definition of the function with
* For the recursive case,
n choose k = (n-1 choose k) + (n-1 choose k-1)
* For the base cases,
n choose n = 1
n choose 1 = n,
where we assume
n >= k > 0
Iterative Definition
The iterative definition was, again:
n!
n choose k = ----------
(n-k)! k!
...but where does this come from?
Well, let's suppose you're going to take one object from n objects. How many different objects might you have? N different. If you choose to remove another, you could have any one of (n-1) objects. Put together, there could be any of n (n - 1) cases.
But for n-choose-k, order isn't important. That is, let's say you removed object 3 first, and then object 4. If you had removed object 4 first, and then object 3, this would be considered the same case.
So, for removing 2 objects from n, while there are n (n - 1) different possibilities, there are only
n (n - 1)
---------
2!
distinct cases - where 2! is 2 factorial: the number of different ways
you could arrange 2 objects.
If you removed three objects from n, there are n (n - 1) (n - 2) different ways, and
n (n - 1) (n - 2)
-----------------
3!
distinct cases (disregarding the order.)
For the general case: removing k objects from n objects, we can have
n (n - 1) (n - 2) .... (n - k + 2) (n - k + 1)
different ways, and
n (n - 1) (n - 2) .... (n - k + 2) (n - k + 1)
----------------------------------------------
k!
distinct cases.
But the numerator can be rewritten as
n!
--------
(n - k)!
and we obtain the iterative definition of n-choose-k,
n!
n choose k = ----------- , n >= k > 0
(n - k)! k!