多重集排列数与组合数的关系

在组合数学中，我们经常遇到需要排列元素的问题。当所有元素都不同时，排列数是 $n!$。但当集合中包含重复元素时，我们就需要计算多重集排列数。有趣的是，这个计算可以巧妙地分解为一系列组合数（二项式系数）的乘积。

1. 多重集排列数 (Multinomial Coefficient)

假设有一个包含 N 个元素的多重集（multiset），其中：

• 有 $n_1$ 个类型 1 的元素
• 有 $n_2$ 个类型 2 的元素
• …
• 有 $n_r$ 个类型 r 的元素

并且所有元素的总数满足 $n_1 + n_2 + \dots + n_r = N$。

将这 N 个元素进行全排列，不同的排列总数（即多重集排列数）由以下公式给出：

$$\frac{N!}{n_1! n_2! \cdots n_r!}$$

这个公式也称为多项式系数，记作 $\binom{N}{n_1, n_2, \dots, n_r}$。

例子： 排列字母 “AABBC”
N=5, $n_A$=2, $n_B$=2, $n_C$=1。
排列数为 $\frac{5!}{2! 2! 1!} = \frac{120}{2 \times 2 \times 1} = 30$。

2. 组合数 (Binomial Coefficient)

组合数 $\binom{n}{k}$ (读作 “n 选 k”) 表示从 n 个不同的元素中无序地选取 k 个元素的方法数。其计算公式为：

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

例子： 从 {A, B, C, D} 中选 2 个字母
n=4, k=2。
组合数为 $\binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{24}{2 \times 2} = 6$。(AB, AC, AD, BC, BD, CD)

3. 两者关系：分解为顺序选择

我们可以将计算多重集排列数的过程看作是一系列选择位置的步骤，每一步都是一个组合问题：

想象我们有 N 个空位，需要将 $n_1$ 个类型 1、$n_2$ 个类型 2、…、$n_r$ 个类型 r 的元素放入这些空位。

1. 为类型 1 的元素选择位置：
   从 N 个空位中选择 $n_1$ 个位置放置类型 1 的元素。由于同类型元素不区分顺序，这是一个组合问题。选择方法数为：
   $$\binom{N}{n_1}$$

2. 为类型 2 的元素选择位置：
   现在还剩下 N - $n_1$ 个空位。从这些剩余空位中选择 $n_2$ 个位置放置类型 2 的元素。选择方法数为：
   $$\binom{N - n_1}{n_2}$$

3. 为类型 3 的元素选择位置：
   还剩下 N - $n_1$ - $n_2$ 个空位。从中选择 $n_3$ 个位置给类型 3 的元素。选择方法数为：
   $$\binom{N - n_1 - n_2}{n_3}$$

4. 依此类推…

5. 为类型 r 的元素选择位置：
   最后剩下 $N - n_1 - \dots - n_{r-1}$ 个空位，这正好等于 n_r。从中选择 n_r 个位置给类型 r 的元素。选择方法数为：
   $$\binom{N - n_1 - \dots - n_{r-1}}{n_r} = \binom{n_r}{n_r} = 1$$

由于每一步的选择是独立的，根据乘法原理，总的排列方法数是所有步骤选择数的乘积：

$$\binom{N}{n_1} \times \binom{N - n_1}{n_2} \times \binom{N - n_1 - n_2}{n_3} \times \cdots \times \binom{n_r}{n_r}$$

4. 数学验证

我们可以展开这个乘积中的组合数定义，看看它是否等于多重集排列数的公式。

我们从这个乘积开始：
$$\binom{N}{n_1} \times \binom{N - n_1}{n_2} \times \binom{N - n_1 - n_2}{n_3} \times \cdots \times \binom{n_r}{n_r}$$

展开每一项组合数的定义 ( \binom{n}{k} = \frac{n!}{k!(n-k)!} )：
$$= \frac{N!}{n_1!(N-n_1)!} \times \frac{(N-n_1)!}{n_2!(N-n_1-n_2)!} \times \frac{(N-n_1-n_2)!}{n_3!(N-n_1-n_2-n_3)!} \times \cdots \times \frac{n_r!}{n_r!0!}$$

观察这个长长的乘积，你会发现一个模式：前一项分母中的阶乘（例如 $(N-n_1)!$）会与紧邻的后一项分子中的阶乘完全相同，因此它们可以相互抵消。这种抵消会依次发生，直到最后。

经过所有中间项的抵消后，只剩下最开始的分子 $N!$ 和每一项分母中对应的 $n_i!$ 以及最后的 $0!$：

$$\frac{N!}{n_1! n_2! n_3! \cdots n_r! \times 0!}$$

因为 $0! = 1$，这正好等于多重集排列数的原始公式。

5. 结论

多重集排列数 $\frac{N!}{n_1! n_2! \cdots n_r!}$ 可以看作是一系列组合选择的结果。这种关系在推导、理解以及某些计算场景（例如结合阈值判断大组合数）下非常有用。它揭示了组合数学中不同概念之间的内在联系。

备注: 本来通过模运算来进行，但是发现被卡了，或者说本身模运算就存在这种问题。