0
$\begingroup$

The number of combinations $n$ from $M$ components to be grouped to two different groups can be calculated by equation below:

$$n = 2^{M-1} - 1$$

Can anybody provide the mathematical proof of this?

As an example, there are $n = 3$ from $M = 3$ to be grouped into two different groups, there are $n = 15$ from $M = 5$ to be grouped into two different groups, so on and so forth.

Thank you.

$\endgroup$

2 Answers 2

2
$\begingroup$

For every subset of a set $\mathcal{M}$ with $M$ elements except for $\emptyset$ and $\mathcal{M}$ one gets a partition with two nonempty sets, and there are $2^M-2$ such subsets. Since every (non-ordered) parttition is counted twice in this way You divide by 2 to obtain

$n=2^{M-1}-1$.

$\endgroup$
0
$\begingroup$

What Melech said is correct, but I think the heart of the matter is why there are $2^M$ subsets of a set of size M. That can be seen as follows. Firstly there are $M \choose K $ subsets of size K. So one needs to calculate $ \sum_{K=0}^{K=M} {M\choose K}$. But, by the binomial theorem, this is just $ (1+1)^M = 2^M$ . Now insert what Melech said.

$\endgroup$
1
  • $\begingroup$ This is correct, but a very roundabout way to show that an $M$ element set has $2^M$ subsets. Just note that each element is in or out half the time and that these choices are independent. $\endgroup$ Nov 15, 2016 at 13:25

You must log in to answer this question.