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

[alec_tronn]

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!

 

[royhaas]

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?

 

[ablaze_mind]

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.

 

[pka]

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.

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

 

[PAULK]

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.