Pascal's Triangle, a Pattern Factory

Definition Pascal’s triangle is a triangular array of numbers arranged in rows. The top row is row 0 and holds a single 1. Row $n$ holds $n + 1$ entries in positions $k = 0, 1, \dots, n$, counted from the left starting at 0. Each row begins and ends with 1, and every other entry is the sum of the two entries diagonally above it. So for $1 \le k \le n - 1$ the entry in row $n$ at position $k$ is the sum of the entries in row $n - 1$ at positions $k - 1$ and $k$. The surprise is that this one rule produces, in row $n$ at position $k$, the number of ways to choose $k$ objects from $n$ different objects. That number is written $\binom{n}{k}$ and called a binomial coefficient. It also counts the paths from the top that end at that position, and it is the coefficient of $a^{n-k}b^k$ when $(a + b)^n$ is multiplied out. As a consequence, the entries of row $n$ add up to $2^n$. The triangle is named after Pascal, who wrote a treatise on it in the 1650s, although it was known centuries earlier in India, Persia and China.

Definition For whole numbers $n \ge 0$ and $0 \le k \le n$, a combination of $k$ objects from a set of $n$ different objects is a selection of $k$ of them in which order does not matter, in other words a subset of size $k$. Two selections are the same combination when they contain the same objects. The number of combinations of $k$ objects from $n$ is written $\binom{n}{k}$ and read as $n$ choose $k$. To count them, fix one object of the set. A combination of size $k$ either leaves that object out, and is then a choice of $k$ of the other $n - 1$ objects, or contains it, and is then a choice of $k - 1$ of the other $n - 1$ objects. No combination is of both kinds, so for $1 \le k \le n - 1$ this gives Pascal’s rule,

the addition rule of the triangle. Together with $\binom{n}{0} = \binom{n}{n} = 1$, for the single empty selection and the selection of everything, these counts fill the triangle row by row.

Definition For whole numbers $n \ge 0$ and $0 \le k \le n$, the binomial coefficient $\binom{n}{k}$ is the number of combinations of $k$ objects from $n$ different objects. It is given by

where $n! = n(n-1) \cdots 2 \cdot 1$ for $n \ge 1$ and $0! = 1$. The formula comes from counting ordered selections, of which there are $n(n-1)\cdots(n-k+1)$, and dividing by the $k!$ orders in which each combination can be listed. The binomial coefficient $\binom{n}{k}$ is the entry of Pascal’s triangle in row $n$ at position $k$, both counted from 0. Binomial coefficients are symmetric, $\binom{n}{k} = \binom{n}{n-k}$, because choosing the $k$ objects to take is the same as choosing the $n - k$ objects to leave. The entries of row $n$ add up to $2^n$, because each of the $n$ objects is either taken or left, which gives $2^n$ subsets of all sizes together.

Definition A lattice path is a route through a grid of points made of steps of a few allowed kinds. In Pascal’s triangle, start at the top entry and step down to the next row each time, either down to the left or down to the right. After $n$ steps the path is in row $n$, and its position there is the number of steps it took to the right. So the paths that end in row $n$ at position $k$ are exactly the sequences of $n$ steps with $k$ steps to the right. There is one path to the top, the path with no steps, and one path to each end of a row, straight down an edge. A path to any other position arrives through one of the two positions diagonally above it, so the number of paths to it is the sum of the numbers of paths to those two. The path counts start, end and grow by the same rule as the triangle, so the number of paths to row $n$, position $k$, is $\binom{n}{k}$. The same count on a square grid says that there are $\binom{r+s}{r}$ paths from the point $(0, 0)$ to the point $(r, s)$ made of steps one unit to the right or one unit up.

Definition The binomial theorem says that for every whole number $n \ge 0$ and all numbers $a$ and $b$,

where the symbol $\sum$ means adding the terms for $k = 0, 1, \dots, n$, and a power with exponent 0 counts as 1, even when its base is 0. The reason is that multiplying out the $n$ brackets of $(a + b)(a + b) \cdots (a + b)$ means choosing $a$ or $b$ from each bracket, multiplying the choices, and adding the products over all $2^n$ ways of choosing. A product equals $a^{n-k}b^k$ exactly when $b$ was chosen from $k$ of the $n$ brackets, and there are $\binom{n}{k}$ ways to pick those brackets.