How many subsets does a set with 10 elements have? The answer, \(1{,}024\), does not need a direct count: it emerges from the sum of row \(n = 10\) of Pascal’s triangle. The binomial coefficient \(\binom{n}{r}\) satisfies identities that reinforce each other and make complex calculations surprisingly direct.
Why binomial coefficients? #
The identities of binomial coefficients reappear in central areas of computing and mathematics:
- Probability and statistics: the binomial distribution (a model of \(n\) independent trials with success probability \(p\)) has \(P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}\). A good part of the analysis of A/B tests, confidence intervals, and Bayesian classification models goes through this formula.
- Coding theory: the number of binary words of length \(n\) with exactly \(k\) bits equal to 1 (Hamming weight \(k\), that is, the number of 1 bits in the word) is \(\binom{n}{k}\). The Row Theorem, \(\sum_k \binom{n}{k} = 2^n\), says that the sum of all weight classes gives the total number of binary words.
- Algorithm analysis: exhaustive search algorithms that evaluate all subsets of size \(k\) have complexity \(\Theta\left(\binom{n}{k}\right)\). The symmetry \(\binom{n}{k} = \binom{n}{n-k}\) shows that evaluating subsets of size \(k\) costs the same as evaluating their complements of size \(n-k\).
- Polynomial expansion: the coefficients of \((1 + x)^n\) are exactly \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\). In machine learning, the number of polynomial features of degree \(\leq d\) generated from \(n\) input variables (features) is \(\binom{n+d}{d}\), directly tied to combination with repetition.
- Recurrences and dynamic programming: Pascal’s rule \(\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\) is the basis for memoizing the triangle, the same pattern of overlapping subproblems that makes dynamic programming (a technique of storing partial results to reuse them) efficient.
The map of identities #
The diagram below shows how the identities in this article relate to each other: Pascal’s rule generates the triangle, and the triangle reveals the three sum theorems.
flowchart TD
DEF["C(n,r): definition"] --> SIM["Symmetry
C(n,r) = C(n,n-r)"]
DEF --> FRONT["Boundary
C(n,0) = C(n,n) = 1"]
DEF --> PASCAL["Pascal's rule
C(n,r) + C(n,r+1) = C(n+1,r+1)"]
PASCAL --> TRI["Pascal's triangle"]
TRI --> LINHA["Row Theorem
∑ C(n,k) = 2ⁿ"]
TRI --> COL["Column Theorem
∑ C(k,r) = C(n+1,r+1)"]
TRI --> DIAG["Diagonal Theorem
∑ C(n+k,k) = C(n+r+1,r)"]
Binomial Coefficient #
Fundamental Identities #
Symmetry #
Combinatorial proof: choosing the \(r\) elements that go in is equivalent to choosing the \(n-r\) that stay out, because each subset of \(r\) elements corresponds to exactly one subset of \(n-r\) elements, its complement. Therefore, \(\binom{n}{r} = \binom{n}{n-r}\), which is what we wanted to prove. \(\blacksquare\)
Boundary and Secondary Identities #
Pascal’s Rule (Stifel) #
In Brazil, the rule is also commonly named after Michael Stifel, who published part of the triangle in 1544, in the Arithmetica integra.
Algebraic proof: starting from the definition and using the common denominator \((r+1)!(n-r)!\):
$$\binom{n}{r} + \binom{n}{r+1} = \frac{n!}{r!(n-r)!} + \frac{n!}{(r+1)!(n-r-1)!}$$$$= \frac{n! (r+1)}{(r+1)!(n-r)!} + \frac{n! (n-r)}{(r+1)!(n-r)!} = \frac{n! [(r+1)+(n-r)]}{(r+1)!(n-r)!}$$$$= \frac{n! (n+1)}{(r+1)!(n-r)!} = \frac{(n+1)!}{(r+1)!(n-r)!} = \binom{n+1}{r+1}$$Therefore, \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\), which is what we wanted to prove. \(\blacksquare\)
Combinatorial proof: from \(n+1\) objects, in how many ways can we choose \(r+1\)? Fix the object \(x\): either it is included (we choose \(r\) of the \(n\) remaining: \(\binom{n}{r}\)) or it is not (we choose \(r+1\) of the \(n\) remaining: \(\binom{n}{r+1}\)). The two cases do not overlap and cover all choices, so they add up. Therefore, \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\), which is what we wanted to prove. \(\blacksquare\)
The figure below illustrates the rule with the concrete example \(C(4,2) = C(3,1) + C(3,2) = 3 + 3 = 6\):
Pascal’s Triangle #
The triangle is much older than Pascal and was discovered several times, independently:
- India: Pingala’s Chandaḥśāstra (3rd or 2nd century BC) already counted the combinations of long and short syllables in verses; around the year 975, Halayudha, commenting on Pingala, described the triangle explicitly, under the name Meru-prastāra.
- Persia: al-Karaji (953-1029) described the triangle in a book now lost, and Omar Khayyam (1048-1131) used it to extract roots. In Iran, it is Khayyam’s triangle.
- China: Jia Xian (1010-1070) already knew it, and Yang Hui (1238-1298) presented it in the 13th century. There, it is Yang Hui’s triangle.
- Europe: Petrus Apianus published the complete triangle in 1527, Stifel part of it in 1544, and Tartaglia six rows in 1556. In Italy, it is Tartaglia’s triangle.
Blaise Pascal gathered the known properties and used them in probability problems in the Traité du triangle arithmétique, published after his death, in 1665, the same treatise that is often cited as the first explicit formulation of mathematical induction. The name “Pascal’s triangle” came later, with Montmort (1708) and de Moivre (1730). More at Pascal’s triangle.
Pascal’s rule lets us build the triangle iteratively: each element is the sum of the two above it in the previous row, with 1 at the ends of each row. Each position of the triangle corresponds to a binomial coefficient: the position in row \(n\) and column \(r\) contains exactly \(C(n, r)\). The figure below shows the triangle written in this notation:
Replacing each \(C(n,r)\) with its numerical value, we get the triangle that usually appears in books:
In row \(n\), column \(r\) contains \(\binom{n}{r}\).
Row Theorem #
Proof: In the binomial theorem \((a+b)^n\) (the topic of the next article), substitute \(a = b = 1\). Therefore, \(\sum_{k=0}^n \binom{n}{k} = 2^n\), which is what we wanted to prove. \(\blacksquare\)
Interpretation: the total number of subsets of a set with \(n\) elements is \(2^n\), and the sum of the coefficients in a row of the triangle confirms this directly. For \(n = 10\), this gives \(2^{10} = 1{,}024\), the answer to the opening question.
The figure below highlights row \(n = 5\) in the triangle, showing that \(1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5\):
Column Theorem #
Summing the \(r\)-th column of the triangle down to row \(n\) gives \(\binom{n+1}{r+1}\), the element immediately below and to the right of the last one summed. The figure below shows the triangle in a grid and highlights column \(r = 2\): the values \(1, 3, 6, 10, 15\) add up to \(35 = C(7,3)\).
Diagonal Theorem #
We add up elements along an ascending diagonal of the triangle and the result lies on the next diagonal. The figure below shows diagonal \(n = 2\): the values \(C(2,0), C(3,1), C(4,2), C(5,3)\) are connected in red and their sum points to \(C(6,3) = 20\) in amber.
Worked Examples #
Symmetry and the complexity of exhaustive search #
Problem: An algorithm evaluates all subsets of size \(k = 3\) and all those of size \(k = 17\) of a set with \(n = 20\) elements. How many subsets are evaluated in each case? What does symmetry imply?
Solution:
$$\binom{20}{3} = \frac{20 \times 19 \times 18}{3!} = \frac{6{,}840}{6} = \mathbf{1{,}140}$$$$\binom{20}{17} = \binom{20}{20-17} = \binom{20}{3} = \mathbf{1{,}140}$$The symmetry \(\binom{n}{r} = \binom{n}{n-r}\) has a direct practical consequence: evaluating subsets of size \(r\) costs exactly the same as evaluating their complements of size \(n - r\). The count is largest for \(r\) near \(n/2\) and smallest for \(r\) near \(0\) or \(n\). Therefore, algorithms that search for small or large subsets are more efficient than searches for subsets of medium size.
Sum of products of consecutive integers #
Problem: Compute \(S = 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \cdots + 50 \cdot 51 \cdot 52\).
Solution: Note that \(k(k+1)(k+2) = 6\binom{k+2}{3}\), since \(\binom{k+2}{3} = \frac{(k+2)(k+1)k}{6}\). Hence:
$$S = 6\sum_{k=1}^{50}\binom{k+2}{3} = 6\left[\binom{3}{3} + \binom{4}{3} + \cdots + \binom{52}{3}\right]$$By the Column Theorem with \(r = 3\), summing from \(k=3\) to \(52\):
$$\binom{3}{3} + \cdots + \binom{52}{3} = \binom{53}{4} = \frac{53 \times 52 \times 51 \times 50}{24} = 292{,}825$$$$S = 6 \times 292{,}825 = \mathbf{1{,}756{,}950}$$
Python: generating the triangle with dynamic programming
Dynamic programming is a technique that solves a complex problem by splitting it into smaller subproblems and storing the intermediate results to reuse them, instead of recomputing them from scratch at every step. Pascal’s triangle is a classic example: \(C(n,r)\) depends on \(C(n-1,r-1)\) and \(C(n-1,r)\), which were already computed in the previous row. Pascal’s rule \(\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}\) translates directly into code: each cell is the sum of the two above it. This avoids computing factorials and the risk of overflow for large \(n\).
def pascal(n):
tri = [[1] * (i + 1) for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, i):
tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j]
return tri
for row in pascal(7):
print(row)[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]The initialization [1] * (i + 1) fills the borders with 1; the inner loop overwrites
only the interior elements of each row. Complexity: \(O(n^2)\) in time and
space, the same cost as filling in the table by hand.
SQL: computing \(C(n,r)\) with WITH RECURSIVE
WITH RECURSIVE
A recursive common table expression (CTE) builds the table of factorials up to \(15!\); then, three joins compute \(C(n,r) = \frac{n!}{r! (n-r)!}\) for all \(0 \leq r \leq n \leq 8\).
WITH RECURSIVE fact(n, f) AS (
SELECT 0, 1
UNION ALL
SELECT n + 1, f * (n + 1) FROM fact WHERE n < 15
)
SELECT
a.n AS n,
b.n AS r,
a.f / (b.f * c.f) AS "C(n,r)"
FROM fact a -- a.n = row, a.f = n!
JOIN fact b ON b.n <= a.n -- b.n = column r, b.f = r!
JOIN fact c ON c.n = a.n - b.n -- c.f = (n-r)!
WHERE a.n <= 8
ORDER BY a.n, b.n;The result is a table with one row per pair \((n, r)\), equivalent to the triangle read row by row. Compatible with SQLite, PostgreSQL, and DuckDB.
Summary Table #
The three sum theorems share the same structure: in each one, one parameter stays fixed while the other varies along a row, column, or diagonal of the triangle. The panel below highlights this pattern with the fixed parameter in red:
| Identity / Theorem | Formula |
|---|---|
| Symmetry | \(\binom{n}{r} = \binom{n}{n-r}\) |
| Boundary | \(\binom{n}{0} = \binom{n}{n} = 1\) |
| Secondary | \(\binom{n}{1} = \binom{n}{n-1} = n\) |
| Pascal’s Rule (Stifel) | \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\) |
| Row Theorem | \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\) |
| Column Theorem | \(\displaystyle\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}\) |
| Diagonal Theorem | \(\displaystyle\sum_{k=0}^{r} \binom{n+k}{k} = \binom{n+r+1}{r}\) |
Exercises #
The following exercises apply the identities of the article: combinatorial proofs, reading the triangle, and use of the Row and Column Theorems. They are ordered from simplest to most complex.
Exercise 1: Generalized Pascal identity
Prove, using a combinatorial argument, that:
$$\binom{n+2}{p+2} = \binom{n}{p} + 2\binom{n}{p+1} + \binom{n}{p+2}$$
Proof
Consider the set \(\{a_1,\ldots,a_n, x, y\}\) with \(n+2\) elements. We count subsets of size \(p+2\) by cases:
- Neither \(x\) nor \(y\): \(\binom{n}{p+2}\)
- Exactly \(x\) or exactly \(y\) (2 cases): \(2\binom{n}{p+1}\)
- Both \(x\) and \(y\): \(\binom{n}{p}\)
The three cases do not overlap and cover all subsets of size \(p+2\). Therefore, \(\binom{n+2}{p+2} = \binom{n}{p} + 2\binom{n}{p+1} + \binom{n}{p+2}\), which is what we wanted to prove. \(\blacksquare\)
Exercise 2: Eighth row of the triangle
Build row \(n=8\) of the triangle from row \(n=7\): \(1\ 7\ 21\ 35\ 35\ 21\ 7\ 1\).
Solution
Adding adjacent pairs and keeping 1 at the ends:
$$1\quad 8\quad 28\quad 56\quad 70\quad 56\quad 28\quad 8\quad 1$$
Exercise 3: Number of elements from subsets
If a set \(A\) has 512 subsets, what is \(|A|\)?
Solution
By the Row Theorem, a set with \(n\) elements has exactly \(2^n\) subsets. We just need to solve:
\(2^n = 512 = 2^9 \Rightarrow n = \mathbf{9}\)
Exercise 4: Cocktails with 2 or more ingredients
How many cocktails (mixtures of ≥ 2 ingredients) can be made with 7 distinct ingredients?
Solution
Subsets of size ≥ 2: \(2^7 - \binom{7}{0} - \binom{7}{1} = 128 - 1 - 7 = \mathbf{120}\)
Exercise 5: Proof by the Column Theorem
Prove that \(\displaystyle\sum_{k=1}^n k = \dfrac{n(n+1)}{2}\).
Proof
Write \(k = \binom{k}{1}\):
$$\sum_{k=1}^n \binom{k}{1} = \binom{n+1}{2} = \frac{(n+1)n}{2}$$Therefore, \(\displaystyle\sum_{k=1}^n k = \dfrac{n(n+1)}{2}\), which is what we wanted to prove. \(\blacksquare\)
Next steps #
The identities in this article reveal the internal structure of \(\binom{n}{r}\), but they do not explain why this coefficient appears in products of powers. When we expand \((a+b)^n\), the coefficients that appear in each term \(a^k b^{n-k}\) are exactly \(\binom{n}{k}\), and the Row Theorem is nothing more than the case \(a = b = 1\) of this expansion. This is the binomial theorem, the topic of the next article in the series.
