Evaluating Sums Combinatorially Consider the following finite sums:
(1) $\sum k(k!)$ for k from 1 to n
(2) $\sum (k-1)(n-k)$ from 1 to n
I am trying to determine how to evaluate these sums combinatorially.  It seems the first is describing the number of ways to arrange k objects k times for each k and the second is describing the number of ways to count the number of ways to choose from two piles of labelled objects with replacement.  Are these ideas in the right direction?
 A: For the first one, we have $n+1$ people,  named $0,1, 2,\dots, n$, and lined up in a row from left to right, in that order.
We want to rearrange them, so that at least one person moves.   There are clearly $(n+1)!-1$ ways to do this. Let us count the number of rearrangements another way.
For any $k$, with $1\le k\le n$, let $N_k$ be the number of rearrangements in which the rightmost person who moves is $k$.
Where $k$ moves to can be any of the $k$ places $0$ to $k-1$.  Once we have chosen this place,  there are $k!$ rearrangements of the remaining people $0$ to $k-1$ into the positions $0$ to $k$. Thus $N_l=k\cdot k!$, and the number of rearrangements in which at least one person moves is $\sum_1^n k\cdot k!$.
For the second problem, one way to visualize is that we have $n$ people lined up in a row, and we want to choose $3$ of them. There are $\binom{n}{3}$ ways to do this.
To count another way, suppose the "middle" person chosen is $k$, where $k$ goes from $2$ to $n-1$. For any such $k$, the person in front of her can be chosen in $k-1$ ways, and then the person behind her can be chosen in $n-k$ ways. Adding up over all $k$ gives us the total number of of ways to choose $3$ people.
