Number of subset-permutations for a set

Question

Suppose you have a set {a, b, c}.

There are 3! = 6 permutations.

Subsets {a, b}, {a, c}, and {b, c} will account for 3 * 2! = 6 permutations.

Subsets {a}, {b} and {c} accounts for 3 * 1! = 3 permutations.

Subset {} accounts for 0! = 1 permutation.

So {1, 2, 3} has 6 + 6 + 3 + 1 = 16 subset-permutations.

How do I generalize this to a formula for a set of length n? I figure we need to sum with i from 1 up to n, and include i! in the sum body. But I can't figure out how to write it down!

It should be $\sum \limits_{i=0}^n i!{n\choose i}$. I don't know whether you can simplify the formula. — Jack Yoon, May 29 '14 at 11:35
Ah yes that is correct and I understand! Thank you so much. Why don't you promote this comment to an answer? — Marty, May 29 '14 at 11:38

score 5 · Accepted Answer · answered May 29 '14 at 11:42

5

It should be $\sum\limits_{i=1}^n i!{n\choose i}$.

answered May 29 '14 at 11:42

Jack Yoon

1,466

2

And note that $\binom{n}{i}=\frac{n!}{i!(n-i)!}$. – mathse May 29 '14 at 11:43

score 2 · Answer 2 · edited Apr 13 '17 at 12:21

One useful (and lazy) way to find out more about about a series is to use OEIS to look it up from the first couple terms. In this case, our series is "number of permutations of subsets of $n$ elements". You could calculate the first couple terms by hand. Another option is to write a program, like this Haskell I cribbed from OIES:

import Data.List
subsetPerms setSize = length $ concatMap permutations $ subsequences [0 .. setSize]
map subsetPerms [0 .. 5]

This shows that the first terms are $2,5,16,65,326,1957$. (Note that in Haskell, the range [0 .. n] is inclusive, so the first term it prints is finding subset-permutations of the set $\{ 0 \}$ instead of subset-permutations of the empty set.) Then, paste it into OEIS's search box and we find it's A000522 "Total number of arrangements of a set with n elements: a(n) = Sum_{k=0..n} n!/k!."

There are a couple formulas listed.

One is the simple formula Jack Yoon's answer: $a(n) = Sum_{k=0..n} binomial(n,k) * k!$ (which is described as "interpretation: for all k-subsets (sum), choose a subset (binomial(n,k)), and permutation of subset (k!). - Joerg Arndt, Dec 09 2012")

Another is the expanded version $a(n) = Sum_{k=0..n} n!/k!$ in the sequence's title.

A third is a recurrence relation: $a(n) = n*a(n-1) + 1, a(0) = 1$

Finally, a particularly neat closed form: $a(0) = 1$; for $n > 0$, $a(n) = floor(e*n!)$

I know this is an old post, but I was asking the same question, so when I found this thread, I put the formula in Wolframalpha. It gave $$e\Gamma(n+1,1)$$ where $\Gamma$ is the incomplete Gamma function. — SlipEternal, Apr 02 '19 at 13:31

Number of subset-permutations for a set

2 Answers2