求网格孤立路数

kuing

如图，甲从 A 到 B，乙从 C 到 D，两人只能沿着网格线向上或者向右走，如果两个人的线路不相交，则称这两个人的路径为一对孤立路，那么不同的孤立路一共有几对？

kuing

先写一点思路的开头：不妨设 A(0,0), D(6,4)，设：
甲路径中的 4 次向右走的纵坐标分别为 `a_1`, `a_2`, `a_3`, `a_4`，
乙路径中的 4 次向右走的纵坐标分别为 `b_1`, `b_2`, `b_3`, `b_4`，
例如下图的走法为 `(a_1,a_2,a_3,a_4)=(0,2,3,3)`, `(b_1,b_2,b_3,b_4)=(1,2,2,4)`：

由条件有 `0\leqslant a_1\leqslant a_2\leqslant a_3\leqslant a_4\leqslant 4`, `0\leqslant b_1\leqslant b_2\leqslant b_3\leqslant b_4\leqslant 4`，
要不相交，还得满足 `b_1<a_2`, `b_2<a_3`, `b_3<a_4`。
这样就转化为求同时满足以上不等式组的整数解的解数。

（也不知这样转化有没有用
不过至少可以通过 mma 用程序

1. Reduce[0 <= a1 <= a2 <= a3 <= a4 <= 4 && 0 <= b1 <= b2 <= b3 <= b4 <= 4 && b1 < a2 && b2 < a3 && b3 < a4, {a1, a2, a3, a4, b1, b2, b3, b4}, Integers] // Length

Copy the Code

得到答案是 1750 😁）

待续……

@hbghlyj 别光点赞，想下有啥办法呗，我搞不定……

Aluminiumor

把你的方法写成嵌套求和就是这样（并没有什么用）：
$$\sum_{i=1}^4\sum_{j=i}^4\sum_{k=j}^4\sum_{w=k}^4\sum_{i'=0}^{j-1}\sum_{j'=i'}^{k-1}\sum_{k'=j'}^{w-1}\sum_{w=k'}^{4}+\sum_{j=1}^4\sum_{k=j}^4\sum_{w=k}^4\sum_{i'=0}^{j-1}\sum_{j'=i'}^{k-1}\sum_{k'=j'}^{w-1}\sum_{w=k'}^{4}=1750$$
（前者为 $a_1\geq1$，后者为 $a_1=0$）

1. Sum[1, {i, 1, 4}, {j, i, 4}, {k, j, 4}, {w, k, 4}, {i', 0, j - 1}, {j',i', k - 1}, {k', j', w - 1}, {w', k', 4}] + Sum[1, {j, 1, 4}, {k, j, 4}, {w, k, 4}, {i', 0, j - 1}, {j', i', k - 1}, {k', j', w - 1}, {w', k', 4}]

Copy the Code

@hbghlyj 别光点赞，想下有啥办法呗，我搞不定……

kuing

Aluminiumor 发表于 2025-5-10 20:51
把你的方法写成嵌套求和就是这样（并没有什么用）：
$$\sum_{i=1}^4\sum_{j=i}^4\sum_{k=j}^4\sum_{w=k}^4\ ...

牛P😂😂

abababa

发maven的解答，我看不懂：
用 LVG，先算几个数：
甲 A->B 共有 C(8,4) = 70 个路径
乙 C->D 共有 C(8,4) = 70 个路径
甲 A->D 共有 C(10,6) = 210 个路径
乙 C->B 共有 C(6,2) = 15 个路径

矩阵
[A->B, A->D]
[C->B, C->D]
=
[70, 210]
[15, 70]

的行列式就是你要求的。

有没有能看懂的，用这个例子详细介绍一下。

kuing

abababa 发表于 2025-5-25 10:54
发maven的解答，我看不懂：
用 LVG，先算几个数：
甲 A→B 共有 C(8,4) = 70 个路径

我似乎明白了😃
孤立路 = 任意路 - 相交路。
“任意路”就是 (A→B)*(C→D)
关键是“相交路”：
如果两条路相交，则可以看成甲从 A 走到 D、乙从 C 走到 B？所以“相交路” = (A→D)*(C→B)？
要证明这一点，需要证明“相交路”与 A→D 且 C→B 可以一一对应。

似乎可以这样：取相交路径的第一个交点，在这点之后交换两人的路线，即构成一一对应。
如下图：从首个交点 E 处之后，交换两路的颜色，形成 A→D, C→B 的路线。

反之，对于 A→D, C→B 的任意路，由于必相交，取首个交点，交换此点后的两路颜色，也就对应 A→B, C→D 的一条相交路。

综上，答案就是 `C_8^4C_8^4-C_{10}^6C_6^2=1750`。

PS、代码作图真好，上面这两图直接拿 2# 的代码稍微改改就出来了😇

abababa

kuing 发表于 2025-5-25 12:57
我似乎明白了😃
孤立路 = 任意路 - 相交路。
“任意路”就是 (A→B)*(C→D)

原来如此。