9
$\begingroup$
  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.

$\endgroup$
12
$\begingroup$

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}$.

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

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.$$

$\endgroup$
2
$\begingroup$

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.