求覆盖全部n个元素的无序子集集合的组合数及子集总数

咱们来好好拆解这个问题，它其实和数学里的集合划分、贝尔数概念完全对应，很容易就能找到规律：

问题明确 #

给定n个元素，我们要计算两个核心值：

• f(n)：所有覆盖全部元素的无序子集集合的数量。简单说就是，把这n个元素拆成若干非空子集（子集之间不交，合起来是全集），而且这些子集的组合是无序的（比如{A, BC}和{BC, A}算同一个）。
• g(n)：把所有符合条件的子集集合里的子集个数加起来的总和。

例子验证（n=3） #

当元素是A、B、C时，符合要求的子集集合有5个：

• {A, B, C}（包含3个子集）
• {A, BC}（包含2个子集）
• {AC, B}（包含2个子集）
• {AB, C}（包含2个子集）
• {ABC}（包含1个子集）
  所以：
• f(3) = 5
• g(3) = 3 + 2 + 2 + 2 + 1 = 10，和你给出的例子完全一致。

核心结论与推导 #

1. 关于f(n)：就是第n个贝尔数 #

f(n)对应的数学概念是n个元素的集合划分个数，也就是贝尔数（Bell Number），记为B_n。

贝尔数的定义就是：将n个元素的集合拆分成非空不交子集的方式数，正好和我们的f(n)要求完全匹配。

贝尔数的递推公式：

B_{n+1} = sum_{k=0}^n C(n, k) * B_k

其中初始值B_0 = 1（空集的划分只有1种，就是空集合）。

比如：

• B_1 = 1，对应{A}这1种划分
• B_2 = 2，对应{A,B}和{AB}两种划分
• B_3 = 5，正好和n=3的例子对应。

2. 关于g(n)：贝尔数的差分 #

g(n)可以通过贝尔数的差值来计算，公式是：

g(n) = B_{n+1} - B_n

为什么？我们可以换个角度想：每个符合条件的子集集合本质是一个集合划分，统计所有划分里的子集总数，等价于统计每个非空子集在多少个划分里出现，再把这些数量加起来。

对于一个大小为k的子集，它能出现在B_{n-k}个划分里（剩下的n-k个元素可以任意划分，这个子集作为其中一部分加入即可）。把所有大小的子集贡献加起来，结合贝尔数的递推公式，就能推导出g(n) = B_{n+1} - B_n这个简洁结论。

验证一下：

• n=2时，B_3=5，B_2=2，5-2=3，正好是g(2)=2+1=3
• n=1时，B_2=2，B_1=1，2-1=1，完全正确。

数值对照表 #

内容的提问来源于stack exchange，提问作者Aart Stuurman