Difference between revisions of "Bill's Triangle"
m (→Why is this useful?) |
|||
| (27 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
==How to Make Bill's Triangle== | ==How to Make Bill's Triangle== | ||
| − | As with Pascal's Triangle, we start with a complete row of zeros. However, in Bill's Triangle, we need another row: | + | As with [[Pascal's Triangle]], we start with a complete row of zeros. However, in Bill's Triangle, we need another row: |
| − | <cmath> | + | <cmath>0, 0</cmath> |
| − | <cmath> | + | <cmath>0, 0, 0</cmath> |
Again, as with Pascal's Triangle, we change a zero to a one: | Again, as with Pascal's Triangle, we change a zero to a one: | ||
| − | <cmath> | + | <cmath>0, 0</cmath> |
| − | <cmath> | + | <cmath>0, 1, 0</cmath> |
Now, we can add the top three numbers to get the next number. The boxed numbers are the ones we add to get the next row. | Now, we can add the top three numbers to get the next number. The boxed numbers are the ones we add to get the next row. | ||
| − | <cmath>0, 0, \boxed{0}, \boxed{0}, 0, 0</cmath> | + | <cmath>\boxed{0}, 0</cmath> |
| − | <cmath>0, 0, 0, \ | + | <cmath>\boxed{0}, \boxed{1}, 0</cmath> |
| + | |||
| + | We add <math>0 + 0 + 1 = 1,</math> so that is the next number. We also add these numbers: | ||
| + | |||
| + | <cmath>0, \boxed{0}</cmath> | ||
| + | <cmath>0, \boxed{1}, \boxed{0}</cmath> | ||
| + | |||
| + | Therefore, the first few rows of Bill's Triangle are | ||
| + | |||
| + | <cmath>0, 0</cmath> | ||
| + | <cmath>0, 1, 0</cmath> | ||
| + | <cmath>0, 1, 1, 0</cmath> | ||
| + | |||
| + | We could keep adding zeroes, but as with Pascal's Triangle, we can get rid of them. Hopefully, by now you have gotten the "gist" of Bill's Triangle, and we can proceed to calculate the next few rows: | ||
| + | |||
| + | <cmath>1</cmath> | ||
| + | <cmath>1 , 1</cmath> | ||
| + | <cmath>1 , 3 , 1</cmath> | ||
| + | <cmath>1 , 5 , 5 , 1</cmath> | ||
| + | <cmath>1 , 7 , 13 , 7 , 1</cmath> | ||
| + | <cmath>1 , 9 , 25 , 25 , 9 , 1</cmath> | ||
| + | <cmath>1, 11, 41, 63, 41, 11, 1</cmath> | ||
| + | <cmath>\vdots</cmath> | ||
| + | |||
| + | ==Why is this useful?== | ||
| + | |||
| + | Bill's Triangle counts paths on a grid, just like Pascal's Triangle. While Pascal's Triangle counts the number of ways to get from point <math>A</math> to point <math>B</math> on a grid, if you are only allowed to go vertically and horizontally. Bill's Triangle allows you to go diagonally, like in this grid: | ||
| + | |||
| + | <center><asy> | ||
| + | for (int i = 0; i <= 8; i += 1) { | ||
| + | for (int j = 0; j <= 8; j += 1) { | ||
| + | draw((0,j)--(i,j)); | ||
| + | draw((i,0)--(i,j)); | ||
| + | } | ||
| + | } | ||
| + | for (int j = 0; j <= 8; j += 1) { | ||
| + | draw((0,8-j)--(j,8)); | ||
| + | draw((8-j,0)--(8,j)); | ||
| + | } | ||
| + | </asy></center> | ||
Latest revision as of 19:25, 12 December 2017
Bill's Triangle is a triangle similar to Pascal's Triangle, except each number is obtained by adding the top three numbers, not just the top two. It was found by Bill9000. (If anyone finds someone who found this triangle before, please tell Bill9000.)
How to Make Bill's Triangle
As with Pascal's Triangle, we start with a complete row of zeros. However, in Bill's Triangle, we need another row:
![\[0, 0\]](http://latex.artofproblemsolving.com/5/e/0/5e0ede1941f205dbbfa24d2c2d2b72d70abfd655.png)
![\[0, 0, 0\]](http://latex.artofproblemsolving.com/3/0/a/30afeff78a22a6b76d6fd3a64a2f0b6982221c19.png)
Again, as with Pascal's Triangle, we change a zero to a one:
![\[0, 1, 0\]](http://latex.artofproblemsolving.com/1/b/5/1b5fecf24cfd67990adb180ea7a68817d2beb207.png)
Now, we can add the top three numbers to get the next number. The boxed numbers are the ones we add to get the next row.
![\[\boxed{0}, 0\]](http://latex.artofproblemsolving.com/c/4/1/c412641f322e031bdb64a91c0b9bd8d7d59d9aad.png)
![\[\boxed{0}, \boxed{1}, 0\]](http://latex.artofproblemsolving.com/7/e/b/7eb6639f87dc9e711f37e80dab29f4966c6a643a.png)
We add 
so that is the next number. We also add these numbers:
![\[0, \boxed{0}\]](http://latex.artofproblemsolving.com/c/c/f/ccfe4d54167bf88457d0d424578eba2c455c4a13.png)
![\[0, \boxed{1}, \boxed{0}\]](http://latex.artofproblemsolving.com/1/8/8/18811a346506fa511594c90a102e206da0616695.png)
Therefore, the first few rows of Bill's Triangle are
![\[0, 1, 1, 0\]](http://latex.artofproblemsolving.com/2/f/e/2feeea9ebd9bd21427068cf7dcd690b5ff87e921.png)
We could keep adding zeroes, but as with Pascal's Triangle, we can get rid of them. Hopefully, by now you have gotten the "gist" of Bill's Triangle, and we can proceed to calculate the next few rows:
![\[1\]](http://latex.artofproblemsolving.com/3/4/c/34c083dd559771e8de90399d77a028e339c7a7f7.png)
![\[1 , 1\]](http://latex.artofproblemsolving.com/2/c/9/2c94e7f368cfa5649302607bc71bba7996170b88.png)
![\[1 , 3 , 1\]](http://latex.artofproblemsolving.com/b/4/4/b44cb837665d5312e53c556855a5d74807a34193.png)
![\[1 , 5 , 5 , 1\]](http://latex.artofproblemsolving.com/0/6/c/06c9c763c331edf0b08907fd472ec6b22fd92cf9.png)
![\[1 , 7 , 13 , 7 , 1\]](http://latex.artofproblemsolving.com/6/3/1/631228e03e13f58a9bb952243d3f12bd23c4014b.png)
![\[1 , 9 , 25 , 25 , 9 , 1\]](http://latex.artofproblemsolving.com/6/2/6/62665effd551260d6a0b47851678e86bb0a27697.png)
![\[1, 11, 41, 63, 41, 11, 1\]](http://latex.artofproblemsolving.com/1/a/b/1abf9b7eae319fbcf038dd9e9e95f14d16f94fd3.png)
![\[\vdots\]](http://latex.artofproblemsolving.com/7/6/4/76403adfdd35fb846675aaeaac92daec680a4fba.png)
Why is this useful?
Bill's Triangle counts paths on a grid, just like Pascal's Triangle. While Pascal's Triangle counts the number of ways to get from point 
to point 
on a grid, if you are only allowed to go vertically and horizontally. Bill's Triangle allows you to go diagonally, like in this grid:
![[asy] for (int i = 0; i <= 8; i += 1) { for (int j = 0; j <= 8; j += 1) { draw((0,j)--(i,j)); draw((i,0)--(i,j)); } } for (int j = 0; j <= 8; j += 1) { draw((0,8-j)--(j,8)); draw((8-j,0)--(8,j)); } [/asy]](http://latex.artofproblemsolving.com/2/2/b/22b63db3cac762e9a8cbfb3e5f0daa7d05b6ea03.png)
