定义
- 一组 \(n\) 的划分（composition）是一个正整数序列 \(\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_k)\)，满足 \(\sum \alpha_i = n\)。
基础组合
证明
考虑插板法。\(|\alpha|\) 即板子的数量 \(+1\)。我们对每个位置强制放板子的情况算贡献，可以得到 \(\sum(|\alpha| - 1) = (n - 1)2^{n - 2}\)。
又有 \(\#\{\alpha\} = 2^{n - 1}\)，故 \(\sum |\alpha| = (n - 1) 2^{n - 2} + 2^{n - 1} = (n + 1)2^{n - 2}\)。
证毕。
证明
考虑插板法。我们先确定下来前 \(n - 2\) 个空隙是否插板，一共 \(2^{n - 2}\) 种方案。
考虑最后一段的长度，即 \(\alpha_k\) 的值。若最后一个空隙插板，则其会变成 \(1\) 和 \(\alpha_k - 1\)，此时 \(\#\{2\mid \alpha_i\} \bmod 2\) 一定改变。
因此不管原先的序列是否满足条件，一定只有一种确定最后一个空隙的方案。从而 \(\text{LHS} = 2^{n - 2} = \text{RHS}\)。
证毕。
有 \(k\) 个 \(\{1, 2, \cdots, n\}\) 的子集 \(S_1, S_2, \dots, S_k\)。对满足如下条件的有序列表 \((S_1, S_2, \cdots, S_k)\) 计数：
- a. \(S_1 \subseteq S_2 \subseteq \cdots \subseteq S_k\)
- b. \(S_i\) 两两不交
- c. \(S_1 \cap S_2 \cap \cdots \cap S_k = \emptyset\)
解答
a. \((k+1)^n\)。由条件我们知道若 \(x \in S_i\)，则 \(\forall j > i, x \in S_j\)。因此我们对于每个 \(1 \leq x \leq n\) 都要选择其第一次出现的集合是哪个（或令其永不出现），方案数 \((k + 1)^n\)。
b. \((k+1)^n\)。本问与 a. 可以建立双射。a. 中任意一组方案的差分对应本问的一种方案。
c. \((2^k - 1)^n\)。对值 \(x\) 出现的位置集合 \(T_x\) 考虑，最终的 \(\bigcap S\) 出现 \(x\) 当且仅当 \(T_x = \{1, 2, \cdots, k\}\)，因此 \(T_x\) 有 \(2^k - 1\) 种选法。从而总方案数 \((2^k - 1)^n\)。
证明
我们认为右边的式子描述的是从 \(x + n + 1\) 个球里取出 \(n\) 个。
令左式枚举的 \(k\) 满足：在取球时，末尾连续取了 \(n - k\) 个球。那么我们只需在剩下的 \(x + k\) 个球里选出 \(k\) 个即可。方案数 \(\binom{x + k}k\)。
为什么剩下 \(x + k\) 个球而非 \(x + k + 1\) 个球？注意倒数第 \(n - k + 1\) 个球是强制不取的。
证毕。