Perché questa soluzione combinatoria non è equivalente alla soluzione ricorsiva per trovare il numero di "percorsi"?

Ecco il problema:

Dato un array m x n, ottieni il numero di percorsi diversi dall'angolo in alto a sinistra all'angolo in basso a destra, se puoi solo muoverti verso il basso, a destra e in diagonale verso il basso e amp; a destra.

Ecco la mia soluzione ricorsiva memorizzata, che è relativamente semplice. Funziona perché il numero di percorsi dalla posizione (m1, n1) è equivalente a # percorsi di un'unità a destra + # percorsi di un'unità verso il basso + # percorsi di un'unità in diagonale:

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)]

Ora voglio scrivere una soluzione combinatoria. Se non ci fossero diagonali, sarebbe facile. Devi spostare m - 1 unità a destra, n - 1 unità verso il basso, quindi il numero di combinazioni è solo (m - 1 + n - 1) scegliere (m - 1).

Le diagonali lo complicano un po ', ma immagino di poter ottenere i # percorsi con 0 diagonali + # percorsi con 1 diagonale + ... + # percorsi con min (m, n) - 1 diagonale (poiché ciò è il numero massimo di diagonali che sono possibili, e le diagonali andrebbero fuori dalla griglia).

Per calcolare ogni termine, posso solo fare (m + n - 2 - d) scegliere d (dato che ci sono m + n - 2 - d posizioni in cui destra, in basso o diagonali potrebbero andare [le diagonali occupano due punti ]) e moltiplicalo per (m + n - 2 - 2 * d) scegli (m - 1 - d) - il numero di modi in cui puoi organizzare i movimenti rimanenti in basso / a destra.

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)

Funziona in molti casi (in particolare le griglie quadrate), ma perché questo non funziona su alcuni input, ad esempio, m = 18, n = 88? numberOfPaths restituisce 399615234030198251385775, mentre combinatorial restituisce 399615234030198283304960 (un numero leggermente più grande). Qualche consiglio?