一、多重集合的核心概念
多重集合（Multiset）是集合概念的推广，允许元素重复出现，其核心特征是元素的重数（Multiplicity）——即元素在集合中出现的次数。与普通集合（元素互异）不同，多重集合中的元素可重复，但元素顺序无关（即{a,a,b}与{a,b,a}视为同一多重集合）。
1. 形式化定义
多重集合通常表示为M={k1⋅a1,k2⋅a2,…,kn⋅an}，其中：
- a1,a2,…,an是互异元素（不同类型）；
- k1,k2,…,kn是重数（非负整数，表示该元素的出现次数）；
- 多重集合的势（Size）是所有重数之和，即∣M∣=k1+k2+⋯+kn（例如M={3⋅a,2⋅b}的势为3+2=5）。
2. 与普通集合的区别
| 特征 | 普通集合 | 多重集合 |
|---|---|---|
| 元素互异性 | 是（元素唯一） | 否（元素可重复） |
| 表示符号 | 花括号{} | 花括号或方括号[\] |
| 势的计算 | 元素个数（不计重复） | 重数之和（计重复） |
3. 相等性判断
两个多重集合相等当且仅当元素类型及对应重数完全一致（与顺序无关）。例如M1={2⋅a,1⋅b}与M2={1⋅b,2⋅a}相等，但与M3={3⋅a}不等。
二、多重集合的重点知识
多重集合的核心问题是计数（排列与组合），以下是关键结论与应用：
1. 多重集合的排列
排列是指从多重集合中选取若干元素并按顺序排列的不同方式，分为两类：
（1）全排列（r=∣M∣）
当选取所有元素排列时，排列数为：
k1!⋅k2!⋅⋯⋅kn!∣M∣!
其中∣M∣=k1+k2+⋯+kn（总元素数），分母是各元素重数的阶乘（消除重复排列）。
例子：单词“MISSISSIPPI”的字母排列数为1!⋅4!⋅4!⋅2!11!=34650（M=11，kM=1,kI=4,kS=4,kP=2）。
（2）r排列（r≤∣M∣）
当选取r个元素排列时，需考虑元素重数的限制，通常通过分类讨论或生成函数求解：
- 无限制情况：若每种元素的重数足够大（≥r），则排列数为kr（k为元素类型数）；
- 有限制情况：需枚举所有可能的重数组合，计算每种组合的排列数再求和。 例子：多重集合M={3⋅a,2⋅b,4⋅c}的8排列数为：
2!⋅2!⋅4!8!+3!⋅1!⋅4!8!+3!⋅2!⋅3!8!=420+280+560=1260
（分别对应a取2、3、3个的情况）。
2. 多重集合的组合
组合是指从多重集合中选取若干元素（不考虑顺序）的不同方式，核心是隔板法（Stars and Bars）。
（1）无限制组合（每种元素可取0或多个）
从k种元素中选取r个的组合数为：
(rr+k−1)
推导：将r个元素视为“星”，用k−1个“隔板”分隔成k组（对应k种元素），总位置数为r+k−1，选择k−1个位置放隔板，故组合数为(k−1r+k−1)=(rr+k−1)。
例子：8种炸面包圈选12个的组合数为(1212+8−1)=(1219)=50388。
（2）有限制组合（每种元素有下界）
若每种元素ai至少取li个，可通过变量代换转化为无限制问题：令xi′=xi−li（xi′≥0），则原方程x1+x2+⋯+xk=r变为x1′+x2′+⋯+xk′=r−(l1+l2+⋯+lk)，组合数为：
(r−∑li(r−∑li)+k−1)
例子：方程x1+x2+x3+x4=20（x1≥3,x2≥1,x3≥0,x4≥5）的解数为：
(20−3−1−0−5(20−3−1−0−5)+4−1)=(1111+3)=(1114)=364
。
3. 多重集合的应用场景
- 计数问题：如字符串排列（含重复字符）、物品组合（如炸面包圈、礼物盒）；
- 组合数学：如多项式定理（展开式项数）、整数分拆（将数表示为若干数的和）；
- 计算机科学：如数据库中的多值属性（如用户的爱好列表）、算法中的频率统计（如词频计算）。
三、多重集合的学习方法
1. 夯实基础：理解概念与符号
- 区分概念：明确多重集合与普通集合的差异（重数、势的计算），避免混淆；
- 符号记忆：记住多重集合的表示形式（如{k1⋅a1,…}），理解重数的含义；
- 参考资料：阅读《组合数学》（Richard A. Brualdi）中的“多重集合”章节，或通过OI-wiki的“多重集合”专题（https://oi-wiki.org/math/multiset/）巩固基础。
2. 掌握核心：排列组合公式与应用
- 公式背诵：牢记全排列（k1!…kn!n!）、无限制组合（(rr+k−1)）、有限制组合（变量代换+隔板法）的公式；
- 例题练习：通过经典例题（如“MISSISSIPPI”的排列数、炸面包圈的组合数）加深对公式的理解；
- 生成函数：学习指数型母函数（用于排列问题）和普通型母函数（用于组合问题），解决复杂计数问题（如HDUOJ 1521“排列组合”题）。
3. 专项练习：从简单到复杂
- 入门题：
- 洛谷P1771“方程的解”（有限制组合问题，用隔板法）；
- LeetCode 62“不同路径”（多重集合排列的变形，用动态规划验证）。
- 进阶题：
- HDUOJ 1521“排列组合”（指数型母函数求多重集合排列数）；
- Codeforces 1335C“Social Distance”（多重集合组合的应用，用隔板法解决）。
- 难题：
- Project Euler 15“Lattice Paths”（多重集合排列的综合应用，用组合数学解决）；
- 《组合数学》中的“多重集合的排列与组合”习题（如习题3.1-3.5）。
4. 实践应用：联系实际问题
- 编程实现：用Python的
collections.Counter（统计元素频率）或C++的std::multiset（处理多重集合）实现计数功能； - 实际场景：尝试用多重集合解决生活中的问题（如统计班级同学的爱好分布、计算超市商品的组合方式）；
- 竞赛参与：参加算法竞赛（如ICPC、CCPC），接触更复杂的多重集合问题（如带限制的排列组合、生成函数应用）。
四、总结
多重集合的核心是处理重复元素的计数问题，关键在于掌握排列（全排列、r排列）与组合（无限制、有限制）的公式及应用。学习时需从基础概念入手，通过例题练习巩固公式，再通过专项练习提升解题能力。推荐的练习顺序是：概念理解→公式背诵→例题练习→专项题目→实际问题，最终实现“看到问题就能识别多重集合模型，并用正确公式计算”的目标。
如需进一步深入学习，可参考《组合数学》（Richard A. Brualdi）或《Introductory Combinatorics》（Richard A. Brualdi）中的相关章节，或通过在线平台（如Coursera的“Combinatorics”）学习更系统的组合数学知识。