Mathematical Digressions: Pascals Triangle

Pascals Triangle was originally discovered by the Chinese in the $11^{th}$ century, but was later studied in depth by the French mathematician Blaise Pascal in the 17th century. Pascals triangle has many interesting properties.

The $k^{th}$ number in the $n^{th}$ row is the binomial coefficient ${n \choose k} = \frac{n!}{k!(n-k)!}$

The number of ways to choose $k$ socks out of a drawer filled with $n$ different socks
The coefficient in front of $a^kb^{n-k}$ when $(a+b)^n$ is expanded

Each number is the sum of the two above it. ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$
The triangle is symmetric. ${n \choose k} = {n\choose n-k}$
The sum of the $n^{th}$ row is $2^n$. $\sum_{k}{n \choose k} = 2^n$
The sum of the squares of the values in the $n^{th}$ row is the middle of the $2n^{th}$ row. $\sum_{k}{n \choose k}^2 = {2n \choose n}$
The semi-diagonals sum to the Fibonacci Numbers
The third diagonal from the left gives the Triangular Numbers
On the third diagonal from the left, each subsequent pair of numbers sums to the next perfect square
If you squeeze together the $n^{th}$ row into one number you get $11^n$
The Hockey Stick identity

${n+1 \choose k+1} = {k \choose k} + {k+1 \choose k} + ... + {n \choose k}$
${n+k+1 \choose k} = {n \choose 0} + {n+1 \choose 1} + ... + {n+k \choose k}$

Modular Pascals Triangle

One of the cooler properties of Pascals triangle is how when you display the remainder of each value when divided by $n$ (mod $n$), it forms a Sierpinski Triangle in the limit. The following are for $n = 2,3,5,7$.

When $n$ is a prime number it is easy to see the recurrence for $R_p(n)$, the number of elements in the $n^{th}$ row not equivalent to 0 (mod p) and the recurrence for $T_p(n)$, the number of elements in the triangle up thru the $n^{th}$ row not equivalent to 0 (mod p). If $n$ written out in base $p$ is $\eta_k\eta_{k-1}...\eta_0$, then

$$R_p(\eta_k...\eta_0) = \prod_{k}(\eta_k + 1)$$
$$T_p(\eta_k...\eta_0) = \frac{\eta_k(\eta_k+1)}{2} T_p(1_k00...0) + (\eta_k+1)\,T_p(\eta_{k-1}...\eta_0)$$

$T_p(p^k) = T_p(1_k00...0) = \left(\frac{p(p+1)}{2}\right)^{k}$

Can we generalize this result to powers of primes, or numbers that are the product of two primes? You can play around with modular pascals triangle with this java applet, though you might need to use a browser other than Chrome. Here are some revealing pictures.