# OK to post homework
# Vikrant, Mar 06 2022, Assignment 12

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C12.txt"):

# ================================================================================
# 1. Read up on Shapley values.
# ================================================================================

# Done.

# ================================================================================
# 2. Check BM, FM are inverses.
# ================================================================================

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

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

# ================================================================================
# 3. Why when f and g are tables with equal entries, evalb(f=g) can be false?
# ================================================================================

# Tables are mutable data structures.
# In Maple, mutable data structures are distinct unless they share the same address.
# That is, f=g iff addressof(f)=addressof(g).
# Arrays, for example, are also mutable data structures; two identical-to-the-eye arrays may not be equal.
# Contrast this with lists, which are immutable.
# Source: Maple 7 Programming Guide.

# ================================================================================
# 4. Super-additivity checker.
# ================================================================================

with(combinat,powerset):

CheckSuperAdditivity:=
    proc(f,n)
        local S,T:
        evalb(`and`(seq(seq(f[S union T]>=f[S]+f[T] or (S intersect T)<>{},S in powerset(n)),T in powerset(n)))):
    end:

# ================================================================================
# 5. Proof that BM, FM are inverses.
# ================================================================================

# t = |T|.
# s = |S|.

# BM(FM(f)) = f :
# FM(f[T]) = sum_{S subset T} f[S].
# Consider any subset S of T.
# If S = T, f[S] is a summand of only FM(f[T]) and so is counted once under BM(FM(f[T])).
# Otherwise, f[S] is counted (t-s)C(t-s) - (t-s)C(t-s-1) + (t-s)C(t-s-2) - ... + (-1)^(t-s)(t-s)C(0) = (1 - 1)^(t-s) = 0 times under BM(FM(f[T])).


# FM(BM(f)) = f :
# Similar argument to above but the alternating signs come from summands of BM(f) rather than BM(FM(f)).

# ================================================================================
# 6. What is this sequence?
# ================================================================================

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:

# A000166.
# f[S] = |S|! where S lives in the boolean lattice of height n.
# Since there are nCk elements living at level k of the boolean lattice of height n, BM(f,n)[[n]] = n! - nC1(n-1)! + ... + (-1)^n(nCn)0!.
# This is identical to the formula for counting derangements of [n] using inclusion-exclusion.