^{2}

sum of all integers = n(n+1)/2

I realized that I never really showed how Pascal's Triangle is related to the Binomial Coefficients... So here we go:

(x+1)^{0} =

*1*

(x+1)^{1} =

1x + 1 =

*1 1*

(x+1)^{2} =

(x+1)(x+1) =

x*x + x*1 + 1*x + 1*1 =

1x^{2} + 2x + 1 =

*1 2 1*

(x+1)^{3} =

(x+1)(x+1)(x+1) =

((x+1)(x+1))(x+1) =

(1x^{2} + 2x + 1)(x+1) =

(1x^{2}*x + 1x^{2})+(2x*x + 2x*1)+(1*x + 1*1)=

1x^{3} + 1x^{2} + 2x^{2} + 2x + x + 1 =

1x^{3} + 3x^{2} + 3x + 1 =

*1 3 3 1*

(x+1)^{4} =

(x+1)(x+1)(x+1)(x+1) =

((x+1)(x+1)(x+1))(x+1) =

(1x^{3} + 3x^{2} + 3x + 1)(x+1) =

(1x^{3}*x + 1x^{3}*1)+(3x^{2}*x + 3x^{2}*1)+(3x*x + 3x*1)+(1*x + 1*1) =

1x^{4} + 1x^{3} + 3x^{3} + 3x^{2} + 3x^{2} + 3x + 1x + 1 =

1x^{4} + 4x^{3} + 6x^{2} + 4x + 1 =

*1 4 6 4 1*

As you generate very large Pascal Triangles, the numbers quickly get out of control. If you are planning on modding the values after obtaining them, why not mod them first?

Here you see an example of doing a mod5 before writing the number down... So, for example, the middle element on Row#4 is 1 because (3+3)%5 = 6%5 = 1... Now, you can use the number 1 for further rows instead of the original number 6.

To look like this, one thing you might do is work out all the values of the previous lines and then mod them to determine whether they should be highlighted or not.

Yet another way might be to just keep track of whether the values above are 1 or 0, and realize that the next one down is only 0 if both the parent hexes are 1.

But, how about a way to do it without any regard to previous rows? This method is quite simple...

Let's say you want to examine nCr (n=row, r=col)... say, 5C2 (10 if you look at the image)...

How do we do it? First, write down the binary value of n and r.

n (5) = 101

r (2) = 010

Now, if ANY digit in r is larger than the corresponding digit in n, it is even. Otherwise, it is odd.

Looking at our example, we compare:

bits | |||
---|---|---|---|

2 | 1 | 0 | |

n | 1 | 0 | 1 |

r | 0 | 1 | 0 |

r[1] is higher than n[1] so it is even |

So, to determine if any point in Pascals' Triangle is odd/even, you just have to compare the binary representation of the row and column. :)

Subscribe to:
Posts (Atom)