多重集排列
Abstract
多重集排列（Permutation of Multiset）解决的是”当元素存在重复时，不同排列有多少种”的问题。其核心公式 是排列计数从”全不同”到”有重复”的自然推广，在概率论、统计学和编码理论中有广泛应用。
定义
多重集（Multiset）
多重集是集合的推广，允许同一元素出现多次。一个多重集可以表示为： 其中 是第 种不同元素， 是该元素的重数（出现次数），总元素数为 。
多重集排列数（Number of Permutations of a Multiset）
设多重集 包含 种不同元素，第 种元素有 个，总元素数 ，则 的所有不同排列的总数为：
该数也称为多项式系数（Multinomial Coefficient），记作 。
核心性质
| 编号 | 性质 | 公式 / 说明 |
|---|---|---|
| 1 | 退化到普通排列 | 当所有 （即 ）时，，退化为全排列 |
| 2 | 退化到可重排列 | 当只有1种元素（）时，，即只有一种排列 |
| 3 | 与二项式系数的关系 | 当 时，，即二项式系数 |
| 4 | 多项式定理 | 展开式中 的系数恰为 |
| 5 | 与可重排列的区别 | 可重排列中每类物体数量无限（排列数 ）；多重集排列中每类物体数量有限（由重数 决定） |
关系网络
graph TD A["多重集排列<br/>$\\frac{n!}{n_1! \\, n_2! \\cdots n_k!}$"] --> B["排列<br/>$n!$"] A --> C["二项式系数<br/>$\\binom{n}{r}$"] A --> D["可重排列<br/>$n^r$"] A --> E["多项式定理<br/>$(x_1+\\cdots+x_k)^n$"] B --> F["排列<br/>$P(n,r)$"] C --> G["组合<br/>$\\binom{n}{r}$"]
章节扩展
- 第6.5节：本概念是Rosen教材第6.5节的重要内容，与可重排列并列，分别处理”有限重复”和”无限重复”两种场景。
- 经典例题 — MISSISSIPPI：单词 MISSISSIPPI 中，M 出现1次，I 出现4次，S 出现4次，P 出现2次，总字母数 ，不同排列数为：
- 概率应用：在等概率假设下，从多重集中随机抽取一个排列，每种特定排列出现的概率为 。
补充
公式推导思路
若 个物体全不相同，则有 种排列。但由于第 种元素的 个个体不可区分，交换它们不产生新排列，因此需要除以 。对所有 种元素都做此修正，得到 。
多项式系数的递推关系
类似于二项式系数的帕斯卡恒等式，该递推关系体现了”第一步选择哪类元素”的思想。