a counting problem

[fourier jr]

show that \frac{ ((n^2)!)!}{(n!)^{n+1}} is an integer.

i was thinking of saying that there are so many people who can be put on a committee, etc etc which would make an integer. i don't think this is real hard but nothing is really jumping out at me

[Davorak]

\frac{ ((n^2)!)!}{(n!)^{n+1}}

Not to bad. The denominator can be broken into:

(n^{n+1})((n-1)^{n+1})... ... ...


Each one of these term must be in the (n^2)! term in the numerator or be a divisor of this term.


(n^2)! > n^{n+1}


Therefore \frac{ ((n^2)!)!}{(n!)^{n+1}} must be an integer.

[fourier jr]

update: i thought of something that might be easier. check this out


the multinomial theorem says

\left(\begin{array}{cc}n\\ r_1, r_2, ..., r_k \end{array} \right) = \frac{n!}{r_1!r_2!...r_k!} for r_1 + r_2 + ... + r_k = n

so if i set r_1 = r_2 = ... = r_k = k, then r_1 + r_2 + ... + r_k = k.k = k^2 in which case the multimonial theorem gives me \frac{(k^2)!}{(k!)^k} which is an integer by definiton, so i'm almost there & i just need to do the rest somehow