Pascal's Triangle and Combinations

Date: 06/05/98 at 10:05:25
From: Jesse Walker
Subject: Pascal's Triangle and Combinations

In Pascal's Triangle, there is a pattern where any given number from 
the triangle is the sum of two numbers in the row before it that are 
closest to the number. So in the fourth row down from the top, in the 
third column, the number is 6. The two numbers closest to it 
in the previous row are 3 and 3. So 3 + 3 = 6. 

Each number from the triangle can represent a combinations problem. 
In this case, the 6 is equal to 4 C 2. The threes are equal to 3 C 1 
and 3 C 2. 

Why is 4 C 2 equal to the sum of 3 C 1 and 3 C 2?  I realize that 
3 plus 3 is 6, but I need a detailed explaination that shows how 
3 C 1 + 3 C 2 equals 4 C 2. I have come up with a formula: 
  
  x combinations taken y at a time = (x-1) C (y-1) + (x-1) C y

However, this hasn't helped much in my understanding of the relation. 
Please give me any information you have on this relation of a number 
in Pascal's Triangle and the two numbers closest to it in the previous 
row, in terms of how they are represented in combinations.

Date: 06/06/98 at 22:07:47
From: Doctor Pat
Subject: Re: Pascal's Triangle and Combinations

Jesse,

I'll try to do all this in a way that you can see it develop.  
Here goes:

I hope the value of n C r  = n! / ( r! (n-r)!) is already known to 
you. I will use it to show why the relation you observe is true. 
First, though, we'll do an example to make a believer of you.  

Let's look at 8 C 3, 8 C 4 and note that the number below and between 
them is 9 C 4. Can you see that it will always be true that if the 
first two numbers are n C r and n C r+1, the number between and below 
will be n+1 C r+1?   

Back to our example: 8!/(8-3)!*3! ends up looking like this:

    8*7*6
   -------
    3*2*1

Note that there will be the same number of values on the top and 
bottom, and with n C t, there are t numbers on top and bottom. 
So 8 C 3 + 8 C 4 looks like:

    8*7*6    8*7*6*5
   ------- + -------
    3*2*1    4*3*2*1

From here we have to do some simple fraction work. The two 
denominators are alike except for the first term of the second (4).  
If we multiply the left fraction top and bottom by four (multiply by 
4/4 = 1) we get:
 
   4*8*7*6   8*7*6*5    4*(8*7*6) + (8*7*6)*5
   ------- + ------- =  ---------------------
   4*3*2*1   4*3*2*1          4*3*2*1  

Notice that on the right side I used parentheses to make a grouping 
show up. 
 
If we factor the (8*7*6) we end up with 9 (8*7*6) which is the 
numerator of 9 C 4. Thus the whole thing is equal to 9 C 4.    

Now rewriting this with (n C r) + (n C r+1) to show it is equal to 
n+1 C r+1 looks full of variables, but remember the variables just 
stand for the numbers we used above:
  
   (n C r) + (n C r+1)

        n*(n-1)*...*(n-r+1)   n*(n-r)*....*(n-r+1)*(n-r)
      = ------------------- + -------------------------- 
           r*(r-1)*...*1        (r+1)*r*(r-1)*.....*1

Now we multiply the left term by (r+1) and use square brackets for 
the special grouping to factor:

        (r+1)*[n*(n-1)*...*(n-r+1)]   [n*(n-r)*....*(n-r+1)](n-r)
      = --------------------------- + ---------------------------  
           (r+1)*r*(r-1)*...*1           (r+1)*r*(r-1)*.....*1

With the square brackets, we see that the numerator is: 

   [(r+1)+(n-r)]*[n*(n-1)*....(n-r+1)] = [n+1]*[n*(n-1)*....(n-r+1)]

which is (n+1)! divided by (n-(r+1))!  
  
The denominator is (r+1)!, giving us:          

        (n+1)!
   ---------------- = n+1 C r+1  
   (r+1)!(n-(r+1))!  
  
I hope the method is clear even if my typing is not always correct.

I hope this helps. If not, please write again with specifics about 
the parts where you are stuck. Good luck. 
            
-Doctor Pat,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/