Walking through houses
Imagine yourself standing at the origin of a grid of streets that divide the city into square blocks of equal size.
You want to reach the point 5 blocks north and 5 blocks east from your current location, and you can (as usual) walk along the streets to the north and east, but you can also walk diagonally through a block (You can make the moves (0,1), (1,0) and (1,1)).
How many ways are there to reach your destination?
The answer is 1683.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
These numbers are called Delannoy numbers
If we define D ( n , k ) to be the number of ways through a grid of size n × k under the given conditions, then we can set up the following recursive formula
D ( n , k ) = D ( n − 1 , k ) + D ( n , k − 1 ) + D ( n − 1 , k − 1 )
This is because there are three possibilities for the last move and for each of them the number of ways to do all moves before is given by a previous Delannoy number.
Using this recursion, we can set up a table that gives the number of ways to reach the point ( n , k ) . We start with 1's in the first row and column and then use the recursion. Every number is the sum of the number above it, to the left of it and above and to the left of it.
0 1 2 3 4 5 k 0 1 1 1 1 1 1 1 1 3 5 7 9 1 1 2 1 5 1 3 2 5 4 1 6 1 3 1 7 2 5 6 3 1 2 9 2 3 1 4 1 9 4 1 1 2 9 3 2 1 6 8 1 5 1 1 1 6 1 2 3 1 6 8 1 1 6 8 3 n