- #1
foxjwill
- 354
- 0
[SOLVED] Binomial Coefficient
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:
I don't really understand, conceptually, why he splits the piles like he does. Any help?
I looked at the established binomial coefficient, and it works out and all, but that didn't help me understand it.
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 [tex]f(n,k)[/tex] is the answer to the question [the binomial coefficient]. We imagine that the collection of all possible subsets of [tex]k[/tex] of these [tex]n[/tex] 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 `[tex]n[/tex]', and into the second pile we put all subsets that do not contain `[tex]n[/tex]'. The first of these piles obviously contains [tex]f(n-1, k-1)[/tex] subsets. The second pile contains [tex]f(n-1, k)[/tex] 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.
Last edited by a moderator: