《组合数学》 §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

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