Proving that $\frac{(k!)!}{k!^{(k-1)!}}$ is an integer

I have to prove that:

$$\frac{(k!)!}{k!^{(k-1)!}} \in \Bbb Z$$

for any $k \geq 1, k \in \Bbb N$

Tried doing $t = k!$ which would give $$\frac{t!}{t^{t/k}}$$

But I think I just made it harder, and I have no other clue!

A hint:

Assume that there are $(k-1)!$ colors, and that you have $k$ balls of each color. In how many ways can you arrange them in a long line?

• (+1) I love the combinatorial approach (probably because I'm bad at it; I often just resort to prime factorisations). – Lord_Farin Apr 10 '13 at 12:31
• @Lord_Farin: I first tried to do this by counting the multiplicity of each and every prime. It is surprisingly close, so the trial lower bound was not quite good enough. I think it is possible to do it that way, but one has to exercise some care. – Jyrki Lahtonen Apr 10 '13 at 12:40
• In my opinion it is enough to say this for a proof. I mean, out of the logic of combinatorics, the number of options of sorting something is a final Integer. Thank you. – TheNotMe Apr 10 '13 at 13:18

We have $$(n!)!=\prod_{i=1}^{n!}i=\prod_{k=1}^{(n-1)!}u_{n,k}$$where$$u_{n,k}=\prod_{i=kn-n+1}^{kn}i=(kn-n+1)\cdots(kn)=n!{kn\choose{n}}$$ hence $$(n!)!=(n!)^{(n-1)!}\left(\prod_{k=1}^{(n-1)!}{kn\choose n}\right)$$

The multinomial coefficient $${n\choose k_1,k_2,\ldots, k_r},$$ where all the variables are non-negative integers and $k_1+k_2+\cdots+k_r=n$, counts the number of ways we can partition a set of $n$ objects into subsets $A_1,A_2,\ldots,A_r$ such that $|A_i|=k_i$ for each $i$. Alternatively it is the coefficient of the term $x_1^{k_1}x_2^{k_2}\cdots x_r^{k_r}$ in the multinomial expansion of $(x_1+x_2+\cdots+x_r)^n$.

It is easy to show by induction on $r$ (using the more common binomial coefficient as the base case as well as the inductive step) that $${n\choose k_1,k_2,\ldots, k_r}=\frac{n!}{k_1!k_2!\cdots k_r!}.$$

The number in the question is the multinomial coefficient with $n=k!$, $r=(k-1)!$ and $k_i=k$ for all $i=1,2,\ldots,(k-1)!$.

Therefore it is an integer.

• But then, $n=k!$ so $k! \cdot (k-1)! \neq n$, hence $\sum k_i \neq n$. – Jean-Claude Arbaut Apr 10 '13 at 12:31
• @arbautjc: But $k \cdot (k-1)! = n$. The $k_i$ are all equal to $k$, not $k!$. – Clive Newstead Apr 10 '13 at 12:33
• There was a typo in the first version, where I had "one factorial sign too many", and the $k_i$ marked equal to $k!$. They are supposed to be equal to $k$. Some people of course saw the version, where the misprint was still there. – Jyrki Lahtonen Apr 10 '13 at 12:37
• Ok, now everything is ok. Clive's comment made me think I had misread. – Jean-Claude Arbaut Apr 10 '13 at 12:39