#OK to post homework
#Blair Seidler, 3/6/22, Assignment 12
with(combinat):

Help:=proc(): print(`CheckBMFM(n,K), CheckFMBM(n,K), CheckSuperAdditivity(f,n)`): end:

#3. Doing this one first, because I'm going to use what I found out in Problem 2.
# The following will tell you if tables f and g are identical:
# evalb(convert(op(op(f)), set) = convert(op(op(g)), set))

#2. Write procedures CheckBMFM(n,K) and CheckFMBM(n,K) that input a random function, call it f,
# defined on subests of {1,...,n} and checkes that FM(BM(f,n),n)=f and 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}

#Assuming that the "input a random function" means that the arguments n,K should be used to call
#RG(n,K) and check that function.

CheckBMFM:=proc(n,K) local f:
f:=RG(n,K):
evalb(convert(op(op(f)), set) = convert(op(BM(FM(f,n),n)), set)):
end:

CheckFMBM:=proc(n,K) local f:
f:=RG(n,K):
evalb(convert(op(op(f)), set) = convert(op(FM(BM(f,n),n)), set)):
end:

(* Output:

As expected, both functions always return true.

*)

#4. Write a procedure CheckSuperAdditivity(f,n) that 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 s:
  for s in choose(powerset(n),2) do
    if nops(s[1] intersect s[2])=0 and f[s[1] union s[2]]<f[s[1]]+f[s[2]] then
      return(false):
    fi:
  od:
true:
end:

#Check for a few random choices of FM(RG(5,20),5), it is indeed super-additive
(* Output: 

As expected, CheckSuperAdditivity(FM(RG(5, 20), 5), 5) returns true. I also checked to
make sure that we get false almost all the time without doing the FM.

*)

#5.

(*
The right way to do this formally is by induction on |S|, but I'm feeling too lazy to do that in Notepad.

Let f be an arbitrary function from 2^[n]->R.
Let g=FM(f,n).
For any S, subset of [n], g(S) is the sum of f(T) for all T which are subsets of S.
When we then calculate h=BM(g,n), we are using I-E to subtract out values.
h(S)=g(S)-sum(g(T) for all T which are S minus one element)
         +sum(g(T) for all T which are S minus two elements)
         - etc...
But g(S) was the sum of f(T) for all subsets T of S. The first subtraction removes f(T)
for all subsets of size |S|-1 but it also removes f(T') for every T' which is a proper subset
of any T. So for all of those T', we have removed a multiple of f(T') for each T which contained
it. So we have to add those back, but we add too many...

Eventually, we get that h(S)=f(S).

A similar argument would work in the other direction.

*)



#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:
(*
What OEIS (if any) is this sequence? A000166 (number of derangements of n variables)

Can you explain why? Sort of. f[S]=|S|! is the total number of permutations of each subset. So
f({1..n}) is the number of permutations of [n]. When we do BM(f,n), we are using Inclusion-Exclusion
to subtract out the permutations with fixed points, leaving us the permutations without fixed points.

Slightly more detailed: Consider n=4. Then f({1,2,3,4})=24, the number of permutations.
We subtract out f({1,2,3}), f({1,2,4}), f({1,3,4}), and f({2,3,4}), which are the number of
permutations with fixed points 4, 3, 2, and 1 respectively. But we have double-subtracted some of
them, so we need to add back in the permutations with 2 fixed points, subtract permutations with
3 fixed points, and finally add back the permutation with 4 fixed points to get the count right.
Classic I-E!
*)

#### From C12.txt ####

#C12.txt

Help12:=proc(): print(`Ex1(), RG(n,K), FM(f,n), BM(f,n) `): end:

Ex1:=proc():table([({3})=18,({2})=12,({})=0,({1, 3})=60,({2, 3})=90,({1, 2})=30,({1})=6,({1, 2, 3})=120]):end:

#RG(n,K): inputs an and K outputs a random "n-person game" with entries in [0,K]
RG:=proc(n,K) local ra,PS,S,f:
ra:=rand(0..K):
f[{}]:=0:
PS:=powerset(n):

for S in PS minus {{}} do
f[S]:=ra():
od:
op(f):
end:

#FM(f,n): inputs a function from 2^{1,...n} to pos. real numbres
#we want g(T)= Sum of g(S) over all subsets S of T
FM:=proc(f,n) local S,PS,PN,g,S1:
PN:=powerset(n):
for S in PN do
PS:=powerset(S):
g[S]:=add(f[S1], S1 in PS):
od:
op(g):
end:

#BM(f,n): inputs a function from 2^{1,...n} to pos. real numbres
#we want g(T)= Sum of (-1)^(|T|-|S|)*g(S) over all subsets S of T
BM:=proc(f,n) local S,PS,PN,g,S1:
PN:=powerset(n):
for S in PN do
PS:=powerset(S):
g[S]:=add( (-1)^(nops(S)-nops(S1))*f[S1], S1 in PS):
od:
op(g):
end: