关于满足子集元素互异条件的多重集划分计数公式的技术咨询

API 探路者

2026-4-23

嗨，我来帮你梳理这个问题的解法和对应的计数思路～

首先我们明确核心定义：

设集合 $S = {(s_1, f_1), (s_2, f_2), ..., (s_k, f_k)}$，其中每个 $f_i$ 代表元素 $s_i$ 在多重集 $T$ 中的重复次数，因此 $T$ 就是由 $f_1$ 个 $s_1$、$f_2$ 个 $s_2$……$f_k$ 个 $s_k$ 组成的多重集。
我们需要计数的是**$T$ 的合法划分方式数**，要求划分中的每个子集（片段）都是元素互异的集合——也就是说，任何一个子集里都不能出现重复的 $s_i$。

举个你给出的例子：当 $S = {(s_1, 1), (s_2, 2), (s_3, 1)}$ 时，$T = {s_1, s_2, s_2, s_3}$，符合条件的划分共有6种，分别是：

这个问题可以通过递归公式来直接计算，而且完全基于元素的频率 $f_1, f_2, ..., f_k$，具体如下：

设 $M(f_1, f_2, ..., f_k)$ 为我们要求的合法划分数目：

基准情况：当所有 $f_i = 0$（即空多重集）时，$M(0, 0, ..., 0) = 1$——只有一种空划分方式。
递归步骤：选取任意一个频率不为0的元素 $s_i$（当前频率为 $f_i$），则：
$$
M(f_1,...,f_i,...,f_k) = M(f_1,...,f_i-1,...,f_k) + \sum_{j \neq i} M(f_1,...,f_i-1,...,f_j-1,...,f_k)
$$

这个公式的逻辑很简单：我们考虑当前选取的那个 $s_i$ 副本所在的子集：

第一种情况：这个子集只包含这个 $s_i$ 副本，那么剩下的划分就是对“减少一个 $s_i$ 后的多重集”的合法划分，对应项 $M(f_1,...,f_i-1,...,f_k)$。
第二种情况：这个子集除了 $s_i$ 副本，还包含另一个元素 $s_j$ 的一个副本（$j \neq i$），此时我们同时减少一个 $s_i$ 和一个 $s_j$，对所有可能的 $s_j$ 求和，就得到这部分的划分数目。

用你给出的例子验证：
$M(1,2,1) = M(0,2,1) + M(0,1,1) + M(1,2,0)$

$M(0,2,1)$：对应多重集 ${s_2,s_2,s_3}$，合法划分有2种：${{s_2,s_3},{s_2}}$、${{s_2},{s_2},{s_3}}$
$M(0,1,1)$：对应多重集 ${s_2,s_3}$，合法划分有2种：${{s_2,s_3}}$、${{s_2},{s_3}}$
$M(1,2,0)$：对应多重集 ${s_1,s_2,s_2}$，合法划分有2种：${{s_1,s_2},{s_2}}$、${{s_1},{s_2},{s_2}}$

求和得 $2+2+2=6$，和例子中的结果完全一致。

对于小规模的频率组合，直接手动递归计算即可；如果是大规模的情况，可以用记忆化搜索或者动态规划来实现这个递归逻辑，避免重复计算相同的频率组合，提升效率。

备注：内容来源于stack exchange，提问作者AmirHosein Adavoudi