6
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

8
$\begingroup$

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)$$

$\endgroup$
1
  • $\begingroup$ Really sneaky. $\endgroup$
    – vonbrand
    Commented Mar 26, 2013 at 18:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .