Pascal's Triangle

Pascal's Triangle is a triangular array of numbers where each entry is the sum of the two entries directly above it. Named after French mathematician Blaise Pascal, who published a comprehensive treatise on it in 1653, the triangle was in fact known centuries earlier across multiple civilizations. Chinese mathematician Jia Xian described it around 1050 AD, Persian mathematician Omar Khayyam studied it in the 11th century, and it appears in the works of Indian mathematicians as early as the 10th century. In China it is still called "Yang Hui's Triangle" after the 13th-century mathematician who popularized it. Despite its simple construction rule, this structure encodes a remarkable wealth of mathematical relationships that continue to find applications across nearly every branch of mathematics and computer science.

How It Works

1. Row 0: Start with a single 1 at the top.
2. Build each row: Each row starts and ends with 1. Every interior entry is the sum of the two entries directly above it from the previous row. For example, in row 4 the entry 6 comes from adding 3 and 3 from row 3.
3. Grow: Each new row has one more element than the previous row. Row n contains exactly n + 1 entries.

Row n contains the binomial coefficients C(n, 0), C(n, 1), ..., C(n, n). The entry at row n, position k equals n! / (k! * (n-k)!), which counts the number of ways to choose k items from a set of n items.

Properties

Beyond these patterns, the triangle reveals even deeper structure when viewed through different lenses. Coloring entries by divisibility by a prime p produces a fractal pattern resembling Sierpinski's Triangle -- a striking connection between number theory and fractal geometry. The hockey stick identity states that the sum of consecutive entries along a diagonal equals the entry just below the last one, offset by one position. Each row is also palindromic -- it reads the same forwards and backwards -- because C(n, k) = C(n, n-k).

Mathematical Significance

The binomial theorem states that (a + b)^n equals the sum of C(n, k) * a^(n-k) * b^k for k from 0 to n. Pascal's Triangle provides these coefficients directly. Setting a = b = 1 gives 2^n, which is why each row sums to a power of 2. Setting a = 1 and b = -1 gives 0 for n greater than 0, proving that the alternating sum of each row is zero.

The triangle also connects to the Catalan numbers, Stirling numbers, and the coefficients of Chebyshev polynomials through various combinatorial identities. Pascal himself used the triangle to solve problems in probability theory during his famous correspondence with Pierre de Fermat, laying groundwork for the entire field of probability.

When It's Used

Pascal's Triangle appears throughout mathematics and computer science. The binomial coefficients are essential in combinatorics for counting combinations, in probability for computing binomial distribution probabilities, in algebra for expanding polynomial expressions, and in calculus for polynomial interpolation via Newton's forward difference formula. In programming, building the triangle row by row provides an efficient way to compute C(n, k) using only addition, avoiding the factorial computations that cause integer overflow for large values. Dynamic programming solutions to many problems -- such as counting lattice paths or computing probability distributions -- are essentially computing portions of Pascal's Triangle. The triangle also appears in numerical methods, signal processing (binomial filters for image smoothing), and in the analysis of error-correcting codes.