Pascal's Triangle

Level:

n=0                                 1

n=1                              1     1 

n=2                           1     2     1

n=3                        1     3     3     1

n=4                     1     4     6     4     1

n=5                   1    5    10     10    5     1
 
n=6                1    6    15     20    15    6     1

etc.

To get the next row, add the numbers in pairs, but start and end with 1's.

Pascal's triangle can also be generated by a formula. To use the formula you 
need to know what a _factorial_ is. Here are some examples:

3! = 3 x 2 x 1 = 6

5! = 5 x 4 x 3 x 2 x 1 = 120

Given a positive integer N, "N factorial", denoted "N!", is the product of 
the positive integers less than or equal to N.

N! = N x (N-1) x (N-2) x ... x 2 x 1.

We also define 0! to be 1. (I know that looks weird, but it works well in many
applications.)

Let C(n,r) be the rth entry in the nth row of Pascal's Triangle, where the
top row is the 0th row, and the first entry in a row is called the 0th entry.
Then you can check that 

C(0,0) = 1 ,  C(3,2) = 1, C(5,2) = 10.

The formula is 

              n! 
C(n,r) =   --------
           r!(n-r)!   

We check this: C(5,2) = (5!)/(2!*3!) = 120/12 = 10.

C(n,r) is the number of ways you can choose r things from among n things.
For example the the number of ways you can choose 2 numbers form a list
of 5 numbers is:

List = {1,2,3,4,5}. Choices are: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45.
There are 10 of them.  

Now consider (a+b)^5 = (a+b)(a+b)(a+b)(a+b)(a+b)
There will be a term for a^2b^3 in the expansion. 
How many ways can we choose two a's from the five (a+b)'s?

aabbb
ababb
abbab
abbba
baabb
babab
babba
bbaab
bbaba
bbbaa

There are 10. (I know I have not missed any because my list is in 
alphabetical order.) But this is C(5,2). Thus, 

(a+b)^5 = a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5

(I guess I went backwards there, but it does not really matter:
Pascal's triangle is clearly symmetric.)

Note: The proof that C(n,r) generates Pascal's triangle is nontrivial,
but can be found in the appendices of many college algebra, finite math,
and discrete math textbooks.