使用置换和组合遍历N * N矩阵的方法数

Question

我们的想法是从N * N矩阵的左上角到右下角行进，其中唯一允许的运动是向下或向右。不允许回溯。使用动态编程很简单，如下面的geeks for geeks链接所示。我试图了解如何使用简单的排列和组合来实现同样的目标。我遇到了以下BetterExplained链接。他们正在解决的问题肯定存在不匹配。有没有办法找到使用置换和组合的解决方案？一个指针，可以帮助我更好地理解解决方案？

编辑1：

以下是3X3矩阵的示例，当我们进行动态编程时，它显示了从左上角到最右下角的6种方式，这在使用公式2(N-1)!/ (N-1)!(N-1)!时是可行的。但是我已经列出了20种从原点到目的地到达目的地的方式，这是2N!/N!*N!或者我可以正确理解这个问题是可行的，它是我们已经在左上方的单元格并且遍历到最右边的大部分单元格，案件答案将是6

Answer 1

如果矩阵是正方形（N x N），我相信路径的数量可以如下计算：n = N - 1：

from math import factorial

def number_of_paths(n):
    return int(factorial(2 * n) / (factorial(n) ** 2))

至于为什么......这有点复杂。首先，不要考虑向下和向右，让我们将矩阵旋转45度，以便我们总是向下，但选择向左或向右。

我们的矩阵现在是一个钻石站在它的尽头，形成Pascal's triangle的中心。这意味着我们可以看看帕斯卡三角形底部中心的binomial coefficient，它是我们矩阵的两倍 - 1。

我们使用二项式系数，因为它的一个解释是它显示了我们可以选择到达那里的路径数量。

例如在3 x 3案例中，2 * 3 - 1 = 5：

       [1]                          C(0,0)
     [1   1]                    C(1,0), C(1,1)
   [1   2   1]              C(2,0), C(2,1), C(2,2)
  1  [3   3]   1        C(3,0), C(3,1), C(3,1), C(3,1)
1   4 [!6!]  4   1  C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)

   Answer is 6!              Answer is C(4, 2)!

答案结果是(2n)! / n! ** 2（下面的推导），我们可以直接计算。

您还可以通过移动您关心的底行中的项目来推广到非方形矩阵，此时您基本上只能得到C(n, k)。希望很清楚为什么。

只是数学！

从上图中我们可以看出N的前三个值是：

N | Value
- + -------
1 | C(0, 0)
2 | C(2, 1)
3 | C(4, 2)

因此，我们可以看到答案是：

= C(2(N - 1), N - 1)

let n = N-1
Given C(a, b) = a! / b!(a - b)!

= C(2n, n)
= (2n)! / n!(2n - n)!
= (2n)! / n! ** 2

路径长度的几何解释

想象一下4x4矩阵的情况，试着看看为什么长度是2(N-1)。先是几点意见：

• 所有路径长度都相同
• 因此，我们可以考虑任何特定的路径来检查所有人的长度
• 因此，我们考虑以下路径： 左上角到右上角（全部右转） 然后从右上角到右下角（全部向下）

首先，我们从左上方开始，没有进行任何移动，并沿着顶部进展：

0 - - -     0 1 - -     0 1 2 -     0 1 2 3
- - - -  >  - - - -  >  - - - -  >  - - - -  
- - - -     - - - -     - - - -     - - - - 
- - - -     - - - -     - - - -     - - - -

经过3次移动后，我们遍历了长度为4的一侧。因此，对于长度为N的一侧，需要N-1移动来遍历。对于垂直方向也是如此，它将需要我们另一个N-1移动从顶部到底部：

0 1 2 3     0 1 2 3     0 1 2 3     0 1 2 3
- - - -  >  - - - 4  >  - - - 4  >  - - - 4  
- - - -     - - - -     - - - 5     - - - 5 
- - - -     - - - -     - - - -     - - - 6

因此总路径长度为2(N-1)

Answer 2

有(n-1) among 2(n-1)方法用你给出的规则遍历n*n矩阵。

一个简单的解释：由于允许的唯一运动是downward或rightward，所以路径必须是2(n-1)的长度。 更重要的是，在这条道路上，将有n-1移动downward，而n-1移动rightward（这是从左上角到达右下角的唯一可能方式）。 所以(n-1) among 2(n-1)来自所有可能的方式，以适应n-1向下移动2(n-1)执行。