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 – Henning Makholm 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 May 1 '16 at 16:25
• @user2357112: Hmm, so it does. I missed that. – Henning Makholm 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.

So we have three things we want to prove are divisible. By using modulo we may express this:

a is divisible by b if: $$a \mod b = 0$$

Therefore, we can write the three equality's below and prove by lack of contradiction within algebra:

A.

$$(kn)! \mod (n!)^k = 0$$

Rewrite it as the large product operator:

$$\prod_{i=1}^{kn} i \mod (\prod_{i=1}^{n} i)^k = 0$$

I'm not sure how this guarantees divisibility. I know I can divide out one n!, but I think this is indivisible. Is the author certain that only one answer is true?

B.

Since A's formula only differs by reversing arbitrary letters, we have the same result for B.

C.

$$(kn)! \mod (n!)(k!) = 0$$

Write as a large product:

$$\prod_{i=1}^{kn} i \mod \prod_{i=1}^{n} i * \prod_{i=1}^{k} i = 0$$

Rewrite assuming n < k

$$\prod_{i=1}^{kn} i \mod \prod_{i=1}^{2n} i * \prod_{i=n+1}^{k} i = 0$$

Since k is guaranteed to at least equal 2...

$$\prod_{i=2n+1}^{kn} i \mod \prod_{i=n+1}^{k} i = 0$$

Since n is guaranteed to at least equal 2...

We can split the left product into two quantities. One is the odd indexes multiplied together and one is the even indexes multiplied together. Since multiplication is commutative and associative, this is valid, just not easily expressable through notation. Therefore, since we wish to prove that 2 times the right term exists in the left term, we must assure that even indexes [2n + 2, 2k] are present. Now, since k > n, k >= n+1. Also, since n > 1, kn > k. n is an integer so 2k is present at least. 2n+1 < 2n+2 <= 2k. Therefore, the terms are divisible and C is proven to be valid through algebra.

Unfortunately, this question seems to imply multiple indivisible quantities. If the author would establish only one is wrong then I will try to finish proving the A and B. Otherwise, I can only presume that some of these are indeterminate forms. Of course, if only one answer is correct, than A and B cannot be the answer due to them being completely identical statements.