多重组合数的应用-集合的划分数、对称群的共轭类计数

摘要: 多重组合的若干应用场景

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在 n 元对称群中，每个置换根据其轮换分解中各个长度的轮换的个数，可以将置换分为各个型号。一个自然的问题是，在 n 元对称群中给定置换的型号，该型号的置换有多少个，这个计数结果对了解群的结构很有帮助。

本文我们首先复习一下多重排列和多重组合，然后由多重组合推导出 n 元素集合的划分数，然后进一步推导出 n 元对称群中给定型号的置换个数，最终结果称为柯西公式。

多重集的排列与多重组合

在 组合数学1-排列组合 中，我们提到过多重组合数，这里做个复习。

多重集的排列也就是有重复元素的排列，考虑多重集合（有重复元素的集合）$\{r_{1} \cdot a_{1}, r_{2} \cdot a_{2}, …, r_{k} \cdot a_{k}\}$，多重集的排列就是将该集合所有元素排成一排的方案数。

多重集的排列可以看做多重组合的问题：在 n 个位置中($n = \sum\limits_{i=1}\limits^{k}r_{i}$)，选出 $r_{1}$ 个给 $a_{1}$、然后再剩下的位置中选出 $r_{2}$ 个给 $a_{2}$，以此类推，最后剩下的 $r_{k}$ 个位置给 $a_{k}$。总的选法数如下：

$$\binom{n}{r_{1}}\binom{n-r_{1}}{r_{2}}\binom{n-r_{1}-r_{2}}{r_{3}}\cdots\binom{n-r_{1}-\cdots-r_{k-1}}{r_{k}} \\ = \frac{n!}{(r_{1}!r_{2}!\cdots r_{k}!)}$$

因此多重集的排列数（多重组合的乘积）为：

$$P(n; r_{1}, r_{2}, \cdots, r_{k}) = \frac{n!}{(r_{1}!r_{2}!\cdots r_{k}!)}$$

多项式定理

有了多重组合，可以立刻得到多项式定理：

$$(a + b)^{n} = \sum_{0 \lt k \lt n}C(n, k)a^{k}b^{n-k}$$ $$(a_{1}+a_{2}+\cdots+a_{k})^{n} = \sum\frac{n!}{r_{1}!r_{2}!\cdots r_{k}!}a_{1}^{r_{1}}\cdots a_{k}^{r_{k}}$$

n集合的全体划分数

考虑集合 $\{1, 2, \cdots, n\}$，将该集合划分为 $b_{1}$ 个 1-子集，$b_{2}$ 个 2-子集，以此类推，最后是 $b_{k}$ 个 k-子集。其中 $\sum\limits_{i=1}\limits^{k}ib_{i}=n$，问有多少种划分方法。

思路1-排列数

从排列数出发，n 元素的全排列个数为 $n!$。对每个划分，其中 $b_{i}$ 个 i-子集是没有顺序的，划分中的每个元素也是没有顺序的，因此每个划分对应 $b_{1}!b_{2}!\cdots b_{k}!(1!)^{b_{1}}(2!)^{b_{2}}\cdots(k!)^{b_{k}}$ 个不同的排列。因此答案为：

$$\frac{n!}{b_{1}!b_{2}!\cdots b_{k}!(1!)^{b_{1}}(2!)^{b_{2}}\cdots(k!)^{b_{k}}}$$

思路2-多重组合

因为划分得到的 i-子集之间没有顺序，可以直接从多重组合出发，结果如下：

$$\frac{\binom{n}{1,\cdots,1,2,\cdots,2,\cdots,k,\cdots,k}}{b_{1}!b_{2}!\cdots b_{k}!} \\ = \frac{n!}{b_{1}!b_{2}!\cdots b_{k}!(1!)^{b_{1}}(2!)^{b_{2}}\cdots(k!)^{b_{k}}}$$

结论

一个 n-集合的全体划分数为：

$$\sum\limits_{\sum\limits_{i=1}\limits^{n}ib_{i}=n}\frac{n!}{b_{1}!b_{2}!\cdots b_{n}!(1!)^{b_{1}}(2!)^{b_{2}}\cdots(n!)^{b_{n}}}$$

n元对称群中特定轮换型号的置换个数

记集合 $[n] = \{1,2,\cdots,n\}$，$[n]$ 到其自身的双射，即 n 元置换在全体映射合成下构成一个群，记n元对称群$S_{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$ 的轮换型号，记为 $type(\sigma)$。

若 $\sum\limits_{i=1}\limits^{n}il_{i}=n$，则 $S_{n}$ 中轮换型号为 $(l_{1}, l_{2}, \cdots, l_{n})$ 的置换有多少个。

思路

基于前面 n-集合的划分数的结论，把 $[n]$ 分成 $l_{1}$ 个 1-子集、$l_{2}$ 个 2-子集，…，$l_{n}$ 个 n-子集的分法数为：

$$\frac{n!}{l_{1}!l_{2}!\cdots l_{n}!(1!)^{l_{1}}(2!)^{l_{2}}\cdots(n!)^{l_{n}}}$$

因为同样大小的子集在它们自身内可以任意置换也不改变这个组态，而在每个 t-子集中可形成 $(t-1)!$ 个轮换，所以型号为 $(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\limits_{i=1}\limits^{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公式)

在 n 元对称群中，型号为 $type(\sigma) = (l_{1}, l_{2}, \cdots, l_{n})$ 的置换 $\sigma$ 个数为：

$$\frac{n!}{l_{1}!l_{2}!\cdots l_{n}!1^{l_{1}}2^{l_{2}}\cdots n^{l_{n}}}$$

---