Pascal's Triangle

# Pascal's Triangle

One way to relate $k$-combinations of a finite $n$-element set is with a special graph known as Pascal's Triangle. A portion of Pascal's triangle is shown below: The top of Pascal's Triangle is a $1$, and entries for Pascal's triangle are generated to be the sum of the two numbers directly above that entry (or just the number directly above the entry if there's only one).

If we label the rows of Pascal's triangle starting at row $0$, row $1$, etc…, then you should notice that the finite sequence of numbers in row $n$ for each $n = 0, 1, 2, ...$ and for $k = 0, 1, 2, ..., n$ is the same sequence of numbers as:

(1)
\begin{align} \quad \left \{ \binom{n}{0}, \binom{n}{1}, \binom{n}{2}, ..., \binom{n}{k-1}, \binom{n}{k}, \binom{n}{k+1}, ..., \binom{n}{k} \right \} \end{align}

For example, row $5$ in Pascal's triangle forms the finite sequence $\{ 1, 5, 10, 10, 5, 1 \}$, and using the formula $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for counting the number of $k$-combinations for a $5$-element set for $k = 0, 1, 2, ..., 5$, we have that:

(2)
\begin{align} \quad \quad \left \{ \binom{5}{0}, \binom{5}{1}, \binom{5}{2}, \binom{5}{3}, \binom{5}{4}, \binom{5}{5} \right \} = \left \{ \frac{5!}{0! \cdot 5!} , \frac{5!}{1! \cdot 4!}, \frac{5!}{2! \cdot 3!}, \frac{5!}{3! \cdot 2!}, \frac{5!}{4! \cdot 1!}, \frac{5!}{5! \cdot 0!} \right \}= \{ 1, 5, 10, 10, 5, 1 \} \end{align}

As we will shortly see - Pascal's triangle gives us a nice geometric interpretation of a very nice formula known as Pascal's Formula.