Pascal's Triangle and CombinationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/