多重集

定义

多重集（multiset）是一种元素可以重复出现的无序汇集，即集合概念的推广。在普通集合中，同一个元素只会出现一次，只能表达“有”或“无”；在多重集中，同一个元素可以出现任意多次。例如由 5 个 a、3 个 b、1 个 c、2 个 d 组成的多重集可写作 {a, a, a, a, a, b, b, b, c, d, d}^[1]。这一概念在不同文献中也被称为重集或包（bag）、mset^[1]。

刻画多重集的关键量是重数，即某个元素在多重集中出现的次数，通常记为 $\nu(m)$。重数函数可以看作集合的特征函数向多重集的推广，所有重数中的最大值称为该多重集的高^[2]。重数为 0 的元素视为不属于该多重集，所有重数非零的元素构成多重集的支撑集。

按定义，多重集的有序性被排除在外：{a, a, b} 与 {a, b, a} 表示同一个多重集^[3]。因此，多重集与允许重复且讲求次序的列表（元组）是两类不同的结构。

多重集的势（总元素个数）按重数累加计算，即 $\#M=\sum_{m\in M}\nu(m)$。若各重数均有限，其势为非负整数；若不同元素只有有限个而某些重数无限，则势可取超限基数^[4]。支撑集的大小有时被称为多重集的维数。

若把所有重数推广到整数乃至实数，可得到符号多重集与加权集等更一般的对象，前者允许元素带有负的重数^[2]。

原理

从形式化角度看，多重集可以定义为一个二元组 $(A,m)$：$A$ 是一个可数集合，称为底集或论域；$m$ 是从 $A$ 到非负整数的映射，称为重数函数。若要求 $m$ 的取值均为自然数，所得对象称为自然多重集^[5]。支撑集则是使重数函数不为零的那些元素组成的集合。

在这种表示下，集合上的基本关系与运算都可以逐点搬移过来。包含关系 $\mathfrak{A}\subseteq\mathfrak{B}$ 成立，当且仅当对每个元素 $x$ 都有 $m_{\mathfrak{A}}(x)\le m_{\mathfrak{B}}(x)$；并集与交集分别按重数相加、取小来定义，差集则按重数相减^[6]。它们对应的公式为：并 $m(v)=m_1(v)+m_2(v)$，交 $m(v)=\min\{m_1(v),m_2(v)\}$。

组合计数是多重集理论中最常用的部分。从 $n$ 类元素中可重复地取出 $k$ 个元素且不计顺序，所得多重集的个数为 $\binom{n+k-1}{k}$。这一结果可用“隔板法”（也称星与棒法）推出：把 $k$ 个球排成一行，再用 $n-1$ 块隔板分成 $n$ 段，方案数即为从 $n+k-1$ 个位置中选出 $k$ 个放置球的方法数^[7]。等价地，它也等于线性方程 $x_1+x_2+\cdots+x_n=k$ 的非负整数解个数。

多重集的排列则涉及不同重数之间的重复抵消。对重数分别为 $t_1,t_2,\dots,t_n$、总数为 $N$ 的多重集，其全排列数为 $\dfrac{N!}{t_1!\,t_2!\cdots t_n!}$，因为同一元素的各次出现彼此不可区分。

发展历程

虽然“多重集”这一术语出现很晚，但相关思想十分古老。唐纳德·克努特认为，对多重集排列的最早研究可追溯到印度数学家婆什迦罗，他在约 1150 年描述过多重集的排列问题；韦恩·布利泽德更进一步把多重集的源头追到数的起源，认为古人用若干笔画或刻痕表示数目 $n$，这些彼此不可区分的刻痕本身就是一种多重集^[8]。

multiset 一词由荷兰数学家尼古拉斯·霍弗特·德布鲁因在 20 世纪 70 年代创造，据克努特的记述，正式的多重集概念也大约形成于这一时期^[8][9]。此前此后，学者们还使用过 list、bunch、bag、heap、sample、weighted set、collection、suite 等多种名称来指称同一构造^[8]。

20 世纪后半叶，多重集的逻辑与历史基础得到系统梳理。布利泽德从逻辑与历史角度考察了这一构造，西罗普洛斯则撰写了关于多重集数学的综述^[10]。与此同时，把重数取值放宽到整数、实数乃至模糊数的各种推广形式也相继提出，包括韦特尼在 1933 年借助特征函数提出的混合集思想^[10]。

应用

在组合数学与初等计数中，多重集是处理“可重复组合”问题的标准语言。从 $n$ 个不同元素中每次取 $r$ 个、允许重复且不计顺序的方案，就对应一个多重集，其总数可由前述隔板法公式给出^[11]。整数分拆、多项式系数、素数分解中重复因子的统计等问题，也都可以用多重集描述^[1]。

在计算机科学中，多重集常被称为包，它允许元素重复但不保证次序。C++ 标准模板库中的 std::multiset 是有序容器，支持插入、删除、查找与计数，其中 count 操作返回某元素出现的次数^[3]。Java 的 Guava 库提供 Multiset 接口，行为类似映射，可自动维护各元素的计数，常用于词频统计等需要记录元素出现频次的场景^[3]。

在数值计算与统计学中，多重集也有具体用途。GNU 科学计算库用多重集表示从 $n$ 维向量中可重复选取的 $k$ 个下标，便于遍历 $k$ 阶对称张量的分量。统计学中的多重集典型相关分析及其二维鉴别型等变体，则以多重集思想处理多组数据集之间的相关关系^[3]。

局限

多重集只保留“有哪些元素、各出现几次”这一层信息，其余结构一概舍弃。元素之间的次序、来源与相互关联都无法表达，因此凡涉及顺序或位置关系的问题，必须改用序列、元组或列表来刻画^[3]。

基本重数取非负整数的约定也限制了表达能力。当需要表示“欠账”式的关系或连续权重时，普通多重集不够用，须求助于允许负重数的符号多重集或将重数取为实数的加权集；这些推广虽已提出，但其运算性质与计数公式并不自动继承自经典理论^[2]。

在可计算层面，多重集的许多操作存在效率约束。以有序多重集容器为例，统计某元素出现次数的操作在常见实现中耗时与“对数规模加该元素出现次数”相关，元素大量重复时开销随之上升^[3]。此外，不同文献对重数是否允许为 0、是否允许无限重数并无统一约定，这也给跨文献的比较与引用带来不便^[2]。

参见

• 集合 —— 多重集所推广的基础概念，同一元素在其中至多出现 1 次。

• 组合 —— 从给定对象中选取若干对象的计数问题，可重复组合与多重集直接对应。

• 排列 —— 讲求次序的安排方式，多重集的全排列数需按重数作重复折算。

• 映射 —— 多重集可等价地由底集到非负整数的重数函数来定义。

• C++标准模板库 —— 提供 std::multiset 有序容器的程序设计库。