Combinatorial identity $\prod_{j=1}^n {n\choose j} =\prod_{k=1}^n {k^k\over k!}$

Question

How to prove the combinatorial identity?

$$\prod_{j=1}^n {n\choose j} =\prod_{k=1}^n {k^k\over k!}$$

I took $\ln$ of the left hand side

$$\sum_{j=0}^n \ln(j^{n+1}) - \ln((j!)^2)$$

but not going anywhere from here. any help is welcome

Answer 1

Start by rewriting the lefthand side:

$$\prod_{k=1}^n\binom{n}k=\prod_{k=1}^n\frac{n^{\underline k}}{k!}\;,$$

where $n^{\underline k}=n(n-1)(n-2)\ldots(n-k+2)$, so we need only show that

$$\prod_{k=1}^nn^{\underline k}=\prod_{k=1}^nk^k\;.\tag{1}$$

For $k=1,\ldots,n$ there is a factor of $k$ in $n^{\underline j}$ if and only if $n\ge k>n-j$, i.e., if and only if $n\ge j>n-k$. There are $n-(n-k)=k$ such integers $j$, so $k$ appears $k$ times in the product on the lefthand side of $(1)$. Of course it also appears $k$ times on the righthand side, so the two are equal.

Answer 2

We may just prove the claim by induction on $n$.
The case $n=1$ is trivial, hence we just have to prove that:

$$\frac{n^n}{n!}=\prod_{j=1}^{n-1}\frac{\binom{n}{j}}{\binom{n-1}{j}}=\prod_{j=1}^{n-1}\frac{n}{n-j}=\frac{n^{n-1}}{(n-1)!} $$ that is trivial as well.

Answer 3

We have, by product operator $\prod$ properties $$ \prod_{j=1}^{n}{ n \choose j} = \prod_{j=1}^{n}{ n! \over (n-j)!j! } = {\prod_{j=1}^n n! \over \prod_{j=1}^n (n-j)!\cdot j!} = {(n!)^n \over \prod_{j=1}^n (n-j)!\prod_{j=1}^nj!} $$ The result can be obtained by induction on n. The proposition $P(n):\prod_{j=1}^{n}\binom{n}{j}=\prod_{j=1}^{n}\frac{j^j}{j!}$ can be verified for $n = 2,3$ by simple inspection. Let us prove that for all $n\geq 3$ the proposition $P(n):\prod_{j=1}^{n}\binom{n}{j}=\prod_{j=1}^{n}\frac{j^j}{j!}$ is true whenever the proposition $P(n-1):\prod_{j=1}^{n-1}\binom{n-1}{j}=\prod_{j=1}^{n-1}\frac{j^j}{j!}$ is true. For this, we prove three equalities.

\begin{align} (\ast)\quad (n!)^n =& n^n\cdot(n-1)^n\cdot (n-2)^n\cdot \ldots\cdot 3^n\cdot 2^n\cdot 1^n \\ =& n^n\cdot\color{red}{(n-1)}\cdot\color{blue}{(n-1)^{n-1}}\cdot \color{red}{(n-2)}\cdot\color{blue}{(n-2)^{n-1}}\cdot \ldots\cdot \color{red}{3}\cdot \color{blue}{3^{n-1}}\cdot \color{red}{2}\cdot \color{blue}{2^{n-1}}\cdot \color{red}{1}\cdot \color{blue}{1^{n-1}} \\ =& n^n\cdot \color{red}{(n-1)!}\cdot \color{blue}{(n-1)^{n-1}\cdot (n-2)^{n-1}\cdot \ldots\cdot 3^{n-1}\cdot 2^{n-1}\cdot 1^{n-1}} \\ =& n^n\color{red}{(n-1)!}\color{blue}{\big((n-1)!\big)^{n-1}} \end{align} \begin{align} (\ast\ast)\quad\prod_{j=1}^{n}(n-j)! =& \color{red}{(n-1)!}\cdot\color{blue}{(n-2)!\cdot(n-3)!\cdot \ldots \cdot (n-(n-3))!\cdot(n-(n-2))!(n-(n-1))!(n-(n))!} \\ =& \color{red}{(n-1)!}\cdot\color{blue}{((n-1)-1)!\cdot((n-1)-2)!\cdot \ldots \cdot 3!\cdot 2!\cdot 1!} \\ =& \color{red}{(n-1)!}\color{blue}{\prod_{j=1}^{(n-1)}((n-1)-j)!} \end{align} and \begin{align} (\ast\ast\ast)\quad\prod_{j=1}^{n}j! =& n!\cdot \color{blue}{(n-1)!\cdot(n-2)!\cdot \ldots \cdot 3!\cdot 2!\cdot 1!} \\ =& n!\color{blue}{(n-1)!\cdot((n-1)-1)!\cdot((n-1)-2)!\cdot \ldots \cdot 3!\cdot 2!\cdot 1!} \\ =& n!\color{blue}{\prod_{j=1}^{(n-1)}j!} \end{align} Then $$ \prod_{j=1}^{n}{ n \choose j} = {(n!)^n \over \prod_{j=1}^n (n-j)!\prod_{j=1}^nj!} = {n^n\color{red}{(n-1)!}\color{blue}{\big((n-1)!\big)^{n-1}} \over \color{red}{(n-1)!}\color{blue}{\prod_{j=1}^{(n-1)}((n-1)-j)!} n!\color{blue}{\prod_{j=1}^{(n-1)}j!}} = {n^n \over n!} \prod_{j=1}^{n-1}{ n-1 \choose j} $$ To obtain the desired result simply replace $P(n-1):\prod_{j=1}^{n-1}\binom{n-1}{j}=\prod_{j=1}^{n-1}\frac{j^j}{j!}$ in the last equality.

Answer 4

Here is another algebraic approach.

We obtain

\begin{align*} \prod_{k=1}^n\binom{n}{k}&=\prod_{k=1}^n\frac{n(n-1)\cdots(n-k+1)}{k!}\\ &=\left(\prod_{k=1}^n\frac{1}{k!}\right)\left(\prod_{k=1}^n\prod_{j=n-k+1}^nj\right)\tag{1}\\ &=\left(\prod_{k=1}^n\frac{1}{k!}\right)\left(\prod_{k=1}^n\prod_{j=k}^nj\right)\tag{2} \\ &=\left(\prod_{k=1}^n\frac{1}{k!}\right)\left(\prod_{j=1}^n\prod_{k=1}^jj\right)\tag{3} \\ &=\left(\prod_{k=1}^n\frac{1}{k!}\right)\left(\prod_{j=1}^nj^j\right)\tag{4} \\ &=\prod_{k=1}^n\frac{k^k}{k!} \end{align*}

Comment:

• In (1) we separate products of numerator and denominator

• In (2) we exchange the order of multiplication in the second double product by letting $k \longrightarrow n-k$

• In (3) we exchange the products of the second double product by observing the index range is $1\leq k\leq j\leq n$

• In (4) we use $\prod_{k=1}^jj=j^j$