#M5.txt: Maple Code for Lecture 5 of Math 454,Combinatorics, Rutgers University, taught by Dr. Z. (Doron Zeilberger)
Help5:=proc():print(` RSS(n,k,l), PIE(U,L), FP(pi), Pnx(n,x)  `): end:

with(combinat):

#RSS(n,k,l): A random set of size  k of subsets of {1,...,n} each of about size l
RSS:=proc(n,k,l) local ra,i,j:
ra:=rand(1..n):
{seq({seq(ra(),i=1..l)},j=1..k)}:
end:


#PIE(U,L): inputs a universal set and a list of subsets L, computes
#the cardianltiy of the intersection of U\L[i] in two different ways
#(i) directly (ii) by the Principal of Inclusion-Exclusion
#Try:
#PIE({1,2,3,4,5},{{1,2,3},{5}});
PIE:=proc(U,L) local a,b,i,SS,s:
a:=nops(`intersect`(seq(U minus L[i],i=1..nops(L)))):

SS:=powerset(L) minus {{}}:

b:=nops(U):

for s in SS do
 b:=b+(-1)^nops(s)*nops(`intersect`(op(s))):
od:

[a,b]:
end:

#FP(pi): The number of fixed-points of the permutation pi
FP:=proc(pi) local i:
coeff(add(evalb(pi[i]=i),i=1..nops(pi)),true,1):
end:


#Pnx(n,x): The polynomial in x of degree n whose coefficients of x^i is the number of permutations with exactly i fixed points. 
#Computed directly
#Try:
#Pnx(5,x);
Pnx:=proc(n,x) local S,pi:
S:=permute(n):
add(x^FP(pi),pi in S):
end:


#PnxF(n,x): The same as Pnx(n,x) computed via the formula that uses the Principle of Inclusion-Exclusion
#Try:
#PnxF(5,x);
PnxF:=proc(n,x) local k:
expand(add(binomial(n,k)*(x-1)^k*(n-k)!,k=0..n)):
end: