I'm looking for a combinatorial proof that $$\sum_{i=0}^n 2^i\binom{n}{i}i!(2n-i)! = 4^n(n!)^2.$$

My thoughts so far: the RHS counts the number of pairs of permutations on $n$ elements along with an $n$-tuple whose entries come from 4 choices. The LHS might count the same thing but partitioned into cases somehow.

  • $\begingroup$ Where do you find these strange sentences @Carl Mummert? What as you thinking, when you wrote them down? And where did you find these words? $\endgroup$ – coffeee Mar 12 at 9:18

Not a combinatorial proof, but still a proof. We may notice that $$ k!(2n-k)! = \Gamma(k+1)\Gamma(2n-k+1) = (2n+1)!\cdot B(k+1,2n-k+1) $$ equals $(2n+1)! \int_{0}^{1} x^{2n-k}(1-x)^k\,dx=(2n+1)! \int_{0}^{1} x^{k}(1-x)^{2n-k}\,dx$, hence $$ \sum_{k=0}^{n}2^k\binom{n}{k}k!(2n-k)! = (2n+1)!\int_{0}^{1}\sum_{k=0}^{n}\binom{n}{k}(2x)^k (1-x)^{2n-k}\,dx $$ and by the binomial theorem the integrand function in the RHS equals $(1-x^2)^n$, so $$\begin{eqnarray*} \sum_{k=0}^{n}2^k\binom{n}{k}k!(2n-k)! &=& (2n+1)!\int_{0}^{1}(1-x^2)^n\,dx\\&=&\tfrac{1}{2}(2n+1)!\int_{0}^{1} x^{-1/2}(1-x)^{n}\,dx\\&=&\tfrac{1}{2}(2n+1)!\cdot B\left(\tfrac{1}{2},n+1\right)=\color{red}{4^n n!^2}.\end{eqnarray*} $$


Not a combinatorial proof either, however from

$$\sum_{q=0}^n {n\choose q} 2^q q! (2n-q)! = 4^n (n!)^2$$

we obtain on dividing by $(n!)^2$

$$\sum_{q=0}^n {2n-q\choose n-q} 2^q = \sum_{q=0}^n [z^{n-q}] (1+z)^{2n-q}2^q = [z^{n}] (1+z)^{2n} \sum_{q=0}^n z^q (1+z)^{-q} 2^q .$$

Now when $q\gt n$ there is no contribution to the coefficient extractor in front and we may write:

$$[z^{n}] (1+z)^{2n} \sum_{q\ge 0} z^q (1+z)^{-q} 2^q \\ = [z^{n}] (1+z)^{2n} \frac{1}{1-2z/(1+z)} = [z^{n}] (1+z)^{2n+1} \frac{1}{1-z}.$$

This is

$$\sum_{q=0}^n [z^q] (1+z)^{2n+1} [z^{n-q}] \frac{1}{1-z} = \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 4^n.$$


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.