Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search