Appendix A: Pascal's Triangle

Most students of mathematics are familiar with a triangular array of numbers called Pascal's triangle. The form us usually found in textbooks is shown in Figure 1.

Figure 1: Pascal's Triangle

Pascal wrote a paper dealing with this triangle and its properties entitled Traité Du Triangle Arithmétique. In this paper I will use a different arrangement of this triangle as shown in Figure 2.

Figure 2: Pascal's Triangle (alternate form)

This form lends itself better to row and column notation. We will number the rows and columns starting with 0. Let $(n,r)$ denote the element in the $n$-the row and the $r$-the column. The numbers interior to the triangle satisfy the relation

\begin{equation} (n,r)=(n-1,r)+(n-1,r-1), \end{equation}

i.e, each interior element is obtained by adding the element one row above it in the same column to the element that is one row above and one column to the left. In addition, $(n,0)=(n,n)=1$ for all $n$ and $(n,r)=0$ for $r>n$.

We will show that the elements of this triangle are equal to the binomial coefficients. The binomial coefficients are the coefficients $\binom{n}{r}$ in the expansion

\begin{equation} (1+x)^n=\sum_{r=0}^n \binom{n}{r}x^r. \end{equation}

Clearly

\begin{equation*} (1+x)^n=\overbrace{(1+x)(1+x)\cdots(1+x)}^{n\text{ factors}} \end{equation*}

The term $x^r$ is obtained by taking $x$ from $r$ of the factors and $1$ from the remaining $n-r$ factors. Therefore, the coefficient $\binom{n}{r}$ must be the number of different ways of choosing $r$ $x$'s from the $n$ factors. Since there is nothing special about the $x$'s, $\binom{n}{r}$ must be equal to the number of combinations of $n$ objects taken $r$ at a time.

In order to show that $(n,r)=\binom{n}{r}$ we must show that the binomial coefficients satisfy

\begin{equation} \binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1} \end{equation}

with $\binom{n}{0}=\binom{n}{n}=1$ for all $n$ and $\binom{n}{r}=0$ for $r>n$. This is the same relation that the elements $(n,r)$ satisfy [see Equation (1)].

To derive this recursion relation recall that $\binom{n}{r}$ was the number of combinations of $n$ objects taken $r$ at a time. If we want to find the number of groups of $r$ objects taken from a group of $n$ objects, we can break the process into two parts. We divide the $n$ objects into a group A of $n-1$ objects and a group B with one object. If we find all the groups of $r$ objects taken from group A, these groups of $r$ objects are part of the ones considered in $\binom{n}{r}$. There are $\binom{n-1}{r}$ of these groups. What we are missing are those containing the object in group B. Each of those involves $r-1$ objects from group A. Clearly there are $\binom{n-1}{r-1}$ of these. This argument establishes the above recursion relation. In addition, it can be seen from the binomial expansion that $\binom{n}{0}=\binom{n}{n}=1$ for all $n$. Moreover, $\binom{n}{r}=0$ for $r>n$ since there are no powers of $x$ larger than $n$.

Since $(n,r)$ and $\binom{n}{r}$ satisfy the same generating equations, we must have $(n,r)=\binom{n}{r}$. Pascal used the binomial coefficients and the associated Pascal triangle to solve many of the combinatorial problems involved in probability calculations.

The binomial coefficients have a number of other properties. For example, if we let $x=1$ in Equation (2), then we get

\begin{equation} \sum_{r=0}^n\binom{n}{r}=2^n, \end{equation}

i.e, the sum of the elements in the $n$-the row of Pascal's triangle is $2^n$. There is also the following direct expression for calculating the binomial coefficients

\begin{equation} \binom{n}{r}=\frac{n(n-1)\cdots(n-r+1)}{r!}. \end{equation}

To see this we will start with ordered arrangements (permutations) and then proceed to unordered combinations. To find all the ordered arrangements of $n$ elements, we have $n$ choices for the first entry, $n-1$ choices for the second , down to 1 choice for the $n$-the entry. Thus, there are $n(n-1)\cdots 1=n!$ ordered arrangements of $n$ elements. Similarly, there are $n(n-1)\cdots(n-r+1)$ ordered arrangements of length $r$ taken from $n$ elements. However, in the binomial coefficients we don't want ordered arrangements, but unordered sets. For each unordered collection of $r$ elements taken from $n$ elements there are $r!$ arrangements of these $r$ elements. Thus, the number of unordered sets of $r$ elements taken from $n$ elements can be obtained by dividing the number of ordered arrangements of $r$ elements taken from $n$ elements by $r!$. This completes the proof of Equation (5).

From Equation (5) we can easily derive several other recursion relations, e.g.,

\begin{equation} (r+1)\binom{n}{r+1}=(n-r)\binom{n}{r} \end{equation}

and

\begin{equation} r\binom{n}{r}=n\binom{n-1}{r-1}. \end{equation}

Pascal derived these relations along with a number of others in his paper.

+++++