# OK to post homework
# Lucy Martinez, 02-20-2026, Assignment 9

with(combinat):


# Question 1:
# Write a procedure NumberOfProperties(n,L,i)
#  that inputs a positive integer n, a list of subsets, L, of {1, ..., n},
#  and a member of {1, ...,n} and outputs the number of sets in L such that i belongs to them.
#  For example NumberOfProperties(4,[{1,3},{2,4},{3,4}],1)=1,
#   NumberOfProperties(4,[{1,3},{2,4},{3,4}],2)=1,
#   NumberOfProperties(4,[{1,3},{2,4},{3,4}],3)=2, 
#   NumberOfProperties(4,[{1,3},{2,4},{3,4}],4)=2
NumberOfProperties:=proc(n,L,i) local co, s:
co:=0:
for s in L do
 if member(i,s) then
  co:=co+1:
 fi:
od:
co:
end:




# Question 2:
# Using the above, write a procedure PIEgD(n,L,t)
#  that outputs the sum of t^NumberOfProperties(n,L,i) over all i from 1 to n 
PIEgD:=proc(n,L,t) local i:
add(t^NumberOfProperties(n,L,i),i=1..n):
end:




# Question 3:
# Test that PIEg(n,L,t)=PIEgD(n,L,t) by doing 5 times
#  L:=RandL(1000,4): evalb(PIEg(1000,L,t)=PIEgD(1000,L,t)); 
# ANSWER: Yes, they agree


# Question 4:
# Implement the bijective proof in this nice article:
#  https://sites.math.rutgers.edu/~zeilberg/mamarimY/gmDG.pdf


##################################
### From previous class:
# C9.txt, Feb. 19, 2026

Help9:=proc():
 print(`RandL(n,k), PIEd(n,L), IntL(L), PIE(n,L), dn(n) `):
 print(`PIEg(n,L,t), dnt(n,t)`):
end:

#Notes:
# Let X be a universal set
# a finite collection of subsets A1, A2, ..., Ak
# How many members of X belong to none of A1, A2, ..., Ak?
# In computer language:
# Not A1 interset Not A2 intersect Not A3 intersect ... intersect Not Ak
# |X|-|A1|

# First we exclude people that like #1, people that like #2, but we excluded the same
# people that like #1 and #2
# The following is Principle of inclusion/exclusion (PIE) for two subsets
# |X|-|A1|-|A2| + |A1 intersect A2|

# For three subsets: Let "*" mean "intersect"
# |X|-|A1|-|A2|-|A3| + |A1*A2| + |A1*A3| + |A2*A3|-|A1*A2*A3|

# In general: in what follows, "*" means multiplication
# |Not A1 intersect Not 2 ... intersect Not Ak| =
#           Sum((-1)^|S|*|Int(s, s in S), all subsets of {A1,A2,...,Ak}|, S)

#RandL(n,k): A random list of subsets of {1,2,...,n} of length k
RandL:=proc(n,k) local i:
[seq(randcomb(n,rand(2..n-2)()),i=1..k)]:
end:


#PIEd(n,L): What PIE computes but done directly
PIEd:=proc(n,L) local i, s:
nops({seq(i,i=1..n)} minus {seq(op(L[i]),i=1..nops(L))}):
end:


#IntL(L): given a list of sets, outputs the intersection of those sets
IntL:=proc(L) local i:
`intersect`(seq(L[i],i=1..nops(L))):
end:


#PIE(n,L): using the formula PIE
PIE:=proc(n,L) local k,cu,S,s:
cu:=n:
for k from 1 to nops(L) do
 S:=choose(L,k):
 cu:=cu+(-1)^k*add(nops(IntL(s)),s in S):
od:
cu:
end:


#Using PIE, find a formula for the number of derangements
# Def: A derangement is a permutation that has no fixed points
# i.e. pi[1]<>1, pi[2]<>2, ... , pi[n]<>n
#Universal set: all the permutations i.e. n!
# What is a natural choice for A[1]? 
#  A[1]= set of permutations that have a fixed point at the first location:
#  For example: if n=3 then A[1]={[1,2,3], [1,3,2]}
#   A[2]={[1,2,3],[3,2,1]} and A[3]={[1,2,3],[2,1,3]}
# In general:
# A[i]:=set of permutations such that pi[i]=i
# Lemma: for any subset S of k properties
# nops( A[S[1]] intersect A[S[2]] ... intersect A[S[k]] )= (n-k)!
#  i.e. (n-k)! counts the number of permutations with k fixed pts
# Now, in how many ways can you choose k members of A[1],...,A[n]? 
# Sum(binomial(n,k)*(-1)^k*(n-k)!,k=0..n)=Sum( n!/((n-k)!*k!)*(-1)^k*(n-k)!,k=0..n)=
# Sum(n!/k!*(-1)^k,k=0..n)

#dn(n): returns the number of permutations that have no fixed points
# i.e. the number of derangements of length n
dn:=proc(n) local k:
n!*add((-1)^k/k!,k=0..n):
end:


#PIEg(n,L,t): The weight-enumerator of the members of the universal set
# according to t^NumberOfProperties
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:


#dnt(n,t): returns the weight-enumerator of permutations according to
# t^#NumberOfDerangements
dnt:=proc(n,t) local k:
expand(n!*add((t-1)^k/k!,k=0..n)):
end: