# Rigorous proof: Combinatorics problem - The number of ways to arrange $n$ objects, $n_1$ being of one kind,…, $n_r$ being of an rth kind.

Reading in a book on the subject Mathematical Statistics I came across this theorem, whcih is in the section of Combinatorics.

The number of ways to arrange $n$ objects, $n_1$ being of one kind, $n_2$ being of a second kind, ..., and $n_r$ being of a rth kind is:

$$\frac {n!} {n_1!n_2!\ldots n_r!}$$

where $\sum_{i=1}^r n_i = n$.

Proof:

Let $N$ denote the total number of such arrangements. For anyone of those arrangements the similar objects (if they were actually different) could be arranged in $n_1! \cdot n_2! \cdot \ldots \cdot n_r!$ ways. It follows that $N n_1! n_2! \ldots n_r!$ is the total number of ways to arrange $n$ (distinct) objects. But $n!$ equals that same number, so we have $$n! = N \cdot n_1! \cdot n_2! \cdot \ldots \cdot n_r! \Rightarrow N = \frac {n!} {n_1! \cdot n_2! \cdot \ldots \cdot n_r!}.$$

Question:

$N$ is the number of arrangements of $n$ objects with respect to their kind. So for each such arrangement, if considering objects to be different, it must correspond to $n_1! \cdot n_2! \cdot \ldots \cdot n_r!$ permutations. So multiplying this number by $N$ gives the total number of permutations and thereby an equation to solve for $N$.

Is this proof rigorous enough ? I mean it sounds right, but still we cannot normally base a proof on such justification or can we ? Should't we use set theory or something alike ?

• Use $(n!/(n_1!n_2!\cdots n_r!))\times \binom{n+n_{r+1}}{n_{r+1}}$. What makes you think it is not enough? – mathlove Jan 1 '14 at 10:57
• The proof is involving just text, and one could speculate that $N \cdot n_1! \cdot n_2! \cdot \ldots \cdot n_r!$ actually is the number of ways to permute $n$ objects ? – Shuzheng Jan 1 '14 at 11:04
• OK, I'm going to explain it, but can I use the following? "the permutation when we arrange $n$ distinct objects is $n!$." – mathlove Jan 1 '14 at 11:12
• Suppose that I can use the sentence of my last comment. Let us consider an easy case. Suppose that we have $p$ $A$s, $q$ $B$s, $r$ $C$s. Let $X$ be the number of the permutation when we don't distinguish same letters. First, we have $p!$ patterns if we distinguish only the letter $A$. Next, we have $q!(p!X)$ patterns if we distinguish the letter $B$. Finally, we have $r!(q!p!X)$ patterns if we distinguish the letter $C$. (continued) – mathlove Jan 1 '14 at 11:24