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 coefficent

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