# Binomial Coefficient

1. Apr 23, 2008

### foxjwill

[SOLVED] Binomial Coefficient

1. The problem statement, all variables and given/known data
I'm reading the textbook http://www.math.upenn.edu/~wilf/DownldGF.html" [Broken], and in section 1.5, the author explains how to derive the binomial coefficient via a generating function approach.

One of the things he mentions as obvious, isn't (at least to me). Maybe it's just because it's morning and I'm not thinking correctly, but anyway, here's what it is:

"Suppose $$f(n,k)$$ is the answer to the question [the binomial coefficient]. We imagine that the collection of all possible subsets of $$k$$ of these $$n$$ objects are in front of us, and we will divide them into two piles. In the first pile we put all of those subsets that do contain the object $$n$$', and into the second pile we put all subsets that do not contain $$n$$'. The first of these piles obviously contains $$f(n-1, k-1)$$ subsets. The second pile contains $$f(n-1, k)$$ subsets." (bold added by me)​

I don't really understand, conceptually, why he splits the piles like he does. Any help?
2. Relevant equations

3. The attempt at a solution
I looked at the established binomial coefficient, and it works out and all, but that didn't help me understand it.

Last edited by a moderator: May 3, 2017
2. Apr 23, 2008

### Dick

He's trying to suggest how to find f(n,k) if you know all of the values of f(n-1,...). He does this by imagining removing an object ni from the set leaving n-1 objects to choose from. Now imagine how this affects the sets that f(n,k) is counting. If the set did not contain the ni to begin with, it remains unchanged (so there are f(n-1,k) of them). If the set did contain the ni, then it's size drops to k-1 (so there are f(n-1,k-1) of them).

3. Apr 23, 2008

### foxjwill

Oh. That makes sense. Thanks so much!