问题描述
有一行共 $n$ 个地砖，要涂黑色或白色。
- 基础条件：从左往右涂，任意时刻黑色块的数量必须大于等于白色块的数量。
- 进阶条件：在满足基础条件的前提下，要求最后黑色块比白色块多 $m$ 个（$0 \le m \le n$）。
我们将涂黑色记为 $+1$（向上走一步），涂白色记为 $-1$（向下走一步）。 设坐标 $(k, y)$ 表示涂了 $k$ 块砖后，黑块数与白块数的差值为 $y$。
- 起点：$(0, 0)$
- 限制：路径不能低于 $x$ 轴（即 $y \ge 0$）。
1. 仅满足“过程中黑 $\ge$ 白”的方案数
结论
满足该条件的总涂法数为：
$$ A_n = \binom{n}{\lfloor \frac{n}{2} \rfloor} $$推导简述
这是一个经典的格路问题结论。所有从 $(0,0)$ 出发且不穿过 $x$ 轴下方的长度为 $n$ 的路径总数，等于二项式系数中的中间项。
- 当 $n=1$：$\binom{1}{0} = 1$ （黑）
- 当 $n=2$：$\binom{2}{1} = 2$ （黑黑，黑白）
- 当 $n=3$：$\binom{3}{1} = 3$ （黑黑黑，黑黑白，黑白黑）
- 当 $n=4$：$\binom{4}{2} = 6$
- $\cdots$
2. 满足“过程中黑 $\ge$ 白”且“最终黑比白多 $m$ 个”的方案数
前提条件
设最终黑块数为 $B$，白块数为 $W$。
$$ \begin{cases} B + W = n \\ B - W = m \end{cases} \implies B = \frac{n+m}{2}, \quad W = \frac{n-m}{2} $$由于 $B, W$ 必须为整数，因此 $n$ 和 $m$ 必须同奇偶（即 $n \equiv m \pmod 2$）。
- 若 $n, m$ 奇偶性不同，方案数为 0。
- 若 $n < m$，方案数为 0。
计算公式（利用反射原理）
当 $n \equiv m \pmod 2$ 时，合法路径数 = (无限制总路径数) - (触碰 $y=-1$ 的非法路径数)。
-
无限制总路径数： 从 $(0,0)$ 到 $(n, m)$ 的路径数，需向上走 $\frac{n+m}{2}$ 步：
$$ N_{total} = \binom{n}{\frac{n+m}{2}} $$ -
非法路径数： 根据反射原理，从 $(0,0)$ 出发且触碰 $y=-1$ 到达 $(n, m)$ 的路径数，等价于从 $(0, -2)$ 出发到达 $(n, m)$ 的路径数。 此时需要的向上步数为 $\frac{n+(m+2)}{2} = \frac{n+m}{2} + 1$：
$$ N_{bad} = \binom{n}{\frac{n+m}{2} + 1} $$ -
最终公式：
$$ N(n, m) = \binom{n}{\frac{n+m}{2}} - \binom{n}{\frac{n+m}{2} + 1} $$该公式也可化简为广义卡特兰数的形式：
$$ N(n, m) = \frac{m+1}{\frac{n+m}{2} + 1} \binom{n}{\frac{n+m}{2}} $$
总结表格
| 条件 | 公式 | 备注 |
|---|---|---|
| 仅过程约束 | $\displaystyle \binom{n}{\lfloor \frac{n}{2} \rfloor}$ | 适用于所有 $n \ge 1$ |
| 过程 + 终点约束 | $\displaystyle \binom{n}{\frac{n+m}{2}} - \binom{n}{\frac{n+m}{2} + 1}$ | 仅当 $n \equiv m \pmod 2$ 时有效，否则为 0 |
示例验证
假设 $n=4$：
- 仅过程约束： $$ \binom{4}{2} = 6 $$ 合法序列：BBBB, BBBW, BBWB, BWBB, BWBW, BBWW (注意：BWBW 是合法的，因为前缀和分别为 1, 0, 1, 0，从未小于 0)。
- 过程 + 终点 $m=2$ ($n, m$ 同偶)： 需要 $B=3, W=1$。 $$ \binom{4}{3} - \binom{4}{4} = 4 - 1 = 3 $$ 合法序列：BBBW, BBWB, BWBB。 (非法序列：WBBB，因为第一步就变负了)。
- 过程 + 终点 $m=0$ ($n, m$ 同偶)： 需要 $B=2, W=2$。 $$ \binom{4}{2} - \binom{4}{3} = 6 - 4 = 2 $$ 合法序列：BBWW, BWBW。 (非法序列：BWWB, WB…, 等)。