Why does it have to be an integer?

1. Let $k$ and $n$ be integers greater than 1. Then $(kn)!$ is not necessarily divisible by

• A. $(n!)^k$
• B. $(k!)^n$
• C. $n!\cdot k!$
• D. $2^{kn}$

I believe option D is correct and have a counter example for that.

Let $k=2$ and $n=3$ then $(kn)!=6!=720$ is not divisible by $64=2^{2*3}$.

What I don't understand is that why options A, B, C necessarily divide $(kn)!$.
Thanks for help.

• – lhf May 1 '16 at 21:56
• It was either that or snakes. – Daniel R Hicks May 2 '16 at 1:27

This can be seen from the fact that multinomial coefficients are integers : https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients

Then $\frac{(nk)!}{(n!)^k} = \binom{nk}{n,n,\dots,n}$, $\frac{(nk)!}{(k!)^n} = \binom{nk}{k,k,\dots,k}$ and $\frac{(nk)!}{(n!)(k!)} = (nk-n-k)!\binom{nk}{n,k,nk-n-k}$.

• $nk-n-k$ is negative if either $n$ or $k$ is $1$ -- but in that case the divisibility is clear anyway – hmakholm left over Monica May 1 '16 at 14:43
• Good catch, hadn't checked... – Captain Lama May 1 '16 at 14:45
• @HenningMakholm: The problem says $n$ and $k$ are greater than $1$ anyway. – user2357112 supports Monica May 1 '16 at 16:25
• @user2357112: Hmm, so it does. I missed that. – hmakholm left over Monica May 1 '16 at 16:27

For B. :$\binom {n+k} {k}=(n+k)!(n!!k!)^{-1}\in Z$ because it is the number of subsets of an $n+k$-element set that have exactly $k$ members each. So if $k>0$ then $k!$ divides the product of any $k$ consecutive positive integers, for if $k>0$ and $n\geq 0$ then $\binom {n+k} {k}= k!^{-1} \prod_{j=1}^k(n+j)).$ Therefore, for $n,i\geq 0 :$ $$A(i,k,n) = k!^{-1}\prod_{j=1}^k(i n+j)\in Z.$$ .So $k!^{-n}(nk)!=\prod_{i=0}^{n-1} A(i,k,n)\in Z.$

For A. : Interchange $k$ and $n$ in the argument for B.

For C. : $n +k\leq n k$ because $1\leq (n-1)(k-1)=n k -n-k+1.$ So $$(nk)!(n!k!)^{-1}=[(n k)!(n+k)!^{-1}] \binom {n+k} {k}\in Z.$$

$\frac{(kn)!}{n!^k}$ and $\frac{(kn)!}{k!^n}$ can both be recognized as multinomial coefficients which are integers.

Since $n,k>1$ also $\frac{(kn)!}{n!k!(kn-n-k)!}$ is a multinomial coefficient.