3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ So are you purposely missing out empty set? $\endgroup$ – Jack Yoon May 29 '14 at 11:29
  • $\begingroup$ Oh! Forgot about that. $\endgroup$ – Marty May 29 '14 at 11:30
  • $\begingroup$ Sorry, I'm such a math dope! $\endgroup$ – Marty May 29 '14 at 11:32
  • 1
    $\begingroup$ It should be $\sum \limits_{i=0}^n i!{n\choose i}$. I don't know whether you can simplify the formula. $\endgroup$ – Jack Yoon May 29 '14 at 11:35
  • $\begingroup$ Ah yes that is correct and I understand! Thank you so much. Why don't you promote this comment to an answer? $\endgroup$ – Marty May 29 '14 at 11:38
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – InterstellarProbe Apr 2 at 13:31
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.