# OK to post homework
# RDB, 2022-03-04, HW12

# 1. Done!

# 2.

# Thanks to Rebecca for finding EqualEntries!

read "C12.txt":

with(combinat):

setTable := proc(f, n)
    local v:
    for S in powerset(n) do
        v[S] := f(S):
    od:

    op(v):
end:

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

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

# 3. Blegh.

# 5.

# Very nice proof! Essentially the same as the classical Mobius inversion
# formula.

# Say that f(S) = sum(g(T), T <= S). Then:

#   sum(f(T) (-1)^(|T| - |S|), T <= S)
#       = (-1)^|S| sum(g(R) (-1)^|T|, R <= T, T <= S)
#       = (-1)^|S| sum(g(R) sum((-1)^|T|, R <= T <= S), R <= S)
#       = (-1)^|S| sum(g(R) sum(binomial(|S| - |R|, k) (-1)^(|R| + k), k=0..|S|-|R|), R <= S)
#       = (-1)^|S| sum(g(R) (-1)^|R| [|S| = |R|], R <= S)
#       = g(S)

# Going the other way is nearly identical.

# Here's a question for you: In number theory, the Mobius inversion formula
# translates to a statement about (Dirichlet) generating functions. Is there a
# similar generating function statement here?

# I know there's some very general statement of Mobius inversion over a poset.
# Something about incidence algebras. There might be something tucked away in
# "On the Applications of Mobius Inversion in Combinatorial Analysis" by Bender
# and Goldman, which is an explainer of Doubilet, Rota and Stanley's big paper.

# 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:

# The sequence I get is:

# 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961

# This is clearly A166, the derangement numbers!

# My gut tells me to just unfold the definition.

# Let f(S) = |S|!. Then, the inverse Mobius transform applied to f is

#       g(S) = sum(f(T) (-1)^(|T| - |S|), T <= S)
#            = sum(|T|! (-1)^(|T| - |S|), T <= S)
#            = sum(binomial(|S|, t) t! (-1)^(t - |S|, 0 <= t <= |S|)
#            = sum(|S|! / (|S| - t)! * (-1)^(t - |S|, 0 <= t <= |S|)
#            = |S|! sum((-1)^k / k!, 0 <= k <= |S|).

# This is exactly the formula for the |S|th derangement number, which I just
# happen to remember.

# Natasha reminded me of the more combinatorial argument.
# There are |S|! / k! permutations with k fixed points.