Therefore, (mn)! is divisible by m!(n!)^m.

[rukawakaede]

Hi, we know that for all interger $m$, $n_1!\cdots n_k!$ divides $m!$ where $n_1+\cdots+n_k=m$.

Now I want to show that $m! (n!)^m$ divides $(mn)!$.

We see that $(n!)^m$ divides $(mn)!$ since $\overbrace{n+\cdots+n}^{m-terms}=mn$

Also $m!(nm-m)!$ divides $(mn)!$ similarly.

But how could I show my required statement above? It works for some examples that I've tested and I believe it is true.

Any inputs would be appreciated! :)

 

[micromass]

Hi rukawakaede!

First of all, let us define the multinomial coefficient: (for $k_1+...+k_m=1$)

$$\binom{n}{k_1,...,k_m}=\frac{n!}{k_1!...k_m!}$$

What you want to show is that the multinomial coefficient

$$\binom{nm}{n,...,n}$$

is divisible by m!

Now, first note the following equality that represents the multinomial coefficients as binomials:

$$\binom{nm}{n,...,n}=\binom{n}{n} \binom{2n}{n}\binom{3n}{n} ...\binom{mn}{n}$$

So it actually suffices to show that $\binom{kn}{n}$ is divisible by k.

Let me give the idea on how to prove this by showing that 2 divides $\binom{2n}{n}$.

Factorize $2n=2^rs$ such that 2 does not divide s. In modulo 2, we know that

$$(X+1)^2=X^2+1$$

and thus

$$(X+1)^{2^r}=X^{2^r}+1$$

and thus

$$(X+1)^{2n}=(X^{2^r}+1)^s$$

Expanding both terms using the binomial theorem gives us that the coefficient of $X^n$ in both terms are equal. But the coefficient of $X^n$ in the left polynomial is

$$\binom{2n}{n}$$

But the coefficient of $X^n$ in the right polynomial is 0, as we can never write $n=2^rk$ (we have a 2 too much).

Hope that helped.

 

[Yuqing]

I'm wondering how you would generalize this method to composite m. The identity $(1 + x)^{m} \equiv 1 + x^m$ doesn't hold for composite bases.

 

[micromass]

I'm wondering how you would generalize this method to composite m. The identity $(1 + x)^{m} \equiv 1 + x^m$ doesn't hold for composite bases.

Prove it for all the prime factors. For example, to show that something is divisible by 6 is equivalent to showing that it is divisible by 2 and 3.

 

[Yuqing]

Prove it for all the prime factors. For example, to show that something is divisible by 6 is equivalent to showing that it is divisible by 2 and 3.

The problem I'm having is with prime powers. For example, your method proves 2 divides $\binom{2n}{n}$. Can you give an example on how you would prove, say, $\binom{8n}{n}$?

 

[micromass]

Hmm, I see the problem. But I made it harder than it was. In general, we know that

$$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$

Thus

$$\binom{\alpha n}{n}=\alpha\binom{\alpha n-1}{n-1}$$

so it is divisible by $\alpha$.