# Counting Routes Problem¶

## Let's count the number of routes from the bottom-left square to the top-right square¶

### Solve this problem for both the 4x4 board and the 5x5 board¶

In [1]:
def routes(x,y):
if x == 1:
return 1
elif y == 1:
return 1
else:
return routes(x-1,y)+routes(x,y-1)

In [2]:
routes(8,8)

Out[2]:
3432
In [3]:
for x in (5,4,3,2,1):
print([routes(x, y) for y in [1,2,3,4,5]])

[1, 5, 15, 35, 70]
[1, 4, 10, 20, 35]
[1, 3, 6, 10, 15]
[1, 2, 3, 4, 5]
[1, 1, 1, 1, 1]


## Let's look at the third row above, the row starting with [1,3,6,10,15].¶

### What is the pattern? Is there a simple function that generates these numbers?¶

In [4]:
print([routes(x, 3) for x in [1,2,3,4,5,6,7,8,9,10]])

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

In [5]:
%%html
<script src="https://cdn.geogebra.org/apps/deployggb.js"></script>

In [6]:
%%html
<div id="ggb-point"></div>
<script>
var ggbApp = new GGBApplet({
"height": 400,
"showToolBar": true,
"showAlgebraInput": true,
"showResetIcon": true,
"enableLabelDrags": true,
"enableRightClick": true,
"enableShiftDragZoom": true,
"useBrowserForJS": false,
}, 'ggb-point');

ggbApp.inject();
</script>


## Let f(1)=1, f(2)=3, f(3)=6, f(4)=10, f(5)=15. What is the function f(x)?¶

### Can you explain WHY this formula is true?¶

In [16]:
def f(x):
# replace the numbers 0.6, 0.7, 0.8 with the numbers a, b, c you found above
return (0.6)*x*x + (0.7)* x + (0.8)

print([f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8)])

[2.0999999999999996, 4.6, 8.299999999999999, 13.2, 19.3, 26.599999999999998, 35.1, 44.8]