How one can show $(r!)^s$ divides $(rs)!$?

Question

I would like if anybody have suggestions to prove:

if $n = rs$

with: $r > 0$ and $s > 0$

then $(r!)^s \mid n!$

suggestions?

Answer 1

Any of the products

$1\cdot 2 \cdot 3... \cdot r$,

$(r+1)\cdot (r+2)\cdot (r+3)\cdot ... 2r$,

...

$(s-1)r\cdot ((s-1)r+1) \cdot ((s-1)r+2)\cdot ...\cdot sr$

is divisible by $r!$ because dividing the products by $r!$, we simply get the binomial coefficients $\binom {kr}{r}$ , $k=1,...,s$

Answer 2

Let illustrate it with an example. Say to prove that $$ 3!^4 | 12! $$ We may analyze the products as follows: $$ \eqalign { 1 \cdot 2 \cdot 3 \cdot \ \ \ &\ \ \ \ \ 1 \cdot 2 \cdot 3 \cdot \cr 1 \cdot 2 \cdot 3 \cdot \ \ \ &\ \ \ \ \ 4 \cdot 5 \cdot 6 \cdot \cr 1 \cdot 2 \cdot 3 \cdot \ \ \ &| \ \ \ \ 7 \cdot 8 \cdot 9 \cdot \cr 1 \cdot 2 \cdot 3 \cdot \ \ \ &\ \ \ \ \ 10 \cdot 11 \cdot 12 \cr } $$ Now you should observe that the following hold : $$ \eqalign{ (1 \cdot 2 \cdot 3 ) \ &| \ \ (1 \cdot 2 \cdot 3) \ obvious \cr (1 \cdot 2 \cdot 3 ) \ &| \ \ (4 \cdot 5 \cdot 6) \ \ because\ \ \binom{6}{3}\ is \ integer\cr (1 \cdot 2 \cdot 3 ) \ &| \ \ (7 \cdot 8 \cdot 9) \ \ because\ \ \binom{9}{3}\ is \ integer\cr (1 \cdot 2 \cdot 3 ) \ &| \ \ (10 \cdot 11 \cdot 12) \ \ because\ \ \binom{12}{3}\ is \ integer \cr } $$

Answer 3

We have \begin{align*} \frac{(sr)!}{(r!)^s} &=\frac{(sr)!}{r!\cdot[(s-1)r]!} \cdot\frac{[(s-1)r]!}{r!\cdot[(s-2)r]!}\cdots\frac{r!}{r!}= {sr\choose r}\cdot{(s-1)r\choose r}\cdots{r\choose r}\in\mathbb{N}. \end{align*}

Answer 4

You have $r$ balls each of $s$ different colors. In how many ways can you arrange these $rs$ balls in a line?

Answer 5

$S_r \times S_r \times \cdots \times S_r$ ($s$ times) is a subgroup of $S_{rs}$.

By Lagrange's theorem in group theory, its order $(r!)^s$ divides $(rs)!$, the order of $S_{rs}$.

More generally, if $n=n_1+n_2+\cdots+n_k$, then $n_1! n_2!\cdots n_k!$ divides $n!$ because $S_{n_1} \times S_{n_2} \times \cdots \times S_{n_k}$ is a subgroup of $S_{n}$, whose index is the multinomial coefficient $$ \binom{n_1+n_2+\cdots+n_k}{n_1! n_2!\cdots n_k!} $$