3*3网格中的总路径

Question

如果一个人只能向东和向南移动，那么在一个3*3的网格中，从初始点（0,0）到终点（2,2）的总路径数是多少。

- ashmish2

Answer 1

您需要走4步。请将其中的2步朝东走。

- Tom Sirgedas

---

我认为这是正确的，所以我想知道为什么会有两个（匿名）负评？ - Paul R

你的答案是正确的，但我一开始认为人不在网格内，所以答案应该是二项式系数(6,3)，因此我给你点了踩。现在我意识到我错了，但在你编辑帖子之前我无法取消踩。请编辑一些内容，我会给你点赞。对不起 :( - UmmaGumma

Answer 2

Depends on how you define your problem. Here are 3 first ways, that pop into my head.

向量空间问题

1) 从点A(0, 0)到点B(2, 2)创建一个向量AB(B_x-A_x, B_y-B_y)。这个向量存在于仿射空间中，我们将为其引入自定义坐标轴“南”和“东”。因此，我们得到的向量是`AB = 2 "south" + 2 "east"`。

要找出可能的路径：Permutations[{"south", "south", "east", "east"}]

{{"south", "south", "east", "east"}, {"south", "east", "south", "east"}, {"south", "east", "east", "south"}, {"east", "south", "south", "east"}, {"east", "south", "east", "south"}, {"east", "east", "south", "south"}}

要找出它们的长度：Length[Permutations[{"south", "south", "east", "east"}]]

6

代数问题

2) 将问题化简为代数形式。这是一个组合问题，其中二项式系数 4 选择 2 将给出答案，因为您可以总共进行 2 种不同的操作 4 次。

计算方法：Binomial[4, 2]

6

图形问题

3) 绘制一个图形：

然后得出结论，只有6种方法可以完成它。

- Margus

---

代数问题也可以被视为在帕斯卡三角形中移动。http://www.wolframalpha.com/input/?i=Pascal's+triangle - Margus

Answer 3

说明：我们可以通过仅存储向下方向的步骤来编码路径。也就是说，我们只编码选择向下走一步的列：

例如：0 1 1 3 表示我们按照以下方式前进：

 0123      = columns 

 v         v = down
 >V        > = right
  v>v
    X

因此，我们有n行（因此向下有n-1步），在每一步中，我们可以从m个可能性中选择（只要这些可能性是单调递增的）。

因此，我们可以“a priori”从总共的m列中选择n-1个列号，对它们进行排序，并将它们作为我们通过网格的方式。

因此，这个实验相当于从具有m个不同元素的集合中绘制n-1个元素，不考虑绘制的顺序（因为我们只考虑它们按递增顺序）。因此，完成这个实验的总可能性数为：

/ n-1+m-1 \
|         |
\   n-1   /

我意识到我的第一篇帖子包含了错误的细节，但是思路是相同的。请查看星球和棒棒糖来了解这个想法是如何工作的。

- phimuemue

---

@phimuemue -1 二项式(3+3-1,3-1)=二项式(5,2)=10，而你可以看到在我的答案中，至少有20种不同的方法。 - UmmaGumma

@Ashot：这是一个3x3的网格，而不是4x4——只有2次向东移动和2次向南移动，因此有4C2=6种可能性。 - Paul R

@Paul，你说得对。我解决了4*4的问题，但是我的公式是正确的，根据这个解法，我们可以得到10种不同的方法（二项式(3+3-1,3-1)=10），而实际上有20种方法。 - UmmaGumma

@Ashot Martirosyan：修正了公式。 - phimuemue

@phimuemue 现在你的公式是正确的。但是为什么从m个不同元素中无序地选择n-1个元素的不同方法等于Binomial(n-1+m-1,n-1)呢？我认为这并不明显。请解释一下你是如何得出这个公式的，而不使用我们问题的解决方案。 - UmmaGumma

Answer 4

我们必须向东走两次，向南走两次。无论以哪种顺序进行。让我们将东定义为1，南定义为0。那么问题就等同于有多少种长度为4的字符串可以写出两个1和两个0（例如1100或1001等）。

这等于二项式系数（4,2）= 6。

证明：假设南=0，东=1，则以下是所有6种方法：

1100 1010 1001 0110 0101 0011

- UmmaGumma