7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Rewriting $\binom nj$ as $\frac{n(n-1)\dots(n-j+1)}{j!}$ might help. Then compare the numerators and denominators of the LHS and the RHS. $\endgroup$ – Martin Sleziak Aug 11 '16 at 21:05
  • $\begingroup$ Now it's clear to me. thanks. $\endgroup$ – user324333 Aug 11 '16 at 21:10
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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