Calculating $\sum_{k=1}^nk(k!)$ combinatorially

Question

The sum $\sum_{k=1}^nk(k!)$ can be easily calculated by noting $k(k!)=(k+1)!-k!$. Is there a way to calculate the sum nicely using a combinatorial argument. Is it possible to notice it is $(n+1)!-1$ combinatorially?

Answer 1

I will explain it in case $n=4$ then I will replace it by general case. Assume you want to write a 5 digit number by numbers 1,2,3,4,5 except 12345. The number of possible numbers is 5!-1. In fact writing a 5 digit number by 1,2,3,4,5 has 5! possibilities and we delete 1 case.

Now count it in this way;

• Some of them can be written with 5 not be 5th one. So for 5 we have 4 positions and the other 4 numbers should be put in 4 places by 4! possibilities so 4(4!)
• The other cases 5 should remain at 5th position so again divide to two cases. First, 4 not in 4th position you so 4 has to be in 1st, 2nd or 3rd position by 3 choices then 1,2,3 have to be put at 2 remained positions from 1st, 2nd and 3rd which 4 is not there plus 4th position which is empty by 3! ways so this be done by 3(3!).
• The remained cases are ones that 5 is at 5th and 4 is at 4th position. Again divide it into two cases. First, 3 is not at 3rd position so we have 2 choice for it, 1st or 2nd position. 1 and 2 now can be sit at the remained position from 1st and 2nd which 3 is not there plus 3rd position so they can be put in the remained possible places by 2!. So number of numbers which produced here are 2(2!).
• Now the at remained possibilities, 5 is at 5th, 4 is at 4th, 3 is at 3rd positions. As we don't want 12345. So 2 should be at 1st (by 1 choice) and 1 should be at 2nd (by 1!=1 choice) so 1(1!).

By the second method we count possible requested numbers as this sum 4(4!)+3(3!)+2(2!)+1(1!). And as we were counting same thing so we have to have (4+1)!-1=5!-1=4(4!)+3(3!)+2(2!)+1(1!).

The general case is same when you are counting the number of n+1 digits numbers using n+1 (ordered) alphabet except $\overline{123...n(n+1)}$.