What is the number of all set permutations in a po

问题:

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?

回答1:

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)!)

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

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)

Again, see the result by Wolfram Alpha.