#OK to post homework 
#Natalya Ter-Saakov, March 6, Assignment 12
read "C12.txt":

with(combinat):

#Problem 2
#CheckBMFM(n,K) inputs a random function, call it f, defined on subests of {1,...,n}
# and checkes that BM(FM(f,n))=f, viewed as tables, by checking that you always get the same value if you evaluate it at any subset of {1,...n}

CheckBMFM:=proc(f,n) local BMFM:
	BMFM:=BM(FM(f,n),n):
	EqualEntries(f,BMFM):
end:

#CheckFMBM(n,K) inputs a random function, call it f, defined on subests of {1,...,n}
# and checkes that FM(BM(f,n))=f, viewed as tables, by checking that you always get the same value if you evaluate it at any subset of {1,...n}

CheckFMBM:=proc(f,n) local FMBM:
	FMBM:=BM(FM(f,n),n):
	EqualEntries(f,FMBM):
end:

#Problem 4
#CheckSuperAdditivity(f,n): inputs a function on the set of subsets of {1, ...,n} and outputs true iff for every two disjoint subsets S and T of {1,...,n}, you have # f[S union T] ≥ f[S] + f[T]

CheckSuperAdditivity:=proc(f,n) local PN, PS, S, T:
	PN:=powerset(n):
	for S in PN do
		PS:=powerset(S):
		for T in PS do 
			if f[S]<f[S minus T] +f[T] then 
				return false:
			fi:
		od:
	od:
	true:
end:

#for i from 1 to 20 do f:=FM(RG(5,20),5): CheckSuperAdditivity(f,5); od;
#Returned true all 20 times

#Problem 5
#Claim: FM and BM are inverses of each other.
#Proof: Let h be a random game. Then, FM(r)=f is defined by f(S) = Sum_{T subset of S} h(T) and BM(r)=g is defined by g(S) = Sum_{T subset of S} (-1)^(|S|-|T|)*h(T).

#Consider f(g(S)) = Sum_{T subset of S} g(T)
# = Sum_{T subset of S} Sum_{R subset of T} (-1)^(|T|-|R|)*h(R)
# = Sum_{R subset of S} (-1)^|R|*h(R)*Sum_{T subset of S, superset of R} (-1)^|T| 
# = Sum_{R subset of S} (-1)^|R|*h(R)*Sum_{|R|<=t<=|S|} (-1)^t * (|S|-|R| choose t-|R|)
# = Sum_{R subset of S} h(R)*Sum_{0<=t<=|S|-|R|} (-1)^t * (|S|-|R| choose t)
# = Sum_{R subset of S, R=/=S} h(R)*(1-1)^(|S|-|R|) + h(S)*(-1)^0*(0 choose 0)
# = h(S)

# Consider g(f(S)) = Sum_{T subset of S} (-1)^(|S|-|T|)*f(T)
# = Sum_{T subset of S} (-1)^(|S|-|T|)*Sum_{R subset of T} h(R)
# = (-1)^|S|*Sum_{R subset of S} h(R)*Sum_{T subset of S and superset of R} (-1)^|T|
# = (-1)^|S|*Sum_{R subset of S} h(R)*(-1)^|R|* Sum_{0<=t<=|S|-|R|} (-1)^(t)*(|S|-|R| choose t)
# = (-1)^|S|*Sum_{R subset of S, R=/=S) h(R)*(-1)^|R|*(1-1)^(|S|-|R|) + (-1)^|S|*h(S)*(-1)^|S|
# = h(S)

# Therefore, FM and BM are inverses of each other.

#Problem 6

A:=proc(n) local f,S,PN,i1:
PN:=powerset(n):
for S in PN do 
	f[S]:=nops(S)!:
od: 
BM(f,n)[{seq(i1,i1=1..n)}];
end:

#This is A000166, the number of derangements, i.e. permutations of n elements with no fixed points

#This is because f[S] counts the number of permutations where everything that isn't in k is a fixed point. So, to count the number of derangements, we start with all permutations and use  a Mobius transform (or the Principle of Inclusion/Exclusion) to get the permutations with no fixed points.
#(#derangements) = (#permutations)-(#permutations with 1 fixed point) +... +/- (# permutations with all points fixed)

#BM(f,n)[{seq(i1,i1=1..n)}] 
# = add((-1)^(n-nops(S))*nops(S)!, S in PS)
# = add((-1)^(n-k)binomial(n,k) k!, k=1..n)
# = add((-1)^(n-k)n!/(n-k)!, k=1..n)