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$

migrated from stats.stackexchange.com Nov 14 '16 at 15:43

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

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$
  • $\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$ – Ethan Bolker Nov 15 '16 at 13:25

Your Answer

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