一道组合

hjfmhh

有8张除颜色外完全相同的纸牌，其中4张为红色纸牌，4张为蓝色纸牌，将全部纸牌按照某种顺序一张一张地放到桌面上，要求放置的过程中，桌上的红色纸牌与蓝色纸牌数量之差的绝对值始终不超过2，则有   种不同的放置顺序.

kuing

参照这帖：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` 相交，那么上面的计算方法就有重复，所以上面的结果 `C_{2n}^n-2C_{2n}^{n-3}` 只对 `n\leqslant5` 成立，对原题是没问题，而 `n\geqslant6` 则需要加回同时相交的数目，有待修正……

hjfmhh

解：设红色纸牌数为 $r$，蓝色纸牌数为 $b$，定义状态 $(r, b)$，初始状态 $(0,0)$，每次只能放红牌或蓝牌，需满足 $|r-b| \leqslant 2$，
第一步：$(1,0)$ 或 $(0,1)$，各 1 种
第二步：$(2,0) 1$ 种，$(1,1) 2$ 种，$(0,2) 1$ 种
第三步：$(2,1) 3$ 种，$(1,2) 3$ 种
第四步：$(3,1) 3$ 种，$(2,2) 6$ 种，$(1,3) 3$ 种
第五步：$(3,2) 9$ 种，$(2,3) 9$ 种
第六步：$(4,2) 9$ 种，$(3,3) 18$ 种，$(2,4) 9$ 种
第七步：$(4,3) 27$ 种，$(3,4) 27$ 种
第八步：$(4,4) 54$ 种
故有 54 种不同的放置顺序．故答案为 54．

kuing

在网格中，设由原点到 `(n,n)` 且恒满足 `\abs{y-x}\leqslant2` 的最短路径数为 `S_n`。

在到达 `(n,n)` 的前一步，要么是到达 `(n-1,n)` 要么是到达 `(n,n-1)`，由对称性，到达这两个点的路径数是相同的，因此，由原点到 `(n-1,n)` 以及由原点到 `(n,n-1)` 的路径数都是 `0.5S_n`。

于是如下图所示：

考虑到达 `(n+1,n)` 的路径：
要么由 `(n,n)\to(n+1,n)`（红线），
要么由 `(n,n-1)\to(n+1,n-1)\to(n+1,n)`（绿线），
于是有 `0.5S_{n+1}=S_n+0.5S_n`，即 `S_{n+1}=3S_n`，这就是递推关系！

显然 `S_1=2`，所以答案就是 `S_n=2\times3^{n-1}`。

hjfmhh

kuing 发表于 2025-6-21 18:48
在网格中，设由原点到 `(n,n)` 且恒满足 `\abs{y-x}\leqslant2` 的最短路径数为 `S_n`。

在到达 `(n,n)`  ...

这个递推关系是不是只要|y-x|<=k,其中k是大于等于2就可以？

kuing

hjfmhh 发表于 2025-6-21 20:36
这个递推关系是不是只要|y-x|<=k,其中k是大于等于2就可以？

没那么简单。

就比如改成 `\abs{y-x}\leqslant3`，道路加宽后，5# 图中能到达 `(n+1,n)` 的就不止红绿那两条线，还可以是 `(n+1,n-2)\to(n+1,n-1)\to(n+1,n)`，而 `(n+1,n-2)` 是多少还不知道，情况就不一样了。

我想了一下，对于 `\abs{y-x}\leqslant3`，如图：

图中的字母表示原点到该点的路径数，这些数的关系就类似于杨辉三角那样，所以有
\begin{align*}
d&=b+b=2b,\\
g&=e+e=c+2d+c=a+3b+3b+a=2a+6b,\\
i&=c+3e+3e+c=4c+6d+4c=4a+10b+10b+4a=8a+20b,
\end{align*}
由此可得
\[i=4g-2d,\]
因此递推关系是
\[S_{n+2}=4S_{n+1}-2S_n,\]
然后由 `S_1=2`, `S_2=6`，求得
\[S_n=\frac{\bigl(2+\sqrt2\bigr)^n+\bigl(2-\sqrt2\bigr)^n}2,\]
它的前十项为 2, 6, 20, 68, 232, 792, 2704, 9232, 31520, 107616，哪位编程大佬写个程序验证一下……

另外我猜想 `\abs{y-x}\leqslant k` 的递推应该会是 `k-1` 阶线性递推，但像上面这样一步步推似乎有点笨，估计还会有更简洁的方法……