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

Question

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?

Answer 1

Got it. Turns out it was due to floating point imprecision in the combination function. I replaced the function with:

def combination(n, k):
 return factorial(n) // factorial(k) // factorial(n - k)

and now it works. Sanity restored.