Conjecture for product of binomial coefficient

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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