Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$

I tested it for some small $k$ and $n$, but I don't know how to prove that it is true (or find example showing that it is not).

share|improve this question
    
My immediate reaction would be to do generating functions, but that's just because I really like that approach. A better way would probably just be to show that the two sides are simply two different ways of counting the same set of objects. –  Semiclassical Aug 6 at 18:32

4 Answers 4

up vote 3 down vote accepted

We have

$${ln -1 \choose n-1} = \frac{(ln-1)!}{(n-1)! [(l-1)n]!} = \frac{1}{n!}\times \frac{(ln-1)!}{ [(l-1)n - 1]!} \times \frac{1}{l-1}$$

so

$$\prod_{l=1}^k {ln -1 \choose n-1} = \frac{n}{n!^k}\times \prod_{l=2}^k\frac{(ln-1)!}{[(l-1)n - 1]!} \times \prod_{l=2}^k\frac{1}{l-1}$$

In the middle product successive terms cancel

$$\prod_{l=2}^k\frac{(ln-1)!}{[(l-1)n - 1]!} = \frac{(kn-1)!}{(n-1)!}$$

and

$$\prod_{l=2}^k\frac{1}{l-1} = \frac{1}{(k-1)!}$$

so

$$\prod_{l=1}^k{ln -1 \choose n-1} = \frac{n}{n!^k} \frac{(kn-1)!}{(k-1)!} = \frac{(kn)!}{(n!)^kk!}$$

proving the claim.

share|improve this answer

To show that the theorem is true by algebraic manipulations, observe that

\begin{align} \frac{(kn)!}{(n!)^k} =\frac{(kn)!}{(kn-n)!n!}\cdot\frac{(kn-n)!}{(n!)^{k-1}} &=\binom{kn}{n} \frac{(kn-n)!}{(n!)^{k-1}}\\ &=\binom{kn}{n}\binom{kn-n}{n}\cdot\frac{(kn-2n)!}{(n!)^{k-2}}\\ &\;\vdots\\ &=\binom{kn}{n}\binom{kn-n}{n}\cdots \binom{kn-mn}{n}\cdot \frac{(kn-(m+1)n)!}{(n!)^{k-(m+1)}}\\ &\;\vdots\\ &=\binom{kn}{n}\binom{kn-n}{n}\cdots \binom{2n}{n}\binom{n}{n} \end{align} Note that the last fraction has been exhausted in this manner. Thus the LHS of the identity may be rewritten as $$\frac{(kn)!}{k! (n!)^k}=\frac{1}{k!}\prod_{l=1}^{k}\binom{ln}{n}=\prod_{l=1}^{k}\frac{1}{l}\frac{(ln)!}{n! (ln-n)!}\cdot\frac{n}{n}=\prod_{l=1}^{k}\binom{ln-1}{n-1}$$ as claimed.

One can also do a counting proof of the first identity I showed above: Suppose we want to form $kn$ people into $n$ teams of $k$. One way to do that is first choose $n$ out of $kn$ people, then the next $n$, etc. until all $k$ teams are selected. This can be done in $\binom{kn}{n}\cdots \binom{kn-n}{n}\cdots\binom{n}{n}=\prod_{l=1}^k \binom{ln}{n}$ ways. But I could also do this all at once, in which case the total number is given by the multinomial coefficient $$\binom{kn}{\underbrace{n,\cdots,n}_k}=\frac{(kn)!}{\underbrace{n!n!\cdots n!}_k}=\frac{(kn)!}{(n!)^k}$$

share|improve this answer

$\textbf{1)}$ If $k=1$, we have $\frac{n!}{n!}=\binom{n-1}{n-1}=1$.

$\textbf{2)}$ Suppose $\displaystyle\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad$ for some $k\ge1$.

Then $\displaystyle\frac{((k+1)n)!}{(k+1)!(n!)^{k+1}}=\left(\frac{kn+n}{(k+1)n}\right)\frac{(kn+n-1)!}{(n-1)!}\frac{1}{k!(n!)^{k}}=\frac{(kn+n-1)!}{(n-1)!(kn)!}\frac{(kn)!}{k!(n!)^{k}}$

$\displaystyle=\binom{(k+1)n-1}{n-1}\prod_{l=1}^{k}\binom{ln-1}{n-1}=\prod_{l=1}^{k+1}\binom{ln-1}{n-1}.$

share|improve this answer

Using the fact that

$$\frac{\bigg((n-1)!\bigg)^k}{(n!)^k} = \frac{1}{n^k},$$

the formula becomes:

$$\frac{(kn)!}{k!n^k} = \prod_{l = 1}^k \frac{(ln-1)!}{(ln-n)!} = \prod_{l=1}^k \prod_{j=1}^{n-1} (ln-j).$$

By simply looking at the forumla on the right, you will see that it is precisely the product $(kn) \cdot (kn-1) \cdot (kn-2) \cdot \dots \cdot (1)$ except that it is missing the terms of the form $ln$ for $l = 1$ to $k$. The product of these missing terms is $k!n^k$, and so the formula is valid.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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