Understanding the Binomial Coefficient through Generating Functions

[foxjwill]

[SOLVED] Binomial Coefficient

Homework Statement

I'm reading the textbook http://www.math.upenn.edu/~wilf/DownldGF.html" , 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)​

(bold added by me).

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

Homework Equations

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.

 

[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).

 

[foxjwill]

Oh. That makes sense. Thanks so much!