Session 6B
Combinations and binomial coefficients
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- The binomial coefficient C(n,k), read "n choose k," counts how many ways to choose a k-element subset from an n-element set when order does not matter. It is defined by the formula C(n,k) = n!/(k!(n-k)!), but proof-based combinatorics prefers reasoning over formula memorization. A key identity is Pascal's identity: C(n,k) = C(n-1,k) + C(n-1,k-1). The cleanest proof is a counting argument: count k-person committees from n people by splitting into committees that include a particular person versus those that do not.
- Another fundamental identity is symmetry: C(n,k) = C(n,n-k), because choosing k elements to include is equivalent to choosing the n-k elements to exclude. These are best understood via bijections rather than algebra. In proof-based math, you learn to justify formulas, not just apply them. Once you can build and explain these identities with words and logic, you can handle more advanced counting problems without getting lost in algebraic manipulation.
Practice
- 1Prove Pascal identity using counting.
- 2Prove: C(n,k) = C(n,n-k).
- 3Compute C(10,3).
MCQ
C(n,k) counts: