How to calculate the number of all combinations of all permutations?

Question

I have a set n with m elements. I aim for the number of all combinations of all permutations of all elements of the set.

An minimal example would be with a two element set [1,2]:

All permutations of all combinations: [1] [2] [2,1] [1,2]

I know the number gets huge with only a little number of elements in the set. At 10 elements its over 100 000 possibilities.

But how to calculate how many there are?

Answer 1

If your set has $m$ elements, then:

• we have $m$ one-element subsets, each of which contributes a single permutation
• we have ${m\choose 2}$ two-element subsets, each of which contributes $2$ permutations
• we have ${m \choose 3}$ three-element subsets, each of which contributes $3!=6$ permutations
• and so forth.

So we sum over all possible cardinalities of subsets ($k=1, \dots, m$) to obtain:

$$\begin{align*}\sum_{k=1}^m{m\choose k}k! = & \sum_{k=1}^m \frac{m!}{(m-k)!k!}k! \\ = & \sum_{k=1}^m \frac{m!}{(m-k)!} \\ = & \sum_{k=0}^m \frac{m!}{(m-k)!} -1\\ = & \sum_{j=0}^m \frac{m!}{j!} -1\\ = & e\Gamma(m+1,1) -1\\ = & \lfloor m!e\rfloor-1 \end{align*}$$

The last two identities are equations (35) and (36) in the Wolfram page on Binomial Sums (and called "another interesting sum", which I fully agree with). This is almost OEIS series A000522 "Total number of arrangements of a set with n elements" - "almost", since you don't seem to want to count the single permutation contributed by the empty subset, which accounts for the $-1$ term above.

Answer 2

Perhaps it's easier to see the combinations in a geometric arrangement. There are m elements in the set. For simplicity, my example will use the set ${1, 2, 3, 4}$, so $m=4$.

Sampling a times with replacement, where order is important: $(m)^a$

(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)
(4,1) (4,2) (4,3) (4,4)

Sampling a times with replacement, order not important: $\frac {m(m+1)} {2}$

(1,1) (1,2) (1,3) (1,4)
      (2,2) (2,3) (2,4)
            (3,3) (3,4)
                  (4,4)

Sampling a times without replacement, order important: m permute a = $\frac {m!} {(m-a)!}$

      (1,2) (1,3) (1,4)
(2,1)       (2,3) (2,4)
(3,1) (3,2)       (3,4)
(4,1) (4,2) (4,3) 

Sampling a times without replacement, order not important: m choose a = $ \binom n a = \frac {m!} {a!(m-a)!}$

      (1,2) (1,3) (1,4)
            (2,3) (2,4)
                  (3,4)