algorithm - 幂集中所有集合排列的数量是多少？

Question

对于一组大小n，其幂集的大小为2^n。为幂集的每个元素生成所有排列。set 的幂集{a, b}为{{}, {a}, {b}, {a,b}}。在每个集合上生成所有排列，我们可以得到{(),(a),(b),(a,b),(b,a)}. 因此，从 2 元素集生成的幂集的所有子集排列的数量是 5。对于 3 项集，这样的数字是 16。这个数字有公式n吗？

Answer 1

首先，考虑功率组。幂集中的大小组数k（对于某些0 <= k <= n）是

n choose k = n! / (k! * (n - k)!)

事实上，如果我们将所有 的集合数相加k，我们会得到2^n，参见Wolfram Alpha。

一组大小k有多少个排列？嗯，k!。因此，如果我们将其插入，我们会k!从分母中松开 并n! / (n-k)!为所有求和k，即

n! * Sum(1/k!, 0 <= k <= n)

再次查看Wolfram Alpha的结果。