# Combinatorical meaning of an identity involving factorials [duplicate]

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.

-

## marked as duplicate by dtldarek, Brian M. Scott, Javier Álvarez, lab bhattacharjee, Hagen von EitzenFeb 10 '13 at 9:56

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}$$
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$.
Well, it is an comb. interpretation in the same way that «The number of subsets of a set of $n$ elements is $2^n$» interprets $\sum_i\binom{n}{i}=2^n$. – Mariano Suárez-Alvarez Feb 10 '13 at 19:18
There is an easy argument, not using binomial doeffiecients, that an $n$-set has $2^n$ subsets. Do you similarly have an argument that "the number of ways you can sort ... and paint one of them blue" equals $(N+1)!-1$? This fact isn't obvious to me. – Marc van Leeuwen Feb 11 '13 at 5:05