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!

Answer 1

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

Answer 2

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