Mixing
Is it true that $sum_S subset N setminus i S=n!$, where $N=1, 2, dots, n$ and $i in N$?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
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 $vin G^N$ as: $$Phi_i(v):=sum_Ssubset N setminus ifracn!(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 =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 =n!$ ?
Thank you.
combinatorics summation factorial game-theory
edited Jul 16 at 17:38
ervx
9,39531336
asked Jul 16 at 17:20
Rasputin
38619
add a comment |Â
up vote
4
down vote
favorite
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 $vin G^N$ as: $$Phi_i(v):=sum_Ssubset N setminus ifracn!(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 =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 =n!$ ?
Thank you.
combinatorics summation factorial game-theory
edited Jul 16 at 17:38
ervx
9,39531336
asked Jul 16 at 17:20
Rasputin
38619
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
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 $vin G^N$ as: $$Phi_i(v):=sum_Ssubset N setminus ifracn!(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 =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 =n!$ ?
Thank you.
combinatorics summation factorial game-theory
edited Jul 16 at 17:38
ervx
9,39531336
asked Jul 16 at 17:20
Rasputin
38619
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 $vin G^N$ as: $$Phi_i(v):=sum_Ssubset N setminus ifracn!(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 =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 =n!$ ?
Thank you.
combinatorics summation factorial game-theory
edited Jul 16 at 17:38
ervx
9,39531336
asked Jul 16 at 17:20
Rasputin
38619
edited Jul 16 at 17:38
ervx
9,39531336
edited Jul 16 at 17:38
ervx
9,39531336
edited Jul 16 at 17:38
ervx
9,39531336
9,39531336
asked Jul 16 at 17:20
Rasputin
38619
asked Jul 16 at 17:20
Rasputin
38619
asked Jul 16 at 17:20
Rasputin
38619
38619
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39
add a comment |Â
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
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 $Ssubset Nsetminusi$. 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_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
Therefore,
$$
n!=sum_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
answered Jul 16 at 17:37
ervx
9,39531336
add a comment |Â
up vote
1
down vote
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,binomn-1r,r!,(n-r-1)!,,$$
as there are $binomn-1r$ sets $S$ with $r$ elements contained in $Nsetminus i$, where $i in N$ and $rin0,1,2,ldots,n-1$. Now, $binomn-1r=frac(n-1)!r!,big((n-1)-rbig)!$ by definition, so
$$sum_r=0^n-1,binomn-1r,r!,(n-r-1)!=sum_r=0^n-1,(n-1)!=ncdot(n-1)!=n!,.$$
answered Jul 16 at 17:42
Batominovski
23.2k22777
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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 $Ssubset Nsetminusi$. 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_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
Therefore,
$$
n!=sum_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
answered Jul 16 at 17:37
ervx
9,39531336
add a comment |Â
up vote
1
down vote
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 $Ssubset Nsetminusi$. 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_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
Therefore,
$$
n!=sum_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
answered Jul 16 at 17:37
ervx
9,39531336
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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 $Ssubset Nsetminusi$. 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_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
Therefore,
$$
n!=sum_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
answered Jul 16 at 17:37
ervx
9,39531336
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 $Ssubset Nsetminusi$. 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_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
Therefore,
$$
n!=sum_Ssubset Nsetminusi|S|!(n-|S|-1)!
$$
answered Jul 16 at 17:37
ervx
9,39531336
answered Jul 16 at 17:37
ervx
9,39531336
answered Jul 16 at 17:37
ervx
9,39531336
answered Jul 16 at 17:37
ervx
9,39531336
9,39531336
add a comment |Â
add a comment |Â
up vote
1
down vote
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,binomn-1r,r!,(n-r-1)!,,$$
as there are $binomn-1r$ sets $S$ with $r$ elements contained in $Nsetminus i$, where $i in N$ and $rin0,1,2,ldots,n-1$. Now, $binomn-1r=frac(n-1)!r!,big((n-1)-rbig)!$ by definition, so
$$sum_r=0^n-1,binomn-1r,r!,(n-r-1)!=sum_r=0^n-1,(n-1)!=ncdot(n-1)!=n!,.$$
answered Jul 16 at 17:42
Batominovski
23.2k22777
add a comment |Â
up vote
1
down vote
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,binomn-1r,r!,(n-r-1)!,,$$
as there are $binomn-1r$ sets $S$ with $r$ elements contained in $Nsetminus i$, where $i in N$ and $rin0,1,2,ldots,n-1$. Now, $binomn-1r=frac(n-1)!r!,big((n-1)-rbig)!$ by definition, so
$$sum_r=0^n-1,binomn-1r,r!,(n-r-1)!=sum_r=0^n-1,(n-1)!=ncdot(n-1)!=n!,.$$
answered Jul 16 at 17:42
Batominovski
23.2k22777
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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,binomn-1r,r!,(n-r-1)!,,$$
as there are $binomn-1r$ sets $S$ with $r$ elements contained in $Nsetminus i$, where $i in N$ and $rin0,1,2,ldots,n-1$. Now, $binomn-1r=frac(n-1)!r!,big((n-1)-rbig)!$ by definition, so
$$sum_r=0^n-1,binomn-1r,r!,(n-r-1)!=sum_r=0^n-1,(n-1)!=ncdot(n-1)!=n!,.$$
answered Jul 16 at 17:42
Batominovski
23.2k22777
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,binomn-1r,r!,(n-r-1)!,,$$
as there are $binomn-1r$ sets $S$ with $r$ elements contained in $Nsetminus i$, where $i in N$ and $rin0,1,2,ldots,n-1$. Now, $binomn-1r=frac(n-1)!r!,big((n-1)-rbig)!$ by definition, so
$$sum_r=0^n-1,binomn-1r,r!,(n-r-1)!=sum_r=0^n-1,(n-1)!=ncdot(n-1)!=n!,.$$
answered Jul 16 at 17:42
Batominovski
23.2k22777
answered Jul 16 at 17:42
Batominovski
23.2k22777
answered Jul 16 at 17:42
Batominovski
23.2k22777
answered Jul 16 at 17:42
Batominovski
23.2k22777
23.2k22777
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853626%2fis-it-true-that-sum-s-subset-n-setminus-i-sn-s-1-n-where%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
The right side, $n!$, clearly denotes the number of permutations of $1,2,dots,n$. The left side is a summation, and a specific term in the summation denotes the number permutations of $1,2,dots,n$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$).
– JMoravitz
Jul 16 at 17:39