Prove the identity $\sum_{i=0}^n i(n-i) = {n+1 \choose 3}$ , by a combinatorial argument This question was asked on an exam I made. In the answers they proved a bijection between the following sets:
$\def\N{\Bbb N}X_i = \{\,(a, i, b) \mid a,b \in\N ∪ \{0\}, 0 ≤ a < i, i < b ≤ n\,\}$ for $i \in \{ 0, 1, \ldots , n\}$
$Y = \{\,C \mid C ⊆ \N_{n+1}, |C| = 3\,\}$ where $\N_{n+1}=\{\,i\in\Bbb Z\mid 0\leq i\leq n\,\}$
and provided the following relations:
$f : \bigcup_{i=0}^n X_i \to Y : (a,i,b) \mapsto \{a,i,b\} $
$f^{-1}: Y \to \bigcup_{i=0}^n X_i : \{c_1, c_2, c_3\}$  with $c_1 < c_2 < c_3 \mapsto (c_1, c_2, c_3)$
Could someone provide me with an explanation as to why these sets and relations were chosen?
 A: The situation here is to count the number of 3-element subsets in $\{ 0, 1, \dots, n \}$, hence the right hand side $\binom{n + 1}{3}$.
Now we think of another way to generate a 3-element subsets. We pick a "pivot" by fixing one of the element, say $2$. In the next step, we pick another one less than the "pivot", i.e. $0$ or $1$, and the remaining one greater than the "pivot", i.e. $3, 4, \dots , n$. Suppose for now this method generates all the 3-element subsets of $\{ 0, 1, \dots, n \}$.
In your setting, $X_i$ is the collection of triples with "pivot" $i$ generated by the scheme above, and $\bigcup _{i = 0} ^n X_i$ is all the subsets generated by the method above, as we vary the "pivot" from $0$ to $n$. The set $Y$ is simply the collection of 3-element subsets.
Your relation $f$ can be used to show that the two sets are equipotent. Notice that for any triple in sorted order, say $(1, 2, 3)$, we can always link them to the 3-element subset $\{ 1, 2, 3 \}$. Conversely, given such a set, we can always construct this sorted triple. So $f$ is a bijection between $\bigcup _{i = 0} ^n X_i$ and $Y$. In other words, picking a "pivot" then two other elements, one greater and one smaller than the "pivot" indeed generates all the 3-element subsets.
With the bijection established, note that for a fixed "pivot" $i$, as there are $i$ numbers less than it and $n - i$ greater, the number of triples for all the "pivot"s is
$$
  \sum _{ i = 0} ^n i (n - i) \, .
$$
Thus
$$ 
  \sum _{ i = 0} ^n i (n - i) = \binom{n + 1}{3} \, .
$$
A: By stars and bars, the number of $k$-uples $(x_1,\ldots,x_k)$ with $x_j\in\mathbb{N}^+$ such that $x_1+\ldots+x_k = n$ is given by $\binom{n-1}{k-1}$. This is the same as stating that
$$ [x^n]\left(\sum_{m\geq 1}x^m\right)^k = \binom{n-1}{k-1} \tag{1}$$
$$ \frac{x^k}{(1-x)^k} = \sum_{n\geq k}\binom{n-1}{k-1} x^n \tag{2} $$
$$ \frac{x^{k}}{(1-x)^{k+1}} = \sum_{n\geq k}\binom{n}{k} x^{n} \tag{3} $$
so by considering the instance $k=3$ of $(3)$ we have
$$\sum_{k=0}^{n}k(n-k) = [x^n]\left(\sum_{k\geq 0} k x^k\right)^2 = [x^n]\frac{x^2}{(1-x)^4} = [x^{n+1}]\frac{x^3}{(1-x)^4} = \binom{n+1}{3}.$$
