--- title: "Binomial Coefficients and Combinatorial Identities" description: "Read the binomial coefficient as a count and prove identities about it by counting one set two ways rather than by algebra." canonical: https://lightmysky.com/learn/mathematics/binomial-coefficients-and-combinatorial-identities-mt_lHXFvudTh6 source: https://lightmysky.com/learn/mathematics/binomial-coefficients-and-combinatorial-identities-mt_lHXFvudTh6.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Mathematics · Area: Discrete Mathematics · Ages 18 to 19 Page: https://lightmysky.com/learn/mathematics/binomial-coefficients-and-combinatorial-identities-mt_lHXFvudTh6 ## Ready when they can - 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 ## Lesson: One set, counted two ways 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. *(drawing: The entries count sizes 0, 1, 2 and 3. Their sum, 1 + 3 + 3 + 1 = 8, counts all subsets.)* 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. **Example.** 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. **Recap.** 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.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Permutations and Combinations](https://lightmysky.com/learn/mathematics/permutations-and-combinations-mt_1L58kuu-w3) - [The Binomial Expansion](https://lightmysky.com/learn/mathematics/the-binomial-expansion-mt_z16HZkNZ8c) ## Opens up - [The Pigeonhole Principle](https://lightmysky.com/learn/mathematics/the-pigeonhole-principle-mt_wgfpmZqzd9)