Binomial Coefficients and Combinatorial Identities
Read the binomial coefficient as a count and prove identities about it by counting one set two ways rather than by algebra.
What a learner can do afterwards
- Prove Pascal's rule by splitting the selections according to whether one element is chosen
- Give a counting argument for the sum of a row of Pascal's triangle
- Prove Vandermonde's identity by counting a mixed selection two ways
1 · Read
The binomial coefficient C(n, r) counts the r-person groups you can form from n people. Compute it as n factorial divided by r factorial times n minus r factorial. For example, C(5, 2) is 5 times 4 divided by 2 times 1, or 10, and C(9, 2) is 9 times 8 divided by 2, or 36. A binomial coefficient always comes out a whole number.
Fix one person, say Ana, and split every pair from 6 people by whether it holds her. Pairs that skip Ana choose 2 from the other 5, and pairs that hold her choose 1 more from the other 5. That split is Pascal's rule: C(6, 2) equals C(5, 2) plus C(5, 1), or 10 plus 5, which is 15.
Add a whole row of Pascal's triangle by giving each of n people a say: in or out. Each person has 2 choices, so the row sums to 2 to the power n. Row 4 reads 1, 4, 6, 4, 1, and sums to 16, which is 2 to the power 4.
Vandermonde's identity counts one mixed team two ways. Take 2 juniors and 3 seniors and form 2-person teams. Directly, that is C(5, 2), or 10. Split by juniors on the team: 0 juniors with 2 seniors gives 1 times 3, 1 with 1 gives 2 times 3, and 2 with 0 gives 1 times 1. Adding gives 3 plus 6 plus 1, or 10 again.
Read C(n, r) as a count, split selections on one person for Pascal, and count one team two ways for Vandermonde.
2 · Watch
Take it off screen
Where it sits
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.