Редактировать: добавлен расчет для произвольной ячейки, а не только для диагональной.
Количество путей на квадратной сетке известно как Деланной числа , для (n, n) последовательность ячеек равна 1, 3, 13, 63, 321, 1683, 8989...
. Существует простое естественное повторение
D(m, n) = D(m-1, n) + D(m, n-1) + D(m-1,n-1)
, которое можно использовать для довольно быстрого вычисления значений для разумных значений аргументов (табличный подход, O (нм)операции, включая длинное суммирование).
«Закрытая формула»
D(m, n) = Sum[k=0..min(n, m)] {C(m + n - k, m) * C(m, k)}
для эффективной реализации требуется таблица биномиальных коэффициентов
#2D table quadratic approach
def PathsInSqGrid(n, m):
D = [[0 for x in range(m+1)] for y in range(n+1)]
for i in range(n+1):
D[i][0] = 1
for i in range(m+1):
D[0][i] = 1
for i in range(1, n+1):
for j in range(1,m+1):
D[i][j] = D[i][j-1] + D[i-1][j] + D[i-1][j-1]
return D[n][m]
def NCr(n, k):
result = 1
if k > n - k:
k = n - k
for i in range (1, k + 1):
result = (result * (n - i + 1)) // i
return result
#closed formula
def PathsCF(n, m):
#D(m, n) = Sum[k=0..min(n, m)] {C(m + n - k, m) * C(m, k)}
res = 0
for k in range(0, min(n, m) + 1):
res += NCr(m + n - k, m) *NCr(m, k)
return res
print(PathsInSqGrid(7, 9))
print(PathsCF(7, 9))
>>>
224143
224143
Вики также показывает два так называемых "«Закрытые формулы» для центральных чисел Деланной (хотя я считаю, что закрытая формула должна быть одним выражением без цикла длины n):
D(n) = Sum[k=0..n]{C(n,k)*C(n+k,k)}
D(n) = Sum[k=0..n]{C(n,k)^2 * 2^n}
и повторение (выглядит просто, линейная сложность, но реальная реализация требует разделения длинныхномер по короткому)
n*D(n) = 3*(2*n-1) * D(n-1) - (n-1)*D(n-2)
и генерирующая функция
Sum[n=0..Inf]{D(n)*x^n} = 1/Sqrt(1 - 6 * x + x^2) = 1 + 3x + 13x^2 + 63x^3 +...
Код
#central Delannoy numbers
#2D table quadratic approach
#linear approach for diagonal cell (n,n)
def PathsInSqGridLin(n):
if n < 2:
return 2 * n + 1
A, B = 1, 3
for i in range(2, n + 1):
B, A = (3 * (2 * i - 1) * B - (i - 1) * A) // i, B
return B
print(PathsInSqGridLin(3))
print(PathsInSqGridLin(100))
>>
63
2053716830872415770228778006271971120334843128349550587141047275840274143041