# How come $\frac{n!}{n_1!\cdot n_2!\cdot…\cdot n_k!}$ is always an integer? [duplicate]

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?

-

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

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

$${(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}$$

-

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.

-

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.

-