Is it true that $\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$, where $N=\{1, 2, \dots, n\}$ and $i \in N$? Page 227 of An Introductory Course on Mathematical Game Theory by Gonzalez-Diaz, Garcia-Jurado, and Fiestras-Janeiro gives a formula for the Shapley value $\Phi$ of transferable utility games $v\in G^N$ as: $$\Phi_i(v):=\sum_{S\subset N \setminus \{i\}}\frac{|S|!(n-|S|-1)!}{n!}(v(S \cup \{i\})-v(S)).$$ It goes on to state that "therefore, in the Shapley value, each player gets a weighted average of the contributions he makes to the different coalitions." Saying that this is a weighted average of the values $(v(S \cup \{i\})-v(S))$ implies that $\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$, but I'm curious as to why this is true. 
Can someone please give a detailed proof that $\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$ ?
Thank you.
 A: Let $A$ be the number of ways of listing the elements of $N$. 
First way: $n!$. This comes about by first choosing one number at random and writing it first. Then choosing a second number at random and writing in second, etc. There are $n!$ ways to do this. 
Second way. Start by fixing $S\subset N\setminus\{i\}$. Then one way to list out the elements in $N$ is to first list out the elements in $S$ (there are $|S|!$ was to do this), then to append the number $i$, and finally to list out the remaining $n-|S|-1$ elements (there are $(n-|S|-1)!$ ways to do this). Thus, for a fixed $S$, if we insist on listing the elements within $S$ first, then there are $|S|!(n-|S|-1)!$ ways to do this. We can get all possible lists this way as we consider all possible choices of $S$:
$$
\sum_{S\subset N\setminus\{i\}}|S|!(n-|S|-1)!
$$
Therefore, 
$$
n!=\sum_{S\subset N\setminus\{i\}}|S|!(n-|S|-1)!
$$
A: I assume that $N$ is a set with $n$ elements.  I am giving an algebraic proof, since a combinatorial proof has been provided.  The required equality is equivalent to 
$$n!=\sum_{r=0}^{n-1}\,\binom{n-1}{r}\,r!\,(n-r-1)!\,,$$ 
as there are $\binom{n-1}{r}$ sets $S$ with $r$ elements contained in $N\setminus \{i\}$, where $i \in N$ and $r\in\{0,1,2,\ldots,n-1\}$.  Now, $\binom{n-1}{r}=\frac{(n-1)!}{r!\,\big((n-1)-r\big)!}$ by definition, so
$$\sum_{r=0}^{n-1}\,\binom{n-1}{r}\,r!\,(n-r-1)!=\sum_{r=0}^{n-1}\,(n-1)!=n\cdot(n-1)!=n!\,.$$
