Divisibility and factorial

Question

If $n = st$ and $s > 0$ and $t > 0$ then prove that $(s!)^t|n!$ . If I replace $n!$ with $ (st)!$ how can I simplify it so that I can show that the division is an integer.

Answer 1

Paraphrased from this answer, $$ \begin{align} &\binom{st}{s}\binom{st-s}{s}\binom{st-2s}{s}\cdots\binom{2s}{s}\binom{s}{s}\\ &=\frac{(st)!}{\color{#C00000}{(st-s)!}s!}\frac{\color{#C00000}{(st-s)!}}{\color{#00A000}{(st-2s)!}s!}\frac{\color{#00A000}{(st-2s)!}}{\color{#A0A0A0}{(st-3s)!}s!} \cdots\frac{\color{#A0A0A0}{2s!}}{\color{#0000FF}{s!}s!}\frac{\color{#0000FF}{s!}}{0!s!}\\ &=\frac{(st)!}{(s!)^t} \end{align} $$ Only the solid black terms don't disappear.

Answer 2

The easiest way is combinatorial. We have $n=st$ people, and we want to divide them into $t$ teams of $s$ people each, one Team to be called Team $1$, another to be named Team $2$, and so on up to Team $t$. Let $N$ be the number of ways to divide the people into labelled teams.

Line up the $st$ people. There are $(st)!$ ways to do this. Now call the first $s$ people Team $1$, the next $s$ people Team $2$, and so on.

Two permutations give the same division into labelled teams if one is obtained from the other by permuting the first $s$ people, the next $s$ people, and so on. There are $(s!)^t$ such permutations. It follows that $$N(s!)^t=(st)!,$$ and therefore $\dfrac{(st)!}{(s!)^t}$ is an integer.

Another way: We sketch a more algebraic approach. If $m$ is a positive integer, and $p$ is prime, then the largest power $p^e$ that divides $m!$ is given by $$e=\left\lfloor \frac{m}{p}\right\rfloor+ \left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$ Now calculate with $m=st$. Call the answer $a$. Calculate with $m=s$. Call the answer $b$. We need to show that $a-tb\ge 0$.