3
$\begingroup$

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.

  • 0
    I$ $added$ $a concrete example to try and make the question more clear.2011-12-23

1 Answers 1

5

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].$

  • 0
    @Robert S. Barnes: Hard to know about arbitrarily deep nesting until an explicit question is formulated.2011-12-24