Search This Blog

06 February 2007

Binary Representation of Pascal's Triangle



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
210
n101
r010
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. :)

No comments: