Prove that (kn)! is divisible by (n!)^k

Show that (kn)! is divisible by (n!)^k.

My attempts at a solution:
In my first attempt, I tried a factorization of the problem as follows:
(kn)! = (kn)*(kn-1)*(k-2)...(kn-n+1) *
((k-1)n)*((k-1)n-1)*((k-1)n-2)*((k-1)n-1)...((kn-1)n-n+1)*
((k-2)n)*((k-2)n-1)*((k-2)n-2)*((k-2)n-1)...((kn-2)n-n+1)*
.
.
.
((k-k+1)n)*((k-k+1)n-1)*((k-k+1)n-2)*((k-k+1)n-1)...((k-k+1)n-n+1)

Then, I wanted to factor that into: (k!)(n!)^k... which I now realize is illegal.


Then, I wanted to do induction, so I tried to do the first couple k's, so that I'd have a base case to start from:

k=1, (kn)! = (1n)! which is obviously divisible by (n!)^1

k=2, (kn)! = (2n)! = (2n)(2n-1)(2n-2)(2n-3)(2n-4)(2n-5)(2n-6)(2n-7)(2n-8).....
= 2(n)(2n-1)2(n-1)(2n-3)2(n-2)(2n-5)2(n-3)(2n-7)2(n-4).....
= (2^n)(n!)(2n-1)(2n-3)(2n-5)(2n-7)...

I feel like I found a pattern... if I can find another n! in this, maybe I can generalize and all would be good and well?

Does anybody have any advice? Thanks for any help you can give me!

You have \(\displaystyle nk\) items, of which \(\displaystyle n\) are of type \(\displaystyle 1\), \(\displaystyle n\) are of type \(\displaystyle 2\), ... , \(\displaystyle n\) are of type \(\displaystyle k\). How many combinations are possible?

Hi,
I am assuming that both 'k' and 'n' are variables, if so, then take n=2, and k =2. The statement does not hold for these values.

ablaze_mind said:

I am assuming that both 'k' and 'n' are variables, if so, then take n=2, and k =2. The statement does not hold for these values.

Click to expand...

Which statement? n=2 & k=2
\(\displaystyle (2 \cdot 2)! = 24\,\& \,\left[ {2!} \right]^2 = 4\)

I don't think this is true in general -- suppose k > n and k is prime. Then (n!)^k cannot divide (kn)! since k is one of the divisors of (kn)! and all the prime divisors of (n!)^k will be smaller than k. In fact, suppose k = 2. Then you have:

(2n)! is div by (n!)^2

This won't work if the sequence n+1, n+2, .... 2n contains any primes. Almost certainly it does.