• Support PF! Buy your school textbooks, materials and every day products Here!

Binomial Coefficient

  • Thread starter foxjwill
  • Start date
354
0
[SOLVED] Binomial Coefficient

1. Homework Statement
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 [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?
2. Homework 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:

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
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).
 
354
0
Oh. That makes sense. Thanks so much!
 

Related Threads for: Binomial Coefficient

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
631
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
2
Replies
29
Views
6K
Top