PineWiki- More examples of product rule
- Permutations: number of bijections from [n] to [n] is n! = n(n-1)(n-2)...1.
k-permutations: number of injections from [k] to [n] is n(k) = n(n-1)...(n-k+1)
- E.g. counting the number of sequences of 5 cards we can deal from a 52-card deck
- But what if we don't care about order?
- Counting two ways
- C(n,k) [n choose k] = |{A⊆S: |A| = k}|
- We'll count these by connecting them to P(n,k)
Method 1: P(n,k) = n(k) (already done)
- Method 2: P(n,k) = C(n,k)⋅k! (choose the subset then order it)
So P(n,k) = C(n,k)⋅k! ⇒ C(n,k) = n(k)/k! = n!/(k!(n-k)!)
- C(n,k) [n choose k] = |{A⊆S: |A| = k}|
- Reducing to previous case
- n identical balls in k bins
- No restrictions: place k-1 dividers among n+k-1 spaces to get (n+k-1 choose k-1)
- All bins nonempty: remove k balls and reduce to previous case
- n identical balls in k bins
- Binomial coefficients
- Definition in terms of factorials: already given
- Comes from binomial theorem
- Recursive definition using Pascal's identity: (n choose k) = (n-1 choose k) + (n-1 choose k-1)
- Easy combinatorial proof
- Painful algebraic proof
Algebraic identity proofs are an example of GeneratingFunctions