来自讨论组群：三叶装饰品，只能取有 1 个或 0 个相邻的

kuing

鱼子  2025/4/11 10:28
某次庆典后，墙壁上的装饰品需要取下来，如图，由于材料特性，每次只能取一个，且所取的装饰品只能有 1 个或 0 个相邻的装饰品，则不同的取法数有_______种.

有啥好嘀办法呢？

kuing

一个笨方法：
首先，如果是没分支的一串 `n` 个：$\underbrace{{\bigcirc}\mkern-2mu{\bigcirc}\cdots{\bigcirc}}_{n\text个}$，那取法数是 `2^{n-1}`。
看回原题，三叶中，总有一叶先取完，假设右边那一叶先取完，有以下情况：
（1）右边那一叶取完时，另外两叶未取。
那就是先取右边（方向由右向左），然后再取左边一串，可以看成是分开的：

这种取法数是 `2^4`；

（2）右边那一叶取完时，左上叶已经取了一个。
那可以看成左上那一个拿出来插入到右叶中，有两个位置可以插入，如图：

因此这种取法数是 `2\times2^3`；

（3）右边那一叶取完时，左下叶已经取了一个，同（2）；

（4）右边那一叶取完时，左边两叶已各取一个。
类似地，将左边那两个插入到右叶，如图：

此时右边有 `3!` 种排法，所以这种取法数是 `3!\times2^2`。

综上，右叶先取完的取法数为 `2^4+2\times2^3+2\times2^3+3!\times2^2=72`，同理，另外两叶先取完的也一样，所以此数 `\times3` 即为所求，所以答案是 `216`。

kuing

那如果每叶继续加长：

楼上这种笨算法还能继续嘛？🤔

emmm..... 似乎可以喔！

为便于描述，给三叶加上红绿蓝三色，每叶 `n` 个，如上图。

假设红色先取完，设当红的取完的时刻，绿的已取 `x` 个，蓝的已取 `y` 个（`x`, `y\in[0,n-1]`）。

则可看成拿下 `x` 个绿的、`y` 个蓝的插入到右叶中，插入时同一颜色的保持相对顺序不变。

计算插入的方法数：
插入完后，右叶共 `n+x+y` 个，其中与中心连接的那个一定是红色。
其余 `n+x+y-1` 个位置，选 `x` 个放绿色，再选 `y` 个放蓝色，剩下为红色。
所以插入的方法数为 `C_{n+x+y-1}^xC_{n+y-1}^y`，即 `(n+x+y-1)!/\bigl(x!y!(n-1)!\bigr)`。

剩下的 `n-x` 个绿 + 中心 + `n-y` 个蓝的取法数是 `2^{2n-x-y}`。

以上两式相乘，再让 `x`, `y` 取遍 `[0,n-1]` 内的整数，求和，就是红色先取完的方法数，再 `\times3` 得总的取法数，因此结果是
\[3\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\frac{(n+x+y-1)!}{x!y!(n-1)!}2^{2n-x-y}.\]
不知能不能化简。

===== 验证 =====
当 `n` 为 1~5，上式给出的数值分别是 12, 216, 4440, 97440, 2224152
看来 `n=2` 与上面的结果一样，`n=1` 数一下也知道没错，公式大概率正确😃
3~5 的看来很难数，能否编程验证之？

kuing

更一般地，改为红色 `n_1` 个，绿色 `n_2` 个，蓝色 `n_3` 个，取法总数为 `f(n_1,n_2,n_3)`，则
\begin{align*}
f(n_1,n_2,n_3)={}&\sum_{x=0}^{n_2-1}\sum_{y=0}^{n_3-1}\frac{(n_1+x+y-1)!}{x!y!(n_1-1)!}2^{n_2+n_3-x-y}\\
&+\sum_{x=0}^{n_3-1}\sum_{y=0}^{n_1-1}\frac{(n_2+x+y-1)!}{x!y!(n_2-1)!}2^{n_3+n_1-x-y}\\
&+\sum_{x=0}^{n_1-1}\sum_{y=0}^{n_2-1}\frac{(n_3+x+y-1)!}{x!y!(n_3-1)!}2^{n_1+n_2-x-y}.
\end{align*}

更更一般地，再加多一叶：

红绿蓝黄数量分别为 `n_i`（`i=1`, `2`, `3`, `4`）。
仍然可以照此法分析，假设红色先取完，设红取完时其他三色分别取下 `x`, `y`, `z` 个，插入到红色中，`(n_1+x+y+z-1)!/\bigl(x!y!z!(n_1-1)!\bigr)` 种插法，剩下的就用上述公式，即 `f(n_2-x,n_3-y,n_4-z)`，所以，红色先取完的取法数为
\[\sum_{x=0}^{n_2-1}\sum_{y=0}^{n_3-1}\sum_{z=0}^{n_4-1}\frac{(n_1+x+y+z-1)!}{x!y!z!(n_1-1)!}f(n_2-x,n_3-y,n_4-z),\]
然后对上式的 `(n_1,n_2,n_3,n_4)` 作轮换，一共四式，相加就是四叶的取法总数。

如此下去，`n` 叶也可以。