# hw9JikeLiu.txt
# Jike Liu

read `C9.txt`:

with(combinat):




# ------------------------------------------------------------
# Q1. NumberOfProperties(n,L,i)
# ------------------------------------------------------------

# NumberOfProperties(n,L,i): number of sets in the list L that contain i.
NumberOfProperties := proc(n, L, i) local j;
  add( `if`(member(i, L[j]), 1, 0), j=1..nops(L) );
end:


# ------------------------------------------------------------
# Q2. PIEgD(n,L,t) = sum_{i=1..n} t^NumberOfProperties(n,L,i)
# ------------------------------------------------------------

PIEgD := proc(n, L, t) local i;
  add( t^NumberOfProperties(n, L, i), i=1..n );
end:


# ------------------------------------------------------------
# (From C9) IntL(L): intersection of a list of sets
# ------------------------------------------------------------
IntL := proc(L) local i;
  `intersect`(seq(L[i], i=1..nops(L))):
end:


# ------------------------------------------------------------
# (From C9) PIEg(n,L,t): weight enumerator via Inclusion-Exclusion
# ------------------------------------------------------------

PIEg := proc(n, L, t) local k, cu, S, s;
  cu := n:
  for k from 1 to nops(L) do
    S := choose(L, k):
    cu := cu + (t-1)^k * add(nops(IntL(s)), s in S):
  od:
  expand(cu):
end:


# ------------------------------------------------------------
# Q3. Test that PIEg(n,L,t) = PIEgD(n,L,t) five times
# ------------------------------------------------------------

Q3 := proc() local j, n, L;
  n := 1000:
  for j from 1 to 5 do
    L := RandL(n,4):
    print(j, evalb( expand(PIEg(n,L,t) - PIEgD(n,L,t)) = 0 )):
  od:
end:

# output:
# 1, true
# 2, true
# 3, true
# 4, true
# 5, true


# ------------------------------------------------------------
# Q4 Implement the bijective proof (Garsia–Milne)
# ------------------------------------------------------------

# Setting:
# Universe U = {1,...,n}.
# L = [L[1],...,L[m]] is a list of subsets of U, where membership in L[j] means
# "element has property j".
#
# Define PropOf(a) = { j : a in L[j] }.
# Consider pairs (a,J) where J is any subset of PropOf(a).
# Give (a,J) weight (-1)^{|J|}.
# Then the alternating sum over all pairs equals the PIE alternating sum.
#
# Define an involution that toggles the smallest property of a:
# Let s(a) = min(PropOf(a)).
# If s(a) in J, remove it; otherwise add it.
# This flips parity, so pairs cancel in +/- pairs.
# Fixed points occur exactly when PropOf(a)=empty (no properties),
# leaving only (a, emptyset). Therefore the alternating sum equals the
# number of elements with no properties.

# PropOf(n,L,a): set of property-indices j such that a is in L[j]
PropOf := proc(n, L, a) local j;
  { seq(j, j=1..nops(L) if member(a, L[j])) };
end:

# AllSubs(P): all subsets of a set P (returned as a set of sets)
AllSubs := proc(P) local k, out;
  out := {}:
  for k from 0 to nops(P) do
    out := out union choose(P,k):
  od:
  out:
end:

# GMmap(n,L,a,J): parity-changing involution on pairs (a,J)
GMmap := proc(n, L, a, J) local P, s;
  P := PropOf(n, L, a):
  if nops(P)=0 then
    RETURN([a, J]):   # fixed only when J = {}
  fi:
  s := min(P):
  if member(s, J) then
    RETURN([a, J minus {s}]):
  else
    RETURN([a, J union {s}]):
  fi:
end:

# AlternatingSumByPairs(n,L): sum_{a in U} sum_{J subset Prop(a)} (-1)^{|J|}
AlternatingSumByPairs := proc(n, L) local a, P, subs, J, tot;
  tot := 0:
  for a from 1 to n do
    P := PropOf(n, L, a):
    subs := AllSubs(P):
    for J in subs do
      tot := tot + (-1)^nops(J):
    od:
  od:
  tot:
end:

# NoPropertyCount(n,L): number of a in U with PropOf(a)=empty
NoPropertyCount := proc(n, L) local a;
  add( `if`(nops(PropOf(n,L,a))=0, 1, 0), a=1..n ):
end:

# CheckBijection(n,L): verifies the bijective proof numerically
CheckBijection := proc(n, L)
  evalb( AlternatingSumByPairs(n,L) = NoPropertyCount(n,L) ):
end:

# Example run for the optional challenge:
# n := 100:
# L := RandL(n,4):
# CheckBijection(n,L);   # return true


# End of hw9JikeLiu.txt