Counting Problem: Proving the Integer Property of ((n^2)!)!/(n!)^(n+1)

[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