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?
 A: 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.
A: $$\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!)
A: 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.

