# Number of ways of dividing a set into a set of sets

This is really two related questions. First, it seems to me that given a set of $n$ objects you can divide it into a set of subsets of $a_1$ sets containing $n_1$ objects, $a_2$ sets containing $n_2$ objects and so on such that $a_1\cdot n_1 + a_2\cdot n_2 + \cdots + a_m\cdot n_m = n$ in the following way:

$$\frac{\binom{n}{n_1}\cdot\binom{n-n_1}{n_1}\cdots\binom{n-(a_1-1)n_1}{n_1}\cdot\binom{n-a_1n_1}{n_2}\cdots\binom{n-a_1n_1-(a_2-1)n_2}{n_2}\cdots\binom{n-a_1n_1-a_2n_2\cdots}{n_m}}{a_1!a_2!\cdots a_m!}$$

An example of this would be to divide a set of 13 distinct objects into 2 sets of 2 object and 3 sets of 3:

$$\frac{\binom{13}{2}\binom{11}{2}\binom{9}{3}\binom{6}{3}\binom{3}{3}}{2!3!}$$

However, deriving from another question in my book there seems to be another general formula for calculating this whose combinatoric explanation I don't really understand:

$$\frac{n!}{a_1!a_2!\cdots a_m!(n_1 !)^{a_1} \cdot (n_2 !)^{a_2} \cdots (n_m !)^{a_m}}$$

Based on my above example I would get:

$$\frac{13!}{2!(2!)^2 3!(3!)^3}$$

First is this general formula right and if so how do you explain it?

I hope the explanation to the first part is clear.

-
In the second term of you first formula is it $\binom{n-n_1}{n_1}$ or $\binom{n-a_1n_1}{n_1}$?? – Ramana Venkata Dec 23 '11 at 6:29
I mean the first. – Robert S. Barnes Dec 23 '11 at 7:23
@Robert S. Barnes : in $\binom{n}{n_1}\cdot\binom{n-n_1}{n_1}\cdot\dots\cdot\binom{n-a_1n_1-a_2n_2\dots‌​}{n_m}$ the sequence is not clear, would you please add more terms to clarify the sequence? – palio Dec 23 '11 at 7:55
@palio Hope it's clearer now. – Robert S. Barnes Dec 23 '11 at 11:35
I added a concrete example to try and make the question more clear. – Robert S. Barnes Dec 23 '11 at 11:44

Your first formula, though not quite given in full detail, is correct if one makes a reasonable interpretation of what you mean by $\dots$. No explanation is given for the first formula: the reasoning that led to it is not mentioned. Although the actual reasoning is easy to guess from the structure of the formula, some explanation ought to be given. We give a justification of the second formula.

Assume that all of the $n_i$ are distinct. This was not mentioned explicitly, but is a necessary assumption. The result is false otherwise.

Imagine arranging our $n$ objects in a row. Now group the first $n_1$ together, then the next $n_1$, and so on until we have $a_1$ groups of $n_1$ members each. Then do the same with $n_2$, and so on.

Do this for every one of the $n!$ permutations of our $n$ objects. We will get every division of the type you are looking for. The only problem is that we get every division in more than one way. But luckily every division is obtained in the same number of ways.

Each division into groups of $n_1$ occurs in $a_1!(n_1!)^{a_1}$ ways. This is because each of the $a_1$ little groups can be internally permuted in $n_1!$ ways, for a total of $(n_1!)^{a_1}$ ways. Then each of the $a_1$ groups themselves can be permuted as blocks in $a_1!$ ways. The same consideration applies to all $i \le m$. Thus we need to divide $n!$ by $$\left[a_1!a_2!\cdots a_m!\right]\left[(n_1!)^{a_1}(n_2!)^{a_2}\cdots (n_m!)^{a_m}\right].$$

-
Oops, I forgot to type in the division by $a_1!a_2!\dots a_m!$, but I meant to include that. – Robert S. Barnes Dec 23 '11 at 7:31
I added that into the question. – Robert S. Barnes Dec 23 '11 at 7:33
@Robert S. Barnes: Edited answer to omit correction of formula. Comment at the end became irrelevant. – André Nicolas Dec 23 '11 at 7:43
+1 Thanks! Much clearer than the explanation in my book. Just a little nitpick, I think you should use the term sets instead of groups as it's more specific and matches the term in the original question. – Robert S. Barnes Dec 23 '11 at 11:18
I guess that the same logic can be extended to any arbitrarily deep nesting of sets of sets? – Robert S. Barnes Dec 23 '11 at 11:21