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

Question

对于大小为 n 的集合，其幂集的大小为 2^n。为幂集的每个元素生成所有排列。集合 {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 查看结果.