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

Question

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.

Answer 1

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)! $$

Answer 2

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!\,.$$