Help:=proc(): print(` PIE(S,P), TestPIE(N,M,k)` ):
print(`RandSS(), Bonn(S,P,r)`): 

end:

with(combinat):

#inputs a set of objects S and
#a list of properties P 
#[S1,S2, ..., Sk] checks the Principle
#of Inclusion Exclusion
#|(1-S1)(1-S2)...(1-Sk)|=|S|-|S1|-|S2|-...
#+|s1 intersect S2|+....
#Sum(T Subset of {1, ..., k}, (-1)^|T| *|S_T|)
#For example:
#PIE({Daniela,Michael, Emilie,Aron},[{Daniela, Emilie},
#{Daniela, Aron}]=1
PIE:=proc(S,P) local k,PP,T,i:
k:=nops(P):
PP:=powerset(k) minus {{}}:

nops(S)+
add((-1)^nops(T)*
nops(`intersect`(seq(P[i], i in T) ) ) , T in PP),
nops(S minus `union`(seq(P[i],i=1..k))):



end:



#RandSS(S): generates a random subset of S
#where each element has prob. 1/2
RandSS:=proc(S) local aron,i,s,S1:
aron:=rand(0..1):
S1:={}:
for s in S do
 if aron()=1 then
    S1:=S1 union {s}:
 fi:
od:
S1:

end:

#picks a random N-element set with pos. integers
#<=M, and k random subsets  and tests
#PIE for it
TestPIE:=proc(N,M,k) local S,P,ra,i, aron,kellen:

ra:=rand(1..M):

S:={seq(ra(),i=1..N)}:

P:=[seq(RandSS(S),i=1..k)]:

kellen:=PIE(S,P):
evalb(kellen[1]=kellen[2]):



end:


#inputs a set of objects S and
#a list of properties P 
#[S1,S2, ..., Sk] checks the 
#Bonferroni inequality
#of Inclusion Exclusion
#|(1-S1)(1-S2)...(1-Sk)|<= (>=0) |S|-|S1|-|S2|-...
#+|s1 intersect S2|+....
#Sum(|T|<=r, (-1)^|T| *|S_T|)
#For example:
#PIE({Daniela,Michael, Emilie,Aron},[{Daniela, Emilie},
#{Daniela, Aron}]=1
Bonn:=proc(S,P,r) local k,T,i:
k:=nops(P):


nops(S)+
add(
(-1)^r1*
add(nops(`intersect`(seq(P[i], i in T) ) ) , 
T in choose(k,r1)) ,  
r1=1..r),
nops(S minus `union`(seq(P[i],i=1..k))):

end: