|
|
kuing
posted 2025-6-21 14:43
Last edited by kuing 2025-6-21 15:58参照这帖：forum.php?mod=viewthread&tid=4099
等价于由 `(0,0)` 到 `(n,n)` 且恒满足 `\abs{y-x}\leqslant2` 的最短路径数。
也是用排除法，若 `\abs{y-x}>2`，则要么与 `y=x+3` 有公共点，要么与 `y=x-3` 有公共点，由对称性，这两种情况是一样的，只需计算其中一种。
也是用对称法，当与 `y=x+3` 有公共点时，将 `(0,0)` 与第一个共公点的部分沿 `y=x+3` 作对称，变成 `(-3,3)` 到 `(n,n)` 的一条最短路径，所以是 `C_{2n}^{n-3}`。
综上，所求为 `C_{2n}^n-2C_{2n}^{n-3}`。
代 `n=4` 得 `C_8^4-2\times8=54`。
有问题，一般表达式没那么简单，如果 `n\geqslant6`，则路径可以同时与 `y=x+3` 和 `y=x-3` 相交，那么上面的计算方法就有重复 ，所以上面的式子只对 `n\leqslant5` 成立，`n\geqslant6` 还需要加回同时相交的数目，待修正…… |
|
