Pascal's Triangle

Construction

Start with a single 1 at the top. Each subsequent row begins and ends with 1, with each interior entry equal to the sum of the two directly above:

Row 0:                  1
Row 1:                1   1
Row 2:              1   2   1
Row 3:            1   3   3   1
Row 4:          1   4   6   4   1
Row 5:        1   5  10  10   5   1
Row 6:      1   6  15  20  15   6   1
Row 7:    1   7  21  35  35  21   7   1
Row 8:  1   8  28  56  70  56  28   8   1

The (n, k)-th entry (zero-indexed, with row 0 at top) is the binomial coefficient C(n, k) = n! / (k!(n−k)!).

Combinatorial properties

Property	Statement	Why
Symmetry	C(n, k) = C(n, n−k)	Choosing k items "to include" = choosing n−k "to exclude"
Pascal's rule	C(n, k) = C(n−1, k−1) + C(n−1, k)	Either include item n (C(n−1, k−1)) or don't (C(n−1, k))
Row sum	Σₖ C(n, k) = 2ⁿ	Total subsets of n-element set
Alternating row sum	Σₖ (−1)ᵏ C(n, k) = 0 (for n ≥ 1)	Inclusion-exclusion identity
Hockey stick	Σᵢ C(i, k) = C(n+1, k+1)	Sum a column down to row n
Binomial theorem	(a+b)ⁿ = Σₖ C(n, k) aⁿ⁻ᵏ bᵏ	n-th row is the expansion coefficients

Fibonacci hidden in shallow diagonals

Sum the entries along "shallow diagonals" (going right and up):

1                          → 1
1                          → 1
1, 1                       → 2
1, 2                       → 3
1, 3, 1                    → 5
1, 4, 3                    → 8
1, 5, 6, 1                 → 13
1, 6, 10, 4                → 21
1, 7, 15, 10, 1            → 34
...

Result — Fibonacci numbers. This works because C(n, k) + C(n+1, k+1) accounts for both Fibonacci's recursive paths. Combinatorial proof — count paths from one corner to another in two different ways.

The binomial theorem

The expansion of (a + b)ⁿ has coefficients given by row n of Pascal's triangle:

(a + b)⁰ = 1
(a + b)¹ = a + b                                      coefficients 1, 1
(a + b)² = a² + 2ab + b²                              coefficients 1, 2, 1
(a + b)³ = a³ + 3a²b + 3ab² + b³                      coefficients 1, 3, 3, 1
(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴              coefficients 1, 4, 6, 4, 1
...

General form:

(a + b)ⁿ = ∑ₖ₌₀ⁿ C(n, k) · a^(n-k) · b^k

Used to expand binomial expressions algebraically. Each term has total degree n in a and b combined; the coefficient is C(n, k).

Probability — binomial distributions

For n independent Bernoulli trials with success probability p, the probability of exactly k successes is:

P(k successes) = C(n, k) · p^k · (1−p)^(n−k)

The C(n, k) factor is the n-th row, k-th column of Pascal's triangle. So the triangle encodes the combinatorial structure of the binomial distribution.

For p = 0.5 and n = 4 — probabilities are (1, 4, 6, 4, 1)/16 = (0.0625, 0.25, 0.375, 0.25, 0.0625). Bell-shaped — for large n, by the Central Limit Theorem, this approaches the normal distribution.

JavaScript — Pascal's triangle

// Generate first n rows
function pascalTriangle(n) {
  const rows = [[1]];
  for (let i = 1; i < n; i++) {
    const prev = rows[i-1];
    const row = [1];
    for (let j = 1; j < i; j++) row.push(prev[j-1] + prev[j]);
    row.push(1);
    rows.push(row);
  }
  return rows;
}

// Compute C(n, k) using Pascal recurrence (avoids large factorials)
function binomial(n, k) {
  if (k > n - k) k = n - k;
  let result = 1;
  for (let i = 0; i < k; i++) {
    result = result * (n - i) / (i + 1);
  }
  return Math.round(result);  // round to handle float precision
}

console.log(pascalTriangle(8));
// [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], ...]

console.log(binomial(10, 5));  // 252
console.log(binomial(20, 10)); // 184756

// Binomial expansion
function expandBinomial(a, b, n) {
  const coeffs = pascalTriangle(n + 1)[n];
  return coeffs.map((c, k) => ({
    coeff: c,
    aPower: n - k,
    bPower: k,
    term: `${c}${n-k > 0 ? `·${a}^${n-k}` : ''}${k > 0 ? `·${b}^${k}` : ''}`
  }));
}

console.log(expandBinomial('a', 'b', 3));
// 1·a^3, 3·a^2·b, 3·a·b^2, 1·b^3

Where Pascal's triangle shows up

• Combinatorics. Counting subsets, paths in lattices, partitions. C(n, k) is everywhere combinatorial.
• Algebra. Binomial expansion, multinomial generalizations, polynomial arithmetic.
• Probability. Binomial distribution, normal approximation, gambling probabilities.
• Number theory. Lucas's theorem on C(n, k) mod p; Kummer's theorem on prime divisibility of binomials.
• Numerical analysis. Finite differences, Bernstein polynomials, numerical integration weights.
• Computer graphics. Bézier curves use Bernstein polynomials, which are related to binomial coefficients.
• Cryptography. Some algorithms use binomial-coefficient-related identities.

Common mistakes

• Computing factorials directly for large n. 100! is enormous. Use the iterative formula C(n, k) = ∏ (n−i)/(i+1) for i = 0..k−1. Avoids overflow and stays integer-valued.
• Forgetting symmetry. C(n, k) = C(n, n−k). For C(100, 99), don't compute 100·99·98·...; just compute C(100, 1) = 100. Symmetry saves work.
• Off-by-one indexing. Some conventions start row 0 at top; some at row 1. Check before applying formulas.
• Generating all rows when only one entry is needed. If you need C(50, 17), don't generate the whole triangle — use the closed-form recurrence.
• Floating-point errors in binomial computation. The iterative product can drift; use BigInt for large values or round at the end.
• Mixing C(n, k) with permutations P(n, k). P(n, k) = n! / (n−k)! (ordered selections). C(n, k) = P(n, k) / k! (unordered). Different counts; check whether order matters.