幂集合中所有集合排列的数目是多少？ [英] What is the number of all set permutations in a power set?

问题描述

对于大小为 n 的集合，其幂集的大小为 2 ^ n 。为功率集的每个元素生成所有排列。集合 {a，b} 的幂集为 {{}，{a}，{b}，{a，b}} 。在每个集合上生成所有排列，我们可以得到 {（），（a），（b），（a，b），（b，a）} 。因此，由2个元素集生成的幂集的所有子集置换的数目为5。而对于3个元素集，此数的数目为16。是否有根据 n ？

For a set of size n, the size of its power set is 2^n. Generate all permutations for each element of the power set. The power set for set {a, b} is {{}, {a}, {b}, {a,b}}. Generate all permutations on each set, we can get {(),(a),(b),(a,b),(b,a)}. So the number of all subset permutation for a power set generated from a 2-element set is 5. And such a number for a 3-item set is 16. Is there a formula for this number defined in terms of n?

推荐答案

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

First of all, consider the power set. The number of sets of size k (for some 0 <= k <= n) in the power set is

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

的确，如果我们将集合数加起来对于所有 k ，我们得到 2 ^ n ，请参阅 Wolfram Alpha 。

Indeed, if we sum the number of sets for all k, we get 2^n, see Wolfram Alpha.

一组大小为 k 的排列有多少个排列？好吧， k！。因此，如果将其插入，我们将从分母中删除 k！并求和 n！ /（nk）！表示所有 k ，即

How many permutations does a set of size k have? Well, k!. So, if we plug that in, we loose the k! from the denominator and sum n! / (n-k)! for all k, which is

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

再次参见 Wolfram Alpha 。

这篇关于幂集合中所有集合排列的数目是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！