Evaluating $\sum_{0\leq k,l \leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)$ algebraically

I'm having problems with the following sum:

$$\sum_{0\leq k,l \leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)$$

It's quite easy to think about it combinatorically:

We have $n$ balls, we're coloring $k$ of them, then $l$ of these colored balls get sprinkled with gold. Then we're putting a crown on one colored ball, one colored, sprinkled with gold ball and one uncolored ball.

It's all kind of funny but it allowed me to come up with, as it turns out, correct evaluation of this sum - first we're crowning 3 balls $\binom{n}{3}$, then we're chosing for each "crowned" ball whether it's colored, colored and sprinkled with gold or uncolored ($3!$) and then for the remaining $n-3$ balls we're either coloring them, coloring them and sprinkling with gold or do nothing with them ($3^{n-3}$). So we get:

$\sum_{0\leq k,l \leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)=\binom{n}{3}3!3^{n-3}=n(n-1)(n-2)3^{n-3}$

But I have no idea how to get the similair result using only algebraic methods. Any hints?

• This isn't strictly an algebraic problem. The factorial function in most cases isn't even elementary. Using calculus, and mathematical induction is perfectly acceptable and mostly needed. After all, if algebra could solve anything in math, we wouldn't have mathematicians. – Zach466920 Mar 17 '15 at 14:50

\begin{align*} \sum_{k,\ell}\binom{n}k\binom{k}\ell\ell(k-\ell)(n-k)&=\sum_k(n-k)\binom{n}k\sum_\ell\binom{k}\ell\ell(\ell-k)\\ &=\sum_k(n-k)\binom{n}kk(k-1)\sum_\ell\binom{k-2}{\ell-1}\\ &=\sum_k(n-k)\binom{n}kk(k-1)\sum_\ell\binom{k-2}\ell\\ &=\sum_k(n-k)\binom{n}kk(k-1)2^{k-2}\\ &=n(n-1)(n-2)\sum_k\binom{n-3}{k-2}2^{k-2}\\ &=n(n-1)(n-2)\sum_k\binom{n-3}k2^k\\ &=n(n-1)(n-2)3^{n-3}\;, \end{align*}

where the last step uses the binomial theorem. (But I prefer the combinatorial argument!)

• I have written a proof that is very close to yours, but I have added some detail and explanation. Would you mind if I post my answer, too? – robjohn Mar 20 '15 at 22:02
• @robjohn: In a nod to the Any hints? I deliberately didn’t explain the manipulations of the binomial coefficients, but that’s a judgement call; I’ll leave it up to you. – Brian M. Scott Mar 20 '15 at 22:07
• Ah, I missed the "Any hints?" tucked in there at the end. Especially with all the extensive alternatives (not yours; yours is very close to what I was about to post, with some added details). I will just leave it be, then. – robjohn Mar 20 '15 at 22:16

Observe that $$\sum_{0\leq k,l\leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)=\sum_{k=0}^n\binom{n}{k}(n-k)\left(\sum_{l=0}^k\binom{k}{l}l(k-l)\right)$$

Define $$f(x,y,z)=(x+y+z)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}(y+z)^k=\sum_{k=0}^n\binom{n}{k}x^{n-k}\left(\sum_{l=0}^k\binom{k}{l}y^lz^{k-l}\right)$$

Then we have

$$\frac{\partial^3 f}{\partial x\partial y\partial z}(x,y,z)=\sum_{k=0}^n\binom{n}{k}(n-k)x^{n-k-1}\left(\sum_{l=0}^k\binom{k}{l}l(k-l)y^{l-1}z^{k-l-1}\right)$$

Thus plug in $(x,y,z)=(1,1,1)$ we have

$$\frac{\partial^3 f}{\partial x\partial y\partial z}(1,1,1)=\sum_{k=0}^n\binom{n}{k}(n-k)\left(\sum_{l=0}^k\binom{k}{l}l(k-l)\right)$$

On the other hand

$$\frac{\partial^3 f}{\partial x\partial y\partial z}(x,y,z)=\frac{\partial^3}{\partial x\partial y\partial z}(x+y+z)^n=n(n-1)(n-2)(x+y+z)^{n-3}$$

thus

$$\frac{\partial^3 f}{\partial x\partial y\partial z}(1,1,1)=n(n-1)(n-2)3^{n-3}$$

which is exactly what we want.

Using complex variables we have the following result.

Suppose we are trying to evaluate $$\sum_{k=0}^n \sum_{l=0}^k {n\choose k} {k\choose l} l(k-l)(n-k).$$

The inner term is $${n\choose k} {k\choose l} l(k-l)(n-k) = \frac{n!}{k! (n-k-1)!}\frac{k!}{(l-1)!(k-l-1)!} \\ = \frac{n!}{(n-k-1)!(l-1)!(k-l-1)!} = n(n-1)(n-2) \frac{(n-3)!}{(n-k-1)!(l-1)!(k-l-1)!} = n(n-1)(n-2) {n-3\choose n-k-1, l-1, k-1-l}.$$

We see that the problem reduces to showing that $$\sum_{k=0}^n \sum_{l=0}^k {n-3\choose n-k-1, l-1, k-1-l} = 3^{n-3}.$$

We could stop here noticing that this last identity follows by inspection. Instead we will introduce the integral representation

$${n-3\choose n-k-1, l-1, k-1-l} \\ = \frac{1}{2\pi i} \int_{|z|=R_1} \frac{1}{2\pi i} \int_{|w|=R_2} \frac{1}{z^l} \frac{1}{w^{k-l}} (1+z+w)^{n-3} \; dw \; dz.$$

This certainly holds with $0\lt R_{1,2} \lt\infty.$

Observe that we can extend the sums to infinity because the integrals set the range. We have $$\sum_{k=0}^\infty \frac{1}{w^k} \sum_{l=0}^\infty \frac{w^l}{z^l} = \frac{1}{1-w/z} \sum_{k=0}^\infty \frac{1}{w^k} \\ = \frac{1}{1-w/z} \frac{1}{1-1/w} = \frac{z}{z-w} \frac{w}{w-1} .$$

It is important to note that this converges for $|w|\lt |z|$ (inner) and $|w|\gt 1$ (outer).

This gives for the sum $$\frac{1}{2\pi i} \int_{|z|=1+\epsilon_1} \frac{1}{2\pi i} \int_{|w|=|z|-\epsilon_2} (1+z+w)^{n-3} \frac{z}{z-w} \frac{w}{w-1} \; dw \; dz$$ where $\epsilon_1 > \epsilon_2.$

We get from the pole at $w=1$ which is certainly inside the contour used $$\frac{1}{2\pi i} \int_{|z|=1+\epsilon_1} (2+z)^{n-3} \frac{z}{z-1} \; dz.$$

and finally the pole at $z=1$ gives $$3^{n-3}.$$

This MSE link has another computation in the same spirit.