¿Es cierto que$\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$, donde$N=\{1, 2, \dots, n\}$ y$i \in N$?

Question

La página 227 de Un curso de introducción a la teoría de juegos matemáticos por González-Díaz, García-Jurado y Fiestras-Janeiro ofrece una fórmula para el valor Shapley$\Phi$ de juegos de utilidad transferibles$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! $, pero tengo curiosidad de por qué esto es cierto.

¿Alguien puede dar una prueba detallada de que$\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$?

Gracias.

Answer 1

Deje $A$ el número de maneras de listado de los elementos de $N$.

Primera forma: $n!$. Esto viene por primera elige un número al azar y escribir primero. A continuación, la elección de un segundo número al azar y la escritura en segundo lugar, etc. Hay $n!$ maneras de hacer esto.

La segunda manera. Empezar por la fijación de $S\subset N\setminus\{i\}$. Una de las formas de la lista de los elementos en $N$ es primero la lista de los elementos en $S$ (hay $|S|!$ fue a hacer esto), luego añadir el número de $i$, y finalmente a la lista de los restantes $n-|S|-1$ elementos (hay $(n-|S|-1)!$ maneras de hacer esto). Así, por un fijo $S$, si insistimos en el listado de los elementos dentro de $S$ primera, entonces no se $|S|!(n-|S|-1)!$ maneras de hacer esto. Podemos obtener todas las posibles listas de esta manera como vamos a considerar todas las opciones posibles de $S$: $$ \sum_{S\subconjunto N\setminus\{i\}}|S|!(n|S|-1)! $$ Por lo tanto, $$ n!=\sum_{S\subconjunto N\setminus\{i\}}|S|!(n|S|-1)! $$

Answer 2

Supongo que$N$ es un conjunto con$n$ elementos. Estoy dando una prueba algebraica, ya que se ha proporcionado una prueba combinatoria. La igualdad requerida es equivalente a$$n!=\sum_{r=0}^{n-1}\,\binom{n-1}{r}\,r!\,(n-r-1)!\,,$ $ ya que hay$\binom{n-1}{r}$ sets$S$ con$r$ elementos contenidos en$N\setminus \{i\}$, donde$i \in N$ y$r\in\{0,1,2,\ldots,n-1\}$. Ahora,$\binom{n-1}{r}=\frac{(n-1)!}{r!\,\big((n-1)-r\big)!}$ por definición, entonces$$\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!\,.$ $