Proving that $(xy)!/y!^x$ is an integer

Question

I'm learning about factorials and combinatorics in class, and this problem came up, but I don't know how to solve it. The teacher said that it would be an integer, but how can I show this? $$ \frac{\left ( mk \right )!}{k!^{m}} \in \mathbb{N} $$

Thanks in advance

Answer 1

Proceed by induction on $m$. Clearly, if $m=1$ you have $\frac{k!}{k!} = 1$ is an integer. Now, for the inductive step consider $$\frac{((m+1)k)!}{(k!)^{m+1}} = \frac{(mk)!}{(k!)^m} \frac{(mk+1)(mk+2) \cdots (mk+k)}{k!}$$

By hypothesis $\frac{(mk)!}{(k!)^m}$ is an integer, so if you prove that $$\frac{(mk+1)(mk+2) \cdots (mk+k)}{k!} $$ is an integer you are done.

But this is true because the product of $k$ consecutive numbers is divisible by $k!$.

Answer 2

$$\frac{(mk)!}{k!^m}=\frac{\color{red}{(1.2\cdots k)}\color{green}{((k+1).(k+2)\cdots(2k))}\cdots\color{blue}{(((m-1)k+1).((m-1)k+2)\cdots(mk))}}{\color{red}{k!}.\color{green}{k!}\cdots\color{blue}{k!}}$$ Does that gave you some HINT?

Answer 3

You have a total of $xy$ balls, namely $y$ balls of each of $x$ colors. In how many ways can you arrange these balls in a line, when two arrangements that cannot be distinguished colorwise are considered equal?