Extension: \(C(n,r)\) and Pascal's Triangle

In this lesson, the idea of combinations were very briefly introduced.

We also noted two related facts:

1. The entry in row \(n\) and column \(r\) of Pascal's triangle is equal to the number of unique paths that start at the top of the triangle and reach the entry in the \(n\)^th row and \(r\)^th column. Paths only include downward moves through the triangle.
2. The entry in row \(n\) and column \(r\) of Pascal's triangle is \(C(n,r)\).

The latter of these two facts was stated without any justification. Let's see now why it is true.

The Number of Paths in Pascal's Triangle

During the lesson, an explanation was given about why each entry in Pascal's triangle is equal to the number of unique paths that start at the top of the triangle and reach that entry, where paths only include downward moves through the triangle.

For example, we saw that there are \(6\) unique paths from the top of the triangle through the entry in row \(n=4\) and column \(r=2\).

Let's devise a way to list the paths. Starting at the top of the triangle, the first move in the path is either "down and to the left" or "down and to the right." In fact, at each position these are the only two options for the next move in the path. Thus, we can describe any path as a sequence of \(L\)s (for "down and to the left") and \(R\)s (for "down and to the right"). We will call such a listing a "path sequence." For example, one path sequence that arrives at the entry with \(n=4\) and \(r=2\) is \(LRRL\).

Each path in the triangle has a unique path sequence. Here are the \(6\) paths that arrive at the \(n=4\) and \(r=2\) entry:

1. \(LLRR\)
2. \(LRLR\)
3. \(LRRL\)
4. \(RLLR\)
5. \(RLRL\)
6. \(RRLL\)

For any position in the triangle, we can predict how many \(L\)s and \(R\)s are needed for a path sequence that describes a path that arrives at that position in the triangle:

• Since each incidence of either an \(L\) or \(R\) represents moving down one position, a path sequence of a path that ends in row \(n\) must have length \(n\).
• Since each incidence of an \(L\) keeps the path in the same column and each incidence of an \(R\) changes the path to the subsequent column, a path sequence of a path that ends in column \(r\) must contain \(r\) \(R\)s.

Thus, the number of paths to row \(n\) and column \(r\) is equal to the number of arrangements of a total of \(n\) \(L\)s and \(R\)s, where there are \(r\) \(R\)s. This is equivalent to \(C(n,r)\) for the following reason:

• Suppose you have \(n\) boxes.

• You pick \(r\) of these boxes in which you will write an \(R\). Write an \(L\) in the remainder of the boxes.
• This can be done in \(C(n,r)\) ways since \(C(n,r)\) is the number of ways to choose \(r\) objects from a total of \(n\) objects.

Therefore, the number of paths to row \(n\) and column \(r\) in Pascal's triangle is \(C(n,r)\).

Final Comment

We still have only begun to scratch the surface of the mathematics of \(C(n,r)\) and combinations. An entire branch of mathematics, known as Combinatorics, is devoted to the study of combinations and related topics.