Combinatorical meaning of an identity involving factorials

Question

While solving (successfully!) problem 24 in projectEuler I was doodling around and discoverd the foloowing identity:

$$1+2\times2!+3\times3!+\dots N\times N!=\sum_{k=1}^{k=N} k\times k!=(N+1)!-1$$

While this is very easy to prove, I couldn't find a nice and simple combinatorical way to interpret this identity*. Any ideas?

---

*That is, I do have a combinatorical interpretation - that's how I got to this identity - but it's not as simple as I'd like.

Answer 1

Let $\sigma$ be a non-identity permutation of $N+1$. Let $k$ be maximal such that $\sigma_{k+1}\neq k$. Since $\sigma_i=i$ for $k+1<i\leq N+1$, we must have $\sigma_{k+1}\leq k$. Therefore $\sigma$ is determined by (i) the value of $k\in\{1,\ldots,n\}$, (ii) the value of $\sigma_{k+1}\in\{1,\ldots,k\}$, and (iii) the permutation $(\sigma_1,\ldots,\sigma_k)$ of the remaining $k$ numbers $\{1,\ldots,,k+1\}\setminus\{\sigma_{k+1}\}$, for a total of $$ \sum_{k=1}^Nk\times k!\text{ possibilities} $$

Answer 2

The number of ways you can sort a set of consecutive numbers starting from $1$ and none of which is larger than $N$ and then paint one of them blue is $(N+1)!-1$.