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
You have counted groups by dividing out their orders. For integers n >= 0 and 0 <= r <= n, C(n,r) counts r-element subsets of n distinct elements: n! / (r! × (n-r)!). For example, C(8,2) = (8 × 7) / 2 = 28. These counts are whole numbers. Choosing nothing or everything gives one subset. For integer r outside 0 through n, use C(n,r) = 0.
Pascal's rule is C(n,r) = C(n-1,r) + C(n-1,r-1), for n >= 1 and 1 <= r <= n. Fix one element. Subsets excluding it choose r from the other n-1; subsets including it choose r-1 more. Every subset belongs to exactly one case, so add. For example, C(5,1) = C(4,1) + C(4,0) = 4 + 1 = 5. Subtracting either case count recovers the other.
Number Pascal's rows from row 0, which is just 1. Row n lists C(n,0) through C(n,n), counting subsets by size. Each of n elements can be included or excluded, giving 2^n subsets altogether. Adding the row counts those same subsets by size, so its sum is 2^n. Both endpoints matter: the empty subset and the full set each contribute one. The sum counts all sizes, not one fixed size.
Vandermonde counts r-element subsets from disjoint pools of sizes a and b. Directly there are C(a+b,r). If k come from the first pool, r-k come from the second, giving C(a,k) × C(b,r-k). Sum these products for k=0 through r. Impossible choices contribute zero. Each subset has exactly one first-pool count k, so the cases cover all subsets without overlap. This proves the identity for nonnegative integer a, b, r with r <= a+b.
Choose 3 people from 3 artists and 4 writers, with nobody in both pools. Teams with 0 artists number 1 × 4 = 4; with 1 artist, 3 × 6 = 18; with 2 artists, 3 × 4 = 12; with 3 artists, 1 × 1 = 1. Adding gives 35, also C(7,3). Multiply choices within a case and add the disjoint cases.
Read C(n, r) as a count, split selections on one person for Pascal, and count one team two ways for Vandermonde.
Lesson and practice text written for this dataset. Counting resources were consulted for mathematical facts and question-design study.
Readings and extra questions written for this dataset. Video links are credited to Khan Academy in the source catalog; their publisher terms are unverified.
More to read
Which brackets supply y?
Multiply n copies of (x+y), where n is a nonnegative integer. Each product chooses one term from each bracket. To obtain x^(n-r)y^r, choose exactly r brackets to supply y. The remaining brackets supply x. There are C(n,r) choices of those brackets, explaining the coefficient. This also explains the endpoint coefficients: there is one way to choose no brackets and one way to choose all of them. Throughout this counting interpretation, r is an integer from zero through n.
Check both parts of a partition
Mark one element of a set with n elements. To count its r-element subsets, separate those containing the mark from those excluding it. The containing case chooses r-1 further elements; the excluding case chooses all r from the other n-1. No subset belongs to both cases, and every subset belongs to one. Adding proves C(n,r) = C(n-1,r-1) + C(n-1,r). The proof works for every allowed n and r, rather than checking only one calculation. When a case requests more elements than are available, its count is zero.
Explain both counts
A counting proof identifies one collection and explains two counts of it. For a Pascal row sum, the collection contains all subsets. Independent inclusion decisions give 2^n; sorting subsets by size gives the sum of the row. Both counts include the empty subset. For Vandermonde, the collection contains fixed-size subsets from two disjoint pools. Sort them by the number chosen from the first pool. Multiply the two pool counts within a case, then add all possible cases. Explain why no subset is omitted or counted twice.
Explore more
2 · Watch
En anglaisTake it off screen
Where it sits
This opens up
14 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.