# The number of possibilities of $M$ objects to be grouped in $2$ different groups is $2^{M-1} - 1$

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.

## migrated from stats.stackexchange.comNov 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.

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