Pascal's Triangle

The first few rows of Pascal's Triangle are as follows:

                            1                           Row 0
                         1     1                        Row 1
                      1     2     1                     Row 2
                   1     3     3     1                  Row 3
                1     4     6     4     1               Row 4
             1     5     10    10    5     1            Row 5
          1     6     15    20    15    6     1         Row 6
       1     7     21    35    35    21    7     1      Row 7
    1     8     28    56    70    56    28    8     1   Row 8
                          . . .

This triangle is named after Blaise Pascal, who wrote Treatise on the Arithmetical Triangle in 1665. While Pascal was not the first person to discover this binomial triangle (the Persians and Chinese had used it centuries ago, and even in Europe Tartaglia had mentioned this triangle in his General Trattato), Pascal was the first to discover many of the triangle's interesting properties. Each number in Pascal's triangle is the sum of the (usually two) numbers directly above it. Some of the interesting properties of Pascal's triangle are as follows:

• The sum of the numbers in row n is 2 ⁿ.
• The first diagonal is occupied by 1's.
• The second diagonal is occupied by the natural numbers (1, 2, 3, 4, etc.).
• The third diagonal is occupied by triangular numbers (1, 3, 6, etc.).
• The fourth diagonal contains tetrahedral numbers.
• The r^th number in the n^th row is equal to nCr (where C is the combination operator).
• Interesting patterns can be formed by looking at the remainders after dividing each number by a given number. There are some shortcuts that can be employed here - one doesn't have to calculate all of the numbers in a certain section of the triangle. For example, Lucas' theorem states that, to determine whether the number in the k^th column of the n^th row of Pascal's triangle is even or odd, convert n and k to base 2. The number is even unless every binary digit of k is less than or equal to the corresponding binary digit of n.
• Fibonacci numbers can be extracted from the triangle (see the Fibonacci numbers page for more information).