Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
As far as I can see you have interpreted the left hand side combinatorially, but not the right hand side. –  Marc van Leeuwen Feb 10 '13 at 8:59
    
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
    
A combinatorial interpretation (or meaning, as in the question) is not the same thing as a combinatorial proof. The one in your answer, which is the standard bijective proof for this identity, is a proof (usually, these proofs are also interpretations, surely) But my rendition of of left hand side of the identity is a more or less unimaginative way of producing a set with the required cardinal. Mind you, I have no idea how to prove the identity using my interpretation! –  Mariano Suárez-Alvarez Feb 11 '13 at 9:01
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.