第17章　定序、相同元素分配、错排与分堆

1. 定序

若 $n$ 个不同对象中，$k$ 个对象的相对先后固定，但不要求相邻，则总排列数除以 $k!$。例如 A、B、C 必须按 A 在 B 前、B 在 C 前，所有顺序中仅占 $1/3!$。

2. 相同元素分配

把 $n$ 个相同物品分给 $k$ 个不同人，每人至少 1 个：

$$(\genfrac{}{}{0ex}{}{n-1}{k-1}).$$

每人可得 0 个：

$$(\genfrac{}{}{0ex}{}{n+k-1}{k-1}).$$

以 5 个相同球分给 3 个不同盒子为例：每盒至少 1 个，先放 2 个隔板，5 个球之间有 4 个空隙可选，所以有 $C_4^2=6$ 种；允许空盒时有 $C_7^2=21$ 种。盒子可区分，所以把球数 $(3,1,1)$ 分给不同盒子时，要区分是哪一个盒子拿到 3 个。

有最低配额 $x_i\ge a_i$，先发配额，剩下再用隔板法。若还有限制“某组至少两件/每组不同”等，隔板法可能不适用，需要分类枚举。

3. 错位排列

$n$ 个对象全部不能回到原位的错排数记为 $D_n$：

$$D_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!},D_n=(n-1)(D_{n-1}+D_{n-2}).$$

小规模常见值：$D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265$。只问“恰有一个回原位”时，可选该人，再对其余人作不固定点限制，需注意其余排列不能使额外的人回原位。

4. 分堆与分组

把 $2n$ 个不同人分成两组，每组 $n$ 人且组无标签：

$$\frac{(\genfrac{}{}{0ex}{}{2n}{n})}{2}.$$

若两组承担不同任务、组有标签，则不除以 2。多人平均分堆的除数取决于“堆是否可区分”，这是易错核心。