时间戳

首页 > 解决方案 > 允许对角线移动时方形网格中可能的路径总数

combinatorics - 允许对角线移动时方形网格中可能的路径总数

问题描述

我应该如何回答这个问题-“如果允许步骤 R（向右）和 U（向上）以及对角线步骤 D，则计算从 (0,0) 到 (7,9) 的可能路径的总数： (x,y)→(x +1,y+ 1)"

标签： combinatorics

解决方案

编辑：为任意单元格添加了计算，而不仅仅是对角线单元格。

方格上的路数称为Delannoy 数，对于 (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(nm) 操作，包括长求和）。

“封闭式”

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

Wiki 还显示了两个所谓的中心 Delannoy 数的“封闭公式”（虽然我认为封闭公式应该是没有长度为 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

推荐阅读