I solved $\sum_{k=1}^n(k-1)(n-k)$ algebraically \begin{eqnarray*} \sum_{k=1}^n(k-1)(n-k)&=&\sum_{k=1}^n(nk-n-k^2+k)\\ &=&\sum_{k=1}^nnk-\sum_{k=1}^nn-\sum_{k=1}^nk^2+\sum_{k=1}^nk\\ &=&\frac{n(n^2+n)}{2}-n^2-\frac{n(2n^2+3n+1)}{6}+\frac{n^2+n}{2}\\ &=&n\left(\frac{3n^2+3n-6n-2n^2-3n-1+3n+3}{6}\right)\\ &=&n\left(\frac{n^2-3n+2}{6}\right)=\frac{n(n-1)(n-2)}{6}\\ &=&\frac{n!}{(n-3)!3!}=\binom{n}{3} \end{eqnarray*} But now I am interested in a combinatorial interpretation of it. For the right hand side $\binom{n}{3}$ is the number of ways to choose 3 from a total of $n$, and for the left hand side, it looks like dividing $n$ into 2 groups, one of size $k$, and other of size $(n-k)$, then sum over all possible $k$, but I do not see any clues that how I can choose 3 from these 2 groups.


The left hand side represents picking a "middle" element in a set of $3.\ $ Then you have $k-1$ choices for picking the smallest element and $n-k$ choices for picking the largest element.

For example if $n=5$ and $k=3$, then you have $2 \times 2$ ways of $3$ being the middle element:

$$(1 2) 3 (4 5)$$

If $n = 7$ and $k=5$, you have $4 \times 2$ ways for $5$ to be the middle element:

$$(1 2 3 4) 5 (6 7)$$

  • $\begingroup$ Really sneaky. $\endgroup$ – vonbrand Mar 26 '13 at 18:16

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.