Subset counting and Pascal recurrence
An n-element set has 2ⁿ subsets; its k-element subsets correspond to length-n binary strings with k ones.
Key knowledge
An n-element set has 2ⁿ subsets; its k-element subsets correspond to length-n binary strings with k ones. Their number is C(n,k), with C(n,0)=C(n,n)=1. For n≥2 and 1≤k≤n−1, Pascal’s recurrence is C(n,k)=C(n−1,k−1)+C(n−1,k). C(n,k) is also the coefficient of xᵏyⁿ⁻ᵏ in (x+y)ⁿ.
Conditions and scope
- 0≤k≤n are integers and subset order is ignored.
- Ordered selections and selections with repetition are different counting problems.
- The displayed Pascal recurrence applies to interior coefficients, n≥2 and 1≤k≤n−1; endpoint values are supplied separately, including C(0,0)=1.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Finite subset/bit-string correspondence, binomial coefficient interpretation and Pascal’s recurrence for interior coefficients; endpoint identities are separate.
2026-10-10 · Independent Physics and Measurement reference editor (AI editorial bounded review). Exact bounded introductory reference claims and this practical concept inventory are approved after closure. Existing university/research proof and source scopes remain separate; no universal knowledge-completeness or experimental-validation assertion.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Scope or convention differs
Unordered choices, binomial coefficients, Pascal recurrence and binomial expansion.
The repository explicitly covers the empty choice and uses binary subsets to state the total two-to-n count.
University of Cape Town, Department of Mathematics and Applied Mathematics
- MAM1000W Calculus notes South AfricaEnglish
§§8.2–8.4, printed pp.72–77 (PDF pp.75–80)
- MAM1000W Calculus notes
Entry details
Permanent link to this entry ↗- Record identity
- math-binomial-counting
- Revision
- foundations-audit.1
- Structured reference record
- University core expansion