Intuitive understanding of the formula $\frac{(m+n+p)!}{m!n!p!}$ for dividing $m+n+p$ things into three groups of sizes $m,n$ and $p$

Question

The number of ways in which $m+n+p$ things can be divided into three unequal groups containing $m,n$ and $p$ things is $\dfrac{(m+n+p)!}{m!n!p!}$

I need help understanding this formula intuitively and its proof. Moreover, I don't get why this formula has no multiplication by $3!$ since there are $3!$ permutations of those 3 groups possible.

Answer 1

@Useless has given a good explanation. Here is another way to arrive at the same expression using binomial coefficients.

You can choose $m$ objects from $m+n+p$ in ${m+n+p \choose m}$ ways. After choosing $m$ objects, you are left with $n + p$ objects, out of which you need to choose $n$ objects, which can be done in $n+p \choose n$ ways. Now, you are left with $p$ objects out of which you need to choose $p$ objects which can be done in $p \choose p$ ways. So the total number of ways of choosing is

$$ {m+n+p \choose m}{n+p \choose n}{p \choose p} = \cfrac{(m+n+p)!}{(n+p)!m!}\cfrac{(n+p)!}{n!p!}\cfrac{p!}{p!0!} = \cfrac{(m+n+p)!}{m!n!p!} $$

Regarding the part of your question as to why there is no multiplication by $3!$: permutation of the partitions will give the same configuration, ie., if we partition the objects in this way: $(a_1, a_2, \dots, a_m), (b_1, b_2, \dots, b_n), (c_1, c_2, \dots, c_p)$, then it is identical to this configuration: $(b_1, b_2, \dots, b_n), (a_1, a_2, \dots, a_m), (c_1, c_2, \dots, c_p)$.

NOTE: This expression works only when $n \neq m \neq p$. In case, any 2 of $m, n, p$ are equal, say, $m = n \neq p$, then you need to divide the expression by $2!$ because each configuration would appear twice. Similarly, if $m = n = p$, you need to divide by $3!$, since the 3 partitions can be permuted to arrive at the same configuration.

In an older answer, I gave a general formula for partitioning a set, I will just copy it here:

Suppose we wish to partition a set of $N$ elements into $m_1$ partitions of $n_1$ elements in each, $m_2$ partitions of $n_2$ elements in each, ..., $m_k$ partitions of $n_k$ elements in each, such that, $N = m_1 n_1 + m_2 n_2 + ... + m_k n_k$ Then, the number of ways to achieve this is

$$ \cfrac{N!}{(m_1!m_2!\dots m_k!)((n_1!)^{m_1} (n_2!)^{m_2} \dots (n_k!)^{m_k})} $$

We divide by $\Pi (n_i!)^{m_i}$ because elements of each partitions can be permuted among themselves to arrive at the same configuration (and there are $m_i$ partitions of size $n_i$), and we divide by $\Pi m_i!$ partition of similar sizes can be permuted to arrive at the same configuration.

Answer 2

Maybe this can provide some intuition:

$(m+n+p)!$ is the number of ways we can arrange the $m+n+p$ objects in a row. Now let's arbitrarily dictate that the first $m$ objects will go in one group, the next $n$ objects will go in the second group, and the remaining $p$ objects will be in the last group.

We now need to divide by $m!$ to account for rearrangements of the first group, which has $m$ objects, $n!$ to account for rearrangements of the second group, and $p!$ to account for rearrangements of the third group.

Answer 3

Since all group sizes occur only once, they can be thought of as indices of the groups, i.e. instead of ordering groups by $1,2,3$, we can order them by their sizes $m,n,p$, say, in nondecreasing order, and the identification is unique. If some group sizes occurred more than once, those groups could be permuted, and we would need to divide by more factors than those in your question.

In general, suppose we divide the set of $N$ elements into groups, where the multiset of sizes is $S=\{s_1^{r_1},\dots,s_k^{r_k}\}$ (i.e. each distinct size $s_i$ occurs $r_i>0$ times), so $N=\sum_{i=1}^{k}{s_ir_i}$.

Given a list of those $N$ elements, they can be permuted in $N!$ ways. For each way of partitioning this set of $N$ elements into subsets with the multiset of sizes given by $S$, some permutations preserve the size of the part to which each element belongs. Such permutations are those that can do only two things:

• permute elements within each part,
• permute parts of equal sizes.

Elements in a part of size $s_i$ can be permuted in $s_i!$ ways. The $r_i$ parts of the same size $s_i$ can be permuted in $r_i!$ ways. Thus, the number of distinct partitions of $N$ elements into parts with the multiset of sizes $S=\{s_1^{r_1},\dots,s_k^{r_k}\}$ is $$ \frac{N!}{\prod_{i=1}^{k}{\Bigl(\left(s_i!\right)^{r_i}r_i!\Bigr)}}. $$ In our case, $k=3$, $s_1=m$, $s_2=n$, $s_3=p$, $r_1=r_2=r_3=1$, since all $m,n,p$ are distinct.