Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Division of Factorials

For a set of $n$ objects of which $n_1$ are alike and one of a kind, $n_2$ are alike and one of a kind, ... , $n_k$ are alike and one of a kind, such that $n_1+n_2+...+n_k=n$, the number of distinguishable permutations is: $$\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}$$ How come this is always an integer?

share|improve this question

marked as duplicate by leonbloy, Jasper Loy, Fabian, Davide Giraudo, rschwieb Jan 2 '13 at 14:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Since the formula is derrived as a number of distinguishable permutations then it certainly must be an integer. –  Golob Jan 2 '13 at 14:44

3 Answers 3

up vote 9 down vote accepted

$${(n_1 + \dots + n_k)! \over n_1! \cdots n_k!} = \frac{n_1!}{n_1!} \cdot \frac{(n_1 + n_2)!}{n_1!n_2!} \cdot \frac{(n_1 + n_2 + n_3)!}{(n_1 + n_2)!n_3!} \cdots \frac{(n_1 + \dots + n_k)!}{(n_1 + \dots + n_{k-1})!n_k!} =\\ \binom{n_1}{n_1} \cdot \binom{n_1+n_2}{n_2} \cdot \binom{n_1+n_2+n_3}{n_3} \cdots \binom{n_1 + \dots + n_k}{n_k}$$

share|improve this answer

It follows from the Fundamental Theorem of Arithmetic and the power of a prime in a factorial:

If $p$ is a prime, the power of $p$ at the top is

$$\sum_{m=1}^\infty \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

while the power of $p$ in the denominator is

$$\sum_{m=1}^\infty \lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor$$

Now, $\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor$ is an integer and

$$\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \frac{n_1+n_2+..+n_k}{p^m}$$

thus

$$\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

and hence

$$\sum_{m=1}^\infty \lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \sum_{m=1}^\infty \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

Now, since all primes appear at a larger power in the numerator, the FTA guarantees that this number is an integer.

share|improve this answer

You can show that $S_{n_1} \times S_{n_2} \times \ldots \times S_{n_k}$ is a subgroup of $S_n$, the statement then follows from Lagrange's theorem.

share|improve this answer

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