3
$\begingroup$

For $n ≥ 2$, $$\sum_{k=1}^{n-1} k \cdot k!= n!-1 $$

On the left-hand side, we could be choosing ordered subteams from $n-1$ people (let's say for some reason one of these people cannot be qualified). the range of k would be the size of subteams and $k!$ would be ordering them. $k$ could also be ${k \choose 1}$, which means we could be choosing a team leader for each ordered subteam. On the right-hand side, we order all $n$ people and then take out one of these cases but what I can't figure out is how to equate these two sides. Could you give any hints that could help me progress here?

Note: I apologize that this was a duplicate. Thanks for everyone who helped!

|cite|improve this question
$\endgroup$
2
$\begingroup$

Number the players from $1$ to $n$ and ask them to stand in increasing order. For each $k$:

  • Rearrange the first $k$ players in any of $k!$ ways.
  • Insert player $k+1$ in front of any of the first $k$ players (in $k$ ways).

Every permutation of $n$ can be realized in this way except for the identity. I'll leave it to you to establish the bijection.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Wow, numbering players is an ingenious idea! Thanks a lot! I was wondering what you mean by "except for the identity" $\endgroup$ – Mike Oct 11 '16 at 4:48
  • $\begingroup$ oh, I think I get it now. Do you mean except for the original order?(for the right-hand side) Because on the left-hand side, there is no reordering for k=0, which would be the original order. Also, thanks for editing the question! $\endgroup$ – Mike Oct 11 '16 at 4:53
  • $\begingroup$ @Mike That's what I mean. The "identity permutation" is the permutation that does nothing - it leaves all the players in the original order. $\endgroup$ – Austin Mohr Oct 11 '16 at 4:54
  • 1
    $\begingroup$ This is really clever. Thank you very much! $\endgroup$ – Mike Oct 11 '16 at 4:55
  • 1
    $\begingroup$ @Mike Person number $k+1$ gets inserted into the ordering "in front of" one of the first $k$, and thus will not be at his original position. $\endgroup$ – Andreas Blass Oct 11 '16 at 5:18

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