The idea: a triangle of sums
Pascal's triangle starts with a single 1 in row 0. Each next row has one more number. The two edges are always 1, and every inside number is the sum of the two numbers above it. Rows 0 to 8 are 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; … up to 1 8 28 56 70 56 28 8 1. (Demo 1: build rows 1-8)
On the canvas, building a row takes three steps: the numbers of the row above light up and each is copied twice, the copies fly down-left and down-right, and each new cell adds what it received. An edge cell receives only one copy, so it stays 1.
Binomial coefficients C(n,k)
Number the rows n = 0, 1, 2, … from the top and the positions k = 0 … n from the left. The number in row n, position k is the binomial coefficient C(n,k), read "n choose k": the number of ways to choose k things out of n. It has a closed formula:
C(n,k) = n! / (k! · (n−k)!) e.g. C(4,2) = 24 / (2 · 2) = 6.
The sum rule of the triangle is Pascal's rule: C(n,k) = C(n−1,k−1) + C(n−1,k). To choose k of n items, either the last item is chosen (choose k−1 more from the other n−1) or it is not (choose all k from the other n−1). The rows are symmetric because choosing k items is the same as leaving out n−k: C(n,k) = C(n,n−k).
Counting paths
Start at the top and move down n times, each time down-left (L) or down-right (R). You end in row n at position k = the number of R moves. So the paths to C(n,k) are the L/R strings of length n with exactly k R's, and there are C(n,k) of them: choose which k of the n moves are R. The six paths to C(4,2) are LLRR, LRLR, LRRL, RLLR, RLRL and RRLL. (Demo 2: paths to C(4,2))
The path view also explains the sum rule: the last move into a cell comes from the upper-left cell or the upper-right cell, so its path count is the sum of theirs. The same idea counts paths in a grid with dynamic programming: fill a table where each entry adds up smaller entries.
The binomial theorem: (a+b)ⁿ
Multiply out (a+b)⁴ = (a+b)(a+b)(a+b)(a+b). Each term of the product picks a or b from every factor. A term with k b's and 4−k a's can be picked in C(4,k) ways, so
(a+b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴.
In general (a+b)ⁿ = Σk=0..n C(n,k) an−k bk: row n holds the coefficients. (Demo 3: expand (a+b)⁴) Picking b from a factor is the same choice as an R move on a path.
Row sums are 2ⁿ
Row n adds up to 2ⁿ: 1, 2, 4, 8, … 256 for row 8. Two ways to see it:
- Every number is copied into two cells of the next row, so each row sums to twice the row above.
- Put a = b = 1 in the binomial theorem: (1+1)ⁿ = 2ⁿ = C(n,0) + C(n,1) + … + C(n,n).
In path terms: there are 2ⁿ L/R strings of length n, and each ends in exactly one cell of row n. (Demo 5: row sums) Other patterns hide in the triangle too: the second diagonal is 1, 2, 3, 4, …, the third is the triangular numbers 1, 3, 6, 10, …, and a diagonal run adds up to the number just below its end (the hockey-stick identity, e.g. 1 + 2 + 3 + 4 = 10).
The Galton board and the binomial distribution
A Galton board is the triangle made of pegs. A ball lands on the top peg and, at each of 8 rows of pegs, bounces left or right with probability 1/2. After 8 bounces it falls into bin k, where k is its number of R bounces. Every one of the 2⁸ = 256 paths is equally likely, and C(8,k) of them end in bin k, so
P(bin k) = C(8,k) / 2⁸ e.g. P(bin 4) = 70 / 256 ≈ 27%, P(bin 0) = 1 / 256 ≈ 0.4%.
This is the binomial distribution with n = 8 and p = 1/2: mean n·p = 4 and standard deviation √(n·p·(1−p)) ≈ 1.41. On the canvas the bars count the balls in each bin and the red ticks show the expected count for the balls dropped so far. The coin flips come from a fixed seed, so a demo always drops the same balls. (Demo 4: Galton board, 100 balls)
Each ball's bin is a sum of 8 independent ±1/2 coin steps. As the number of rows grows, the shape gets closer and closer to the normal bell curve: that is the central limit theorem in its oldest form (de Moivre–Laplace). With only 100 balls the bars still wobble around the red ticks; the relative wobble shrinks like 1/√(number of balls).
Computing C(n,k) in code
| Method | How | Cost |
|---|---|---|
| Pascal's rule table | fill rows with C[n][k] = C[n−1][k−1] + C[n−1][k] | O(n·k) additions, no division; good for many values or modulo a prime |
| Multiplicative formula | c = 1; for i = 1..k: c = c · (n−k+i) / i | O(k); every partial result is an integer, so the division is exact |
| Factorials | n! / (k!(n−k)!) | simple, but n! overflows 64-bit integers already at n = 21 |
Use the smaller of k and n−k. C(n,k) itself grows fast: C(60,30) ≈ 1.2·10¹⁷ still fits in a 64-bit integer, C(68,34) does not. For counting arrangements and choices see also permutations and combinations, which lists the actual subsets with backtracking.
See also Permutations vs Combinations, which shows C(5,3) = 10 as 60 ordered picks ÷ 3! and splits the sets by E to show Pascal's rule.
The binomial coefficients C(n,k) give the binomial distribution; Binomial vs Poisson shows it turning into a Poisson distribution when n grows with np fixed.
See also hypothesis testing with a coin, which uses Binomial(100, 0.5) to decide whether 62 heads means the coin is biased.
Colour the odd numbers of Pascal's triangle and they form the Sierpinski triangle; the same picture comes out of random halfway jumps in The Chaos Game.
What the page leaves out
The triangle stops at row 8 and the path listing at row 5 so everything fits on the canvas. The Galton board is an ideal one: every bounce is exactly 50/50 and independent, with no ball-to-ball collisions. Biased boards (p ≠ 1/2), the multinomial theorem, Lucas' theorem for C(n,k) modulo a prime, Catalan numbers and the Sierpinski pattern of the odd entries are only mentioned here, not animated.