3

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!

Mike
  • 33
  • 4
    Also check out http://math.stackexchange.com/questions/1730313/combinatorial-argument-for-1-sum-r-1r-n-r-cdot-r-n1?noredirect=1&lq=1, http://math.stackexchange.com/questions/1198735/proving-sum-k-1n-k-k-n1-1?noredirect=1&lq=1, http://math.stackexchange.com/questions/928642/calculating-sum-k-1nkk-combinatorially?noredirect=1&lq=1 – StubbornAtom Oct 11 '16 at 07:15

1 Answers1

2

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.

Austin Mohr
  • 25,662
  • 1
    Wow, numbering players is an ingenious idea! Thanks a lot! I was wondering what you mean by "except for the identity" – Mike Oct 11 '16 at 04:48
  • 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! – Mike Oct 11 '16 at 04:53
  • @Mike That's what I mean. The "identity permutation" is the permutation that does nothing - it leaves all the players in the original order. – Austin Mohr Oct 11 '16 at 04:54
  • 1
    This is really clever. Thank you very much! – Mike Oct 11 '16 at 04:55
  • I was thinking about this a little more and I have another question: When we permute, let's say, 3 people out of these n people, don't we also double-count one of the cases where we permuted 2 people? Like the case where keeping the 3rd person at their original position and permuting the first two (I think this is included in the 3! permutation, as well). – Mike Oct 11 '16 at 05:05
  • @Mike I don't think there is an overcount here. When $k=2$, for example, player 3 cannot remain in their original position (they must be moved to position 1 or 2). When $k=3$, we could possibly duplicate the positions with the first three players, but now player 4 is guaranteed not to be a fixed point, giving a distinct permutation. In general, I think you can build a bijection based on which players must be fixed and which cannot be fixed (namely, player $k$ for each $k$). – Austin Mohr Oct 11 '16 at 05:16
  • 1
    @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. – Andreas Blass Oct 11 '16 at 05:18
  • Oh, I definitely get it now. Thank you both for your explanations! – Mike Oct 11 '16 at 05:30