《组合数学》 §1.3 学习笔记

1.3.1 ~ 1.3.7 和 1.3.11 ~ 1.3.16

这部分请参考 小蓝书 16.1 。书上例题也都比较经典/简单，所以不写了

例 1.3.8

把集合 $\{1,2,\cdots,n\}$ 划分 $b_1$ 个 $1$–子集，$b_2$ 个 $2$–子集，……，$b_k$ 个 $k$ 元集，其中 $\sum_{i=1}^k i b_i = n$ ，求方案数。

解 $b_i$ 个子集之间没有顺序，那么就是

$$\frac{\dbinom{n}{1,\cdots,1,2,\cdots,2,3,\cdots,3,k,\cdots,k}}{b_1!b_2!\cdots b_k!}$$

其中 “$\cdots$” 有多少个取决于 $b_i$ 。

注 1.3.9

进一步，一个 $n$–集合的全体划分数为

$$\sum_{b_1 + 2b_2 + \cdots + nb_n = n} \frac{n!}{b_1!b_2!\cdots b_n!(1!)^{b_1}(2!)^{b_2}\cdots(n!)^{b_n}}$$

例 1.3.10

本部分涉及群论内容，参考 群论基础 。

记集合 $[n] = \{1,2,\cdots,n\}$ ，显然 $[n]$ 到其自身的双射（即 $n$ 元置换）全体在映射合成下构成一个群，

即 $n$ 元对称群 $S_n$ ，其中任一置换 $\sigma$ 均为表示为 $S_n$ 中一些互不相交（即两两无公共元素）的轮换之积，

且这种表示方式在不考虑轮换次序的意义下唯一，称为 $\sigma$ 的轮换分解。

对 $\sigma \in S_n$ ，用 $l_i(\sigma)$ 表示 $\sigma$ 的轮换分解中长度为 $i$ 的轮换个数，

则称 $(l_1(\sigma),l_2(\sigma),\cdots,l_n(\sigma))$ 为 $\sigma$ 的轮换型号，记为 $\operatorname{type}(\sigma)$ 。

若 $1l_1 + 2l_2 + \cdots + n l_n = n$ ，求 $S_n$ 中轮换型号为 $(l_1,l_2,\cdots,l_n)$ 的置换的个数。

解 与上例方法类似，可知

$$\frac{n!}{l_1!l_2!\cdots l_n!(1!)^{l_1}(2!)^{l_2}\cdots(n!)^{l_n}} \prod_{i=1}^n ((i-1)!)^{l_i} = \frac{n!}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}$$

此即 Cauchy 公式 。

例 1.3.17

这个叫十二重计数方法，也就是放球问题 。