5 Pascal's triangle

Pascal's triangle is an interesting method to compute the number of combinations. Let $p[r][c]$ represents column $c$ or row $r$ . For the sake of mathematicians, let us count from 1 (instead of 0, which makes more sense, of course).

For row $p[r]$ , there are exactly $r$ columns. The first and last columns of each row, $p[r][1]$ and $p[r][r]$ , must be 1. All other columns are defined as follows $\forall r > 2: \forall i \in [2\ldots r-1]: p[r][i] = p[r-1][i-1] + p[r-1][i]$ .

This yields a ``triangle'' as represented in table 1.

Table 1: The tip of Pascal's triangle.

				1
			1		1
		1		2		1
	1		3		3		1
1		4		6		4		1

Because of the symmetry of the triangle, you only need to figure out one half (left or right), and the other half is the same.

Here is the interesting part. $p[r][c] = {{r-1} \choose {c-1}}$ . For example, $p[4][2] = 3$ , this means that ${3 \choose 2} = 3$ . Of course, we can easily verify that $\frac{3!}{2!1!} = 3$ .

How does this work, in general? At the core, we need to prove that ${r \choose i} = p[r+1][i+1] = p[r][i] + p[r][i-1] = {{r-1}\choose{i}} + {{r-1}\choose{i-1}}$ .

The proof is as follows:

$${{r-1}\choose{i}} + {{r-1}\choose{i-1}}$$ (9)

$$= \frac{(r-1)!}{(r-1-i)!i!} + \frac{(r-1)!}{(r-i-2)!(i-1)!}$$ (10)

$$= \frac{\prod_{j=r-i}^{r-1} j}{i!} + \frac{\prod_{j=r-i+1}^{r-1} j}{(i-1)!}$$ (11)

$$= \frac{\prod_{j=r-i}^{r-1} j}{i!} + \frac{i\prod_{j=r-i+1}^{r-1} j}{i!}$$ (12)

$$= \frac{{\prod_{j=r-i}^{r-1} j}+i{\prod_{j=r-i+1}^{r-1} j}}{i!}$$ (13)

$$= \frac{(r-i){\prod_{j=r-i+1}^{r-1} j}+i{\prod_{j=r-i+1}^{r-1} j}}{i!}$$ (14)

$$= \frac{((r-i+i)){\prod_{j=r-i+1}^{r-1} j}}{i!}$$ (15)

$$= \frac{r{\prod_{j=r-i+1}^{r-1} j}}{i!}$$ (16)

$$= \frac{\prod_{j=r-i+1}^{r} j}{i!}$$ (17)

$$= \frac{\frac{r!}{(r-i)!}}{i!}$$ (18)

$$= \frac{r!}{(r-i)!i!}$$ (19)

$$= {r \choose i}$$ (20)