0
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

If you want to have a rigorous proof, one way is to prove it by mathematical induction using the idea.

$\endgroup$
  • $\begingroup$ Thanks. How would you prove the inductive case - How can we use the inductive hypotheses ? In general is the proof I've listed considered rigorous enough (sufficient?) $\endgroup$ – Shuzheng Jan 1 '14 at 10:45
  • $\begingroup$ 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? $\endgroup$ – mathlove Jan 1 '14 at 10:57
  • $\begingroup$ 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 ? $\endgroup$ – Shuzheng Jan 1 '14 at 11:04
  • $\begingroup$ OK, I'm going to explain it, but can I use the following? "the permutation when we arrange $n$ distinct objects is $n!$." $\endgroup$ – mathlove Jan 1 '14 at 11:12
  • $\begingroup$ 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) $\endgroup$ – mathlove Jan 1 '14 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.