3
$\begingroup$

I had a question that seems pretty straightforward, but I can't seem to wrap my mind around it.

Let's say I have a bunch of elements in a set. {A, B, C, D, E}.

How many permutations are there of every subset of this set? For example, I want to come up with every permutation of these elements that uses all possible elements, as well as all possible subsets of all the elements.

My guess is that we have 5! permutations to use all elements, 4! permutations to use a set of 4, which there are 5 of, 3! permutations to use a set of 3, which there are (5 * 4) of, 2! permutations to use a set of 2, which there are (5 * 4 * 3) of, and 1! permutations to use a set of 1, which there are (5 * 4 * 3 * 2) of.

Mathematically, how can this expression be generalized to a set of size n?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ The method is not quite right. For example, for sets of $3$, there are $\binom{5}{3}$ ways to choose the elements, and then they can be permuted in $3!$ ways, so the contribution is $\binom{5}{3}3!$, half of what you wrote. $\endgroup$ – André Nicolas Jul 30 '15 at 15:33
6
$\begingroup$

The number of permutations of every subset of a set of size $n$ is $\lfloor n!e\rfloor$. This is because $$ \sum_{k=0}^n\underbrace{\binom{n}{k}}_{\substack{\text{number of}\\\text{subsets of}\\\text{size $k$}}}\underbrace{k!\vphantom{\binom{n}{k}}}_{\substack{\text{number of}\\\text{permutations}\\\text{on a subset}\\\text{of size $k$}}} =\sum_{k=0}^n\frac{n!}{(n-k)!} =\sum_{k=0}^n\frac{n!}{k!} =\lfloor n!e\rfloor $$

$\endgroup$
  • $\begingroup$ So if we were to use big-O notation for this, it would be O(n!) ? $\endgroup$ – jj172 Jul 30 '15 at 15:42
  • 1
    $\begingroup$ It would be, but it is more precise than that, we have $$n!e-\frac1n\le\lfloor n!e\rfloor\le n!e$$ $\endgroup$ – robjohn Jul 30 '15 at 15:48
0
$\begingroup$

No, you have $5!$ permutations of $5$ elements, but for $3$ elements there are $5 \cdot 4 \cdot 3=\frac {5!}{(5-2)!}$ permutations. You have five choices for the first one, four choices (because you have used one) for the second and three for the third. Another way to look at it is that you have $5 \choose 3$ ways to select the three elements and then $3!$ ways to arrange the ones you have selected. And ${5 \choose 3}3!=\frac {5!}{(5-3)!3!}3!=\frac {5!}{(5-3)!}$ as it should.

More generally, the number of permutaions of $k$ elements from a set of size $n$ is $\frac {n!}{(n-k)!}$ You are looking for k-pemutations of n.

$\endgroup$
0
$\begingroup$

Your guess is not quite correct after the first two terms.

It should be $^5P_5$ + $^5P_4$ + $^5P_3$ + $^5P2$ + $^5P1$ +$^5P_0$

Generalizing for n terms, $\sum _0^n {^n P_k}$,

or if you so prefer, $\sum_0^n{n\choose k}\cdot k!$

$\endgroup$

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.