Pascal's triangle

Pascal's triangle (known in Italy as Tartaglia's triangle) is one of the most beautiful structures of combinatorial mathematics. A triangular array where each entry is the sum of the two entries above it:

             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

Rows are indexed from n = 0 and each entry is a binomial coefficient:

C(n, k) = n! / (k! · (n−k)!)

Counting the ways to choose k objects from n. Known in India (Pingala, 200 BCE), Persia (al-Karaji, 10th c.), and China (Yang Hui, 1261), it bears Pascal's name after his systematic treatment in Traité du triangle arithmétique (1654).

The four modes

1. First N rows: up to row N−1 (max 25), centered.
2. C(n, k): single binomial coefficient with Pascal's identity check and triangle highlight.
3. Row sum: verifies ∑ C(n, k) = 2^n and shows Fibonacci numbers along shallow diagonals.
4. Modular triangle: C(n, k) mod p for prime p, revealing the Sierpinski triangle for p = 2.

Pascal's identity

C(n, k) = C(n−1, k−1) + C(n−1, k)

Proof: choosing k from n+1 items, either include the first (then k−1 from remaining n) or not (k from n). Sum gives the recurrence. Yields O(n²) algorithm for all coefficients up to row n.

Newton's binomial theorem

(x + y)ⁿ = ∑_k=0ⁿ C(n, k) · x^n−k · y^k

Example n = 4: (x+y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴. Newton generalised it to non-integer exponents (binomial series) in 1665.

Notable properties

• Symmetry: C(n, k) = C(n, n−k).
• Row sum: ∑ C(n, k) = 2^n (subsets of an n-set).
• Alternating sum: ∑ (−1)^k C(n, k) = 0 for n ≥ 1 (inclusion-exclusion).
• First diagonal: all 1s.
• Second diagonal: natural numbers (C(n, 1) = n).
• Third diagonal: triangular numbers (C(n, 2)).
• Fourth diagonal: tetrahedral numbers (C(n, 3)).
• Shallow diagonals: Fibonacci numbers.
• Hockey stick: ∑_{i=r}^{n} C(i, r) = C(n+1, r+1).

The Sierpinski triangle

Colouring odd entries black and even white in C(n, k) mod 2 reveals the famous Sierpinski triangle (Wacław Sierpiński 1915). Its Hausdorff dimension is log₂ 3 ≈ 1.585 — fractal, non-integer. The fractal structure emerges because «odd + odd = even, even + even = even, odd + even = odd» matches the Sierpinski construction rules. A beautiful link between elementary combinatorics and fractal geometry.

Lucas's theorem

C(n, k) mod p = ∏ C(n_i, k_i) mod p

where n_i, k_i are the digits of n, k in base p. Reduces computation to O(log_p n) — essential in competitive algorithms and number theory.

Applications

• Probability: binomial distribution P(k successes in n trials) = C(n,k)·p^k·(1−p)^(n−k).
• Polynomial expansion: (x+y)^n in algebra and calculus.
• Combinatorics: lattice-path counts, e.g. C(m+n, m) paths from (0,0) to (m,n).
• Statistics: combinations in draws, lotteries, surveys.
• Cryptography: Lucas for fast C(n,k) mod p in RSA-like schemes.
• Graphics & games: Sierpinski patterns as procedural textures.
• Optimisation: DP for knapsack and scheduling.

Pascal, Fermat and the birth of probability

The triangle owes its Western name to the treatise Blaise Pascal devoted to it in 1654, but its historical importance goes beyond combinatorics: it was a key tool in the birth of probability theory. In that same year Pascal and Pierre de Fermat exchanged a famous correspondence on the "problem of points", namely how to fairly divide the stakes of a gambling game interrupted before the end.

The solution required counting in how many ways the game could have ended, and this is where the triangle's binomial coefficients come into play: each row gives the probabilities of the different outcomes of a sequence of repeated trials. From that exchange of letters was born the mathematical theory of chance, which today governs statistics, finance and science. Pascal's triangle is thus far more than a curiosity: it is one of the bridges between elementary arithmetic and modern probability theory.

A triangle of many names: Yang Hui, al-Karaji, Tartaglia

Although in the West it bears Pascal's name, the triangle was known to many cultures centuries earlier. In India the mathematician Pingala described its structure as early as around the 2nd century BC while studying metrical combinations, and Halayudha gave an explicit commentary in the 10th century. In the Islamic world al-Karaji and later al-Tusi knew the rule forming the rows around the year 1000.

In China the mathematician Jia Xian used it in the 11th century to extract roots, and Yang Hui presented it in 1261, so much so that in Chinese it is still called "Yang Hui's triangle". In Italy Niccolo Tartaglia studied it in the 16th century, which is why in the Italian world one often speaks of "Tartaglia's triangle". That so many civilizations discovered it independently testifies to its naturalness: it is a structure that inevitably emerges whenever one counts combinations, a shared heritage of human mathematics.

Updated July 2026