# Why isn't this combinatorial solution equivalent to the recursive solution for finding the number of "paths"?

Here's the problem:

Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right.

Here's my memoized recursive solution, which is relatively straightforward. It works because the number of paths from position (m1, n1) is equivalent to # paths one unit to the right + # paths one unit down + # paths one unit diagonally:

``````def numberOfPaths(m, n, cache = {}):
if (m < 1 or n < 1):
return 0
if (m == 1 and n == 1):
return 1
if ((m, n) not in cache):
cache[(m, n)] = numberOfPaths(m - 1, n, cache) + numberOfPaths(m, n - 1, cache) + numberOfPaths(m - 1, n - 1, cache)
return cache[(m, n)]
``````

Now I want to write a combinatorial solution. If there were no diagonals, this would be easy. You have to move m - 1 units to the right, n - 1 units down, so the number of combinations is just (m - 1 + n - 1) choose (m - 1).

The diagonals complicate it a little bit, but I figure that I can get the # paths with 0 diagonals + # paths with 1 diagonal + ... + # paths with min(m, n) - 1 diagonals (since that's the maximum number of diagonals that are possible; any more and the diagonals would go off of the grid).

To calculate each term, I can just do (m + n - 2 - d) choose d (since there are m + n - 2 - d positions where right, down, or diagonals could go [diagonals take up two spots]) and multiply it by (m + n - 2 - 2 * d) choose (m - 1 - d) -- the number of ways that you can arrange the remaining down/right movements.

``````def combinatorial(m, n):
factorial = math.factorial
def combination(n, k):
return factorial(n) / (factorial(k) * factorial(n - k))
paths = 0
for i in range(0, min(m, n)):
# for 0 through min(m, n) - 1 diagonals,
# sum up the number of combinations that exist with that number of diagonals
paths = paths + combination(m + n - 2 - i, i) * combination(m + n - 2 - 2 * i, m - 1 - i)
return int(paths)
``````

This works in a lot of cases (particularly square grids), but why does this fail on some inputs -- for example, m = 18, n = 88? `numberOfPaths` returns 399615234030198251385775, while `combinatorial` returns 399615234030198283304960 (a slightly larger number). Any tips?

Got it. Turns out it was due to floating point imprecision in the `combination` function. I replaced the function with:
``````def combination(n, k):