1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I'd recommend writing out all possible combinations of sets of 3 and 4. You'll see a pattern when you write it out in a systematic way. Then you can generalize. Think about using factorials and combinations (i.e. choose notation). $\endgroup$
    – ilanman
    Oct 8, 2016 at 18:24

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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