#C2.txt: Maple code for Lecture 2 of Experimaental Mathematics (Rutgers Univ. Spring 2021) by Dr. Z.
Help2:=proc(): print(` FP(pi) , MomFP(n,k), MyPS(S), Box(L)  `):
end:

with(combinat):

#FP(pi): Inputs a permutation pi of {1,...n}, (where n=nops(pi)) and outputs an integer
#between 0 and n indicating the number of fixed points, i.e. the number of places i such that
#pi[i]=i. Note that if pi is a derangement, then FP(pi)=0.
FP:=proc(pi) local n,i,f:

n:=nops(pi):
f:=0:

for i from 1 to n do
 if pi[i]=i then
  f:=f+1:
 fi:
od:
f:

end:




#MomFP(n,k): Inputs a positive integer n and outputs the EXACT (not approximate)
#value of the average of the k-th power of FP(pi) over all permutations
MomFP:=proc(n,k) local S,pi:S:=permute(n):add(FP(pi)^k, pi in S)/nops(S):end:

#MyPS(S): Inputs a set S and outputs the powerset of S, i.e. the set of all
#subsets  of S
MyPS:=proc(S) local s,S1,PS1,s1:

if not type(S,set) then
print(S, `should be a set `):
 RETURN(FAIL):
fi:

if S={} then
 RETURN({{}}):
fi:

s:=S[nops(S)]:

S1:=S minus {s}:

PS1:=MyPS(S1):

PS1 union { seq( s1 union {s}, s1 in PS1)}:

end:

#Box(L): Inputs a list L (where k=nops(L)) of non-negative integers L outputs
#the  LIST of all LISTS [a1,a2,..., ak] in LEX ORDER such that ai is in {0,1,.., L[i])
#In particular the n-dim UNIT cube would be Box([1$n]);
Box:=proc(L) local k,i,L1,B1,b1:
option remember:

if not type(L,list) then
  print(L, `should be a list `):
 RETURN(FAIL):
fi:

k:=nops(L):
if k=0 then 
 RETURN([[]]):
fi:
 if not ({seq(type(L[i],integer),i=1..nops(L))}={true} and min(op(L))>=0) then
   print(`bad input`):
  RETURN(FAIL):
 fi:




L1:=[op(1..k-1,L)]:

B1:=Box(L1):
 [ seq(seq([op(B1[j]),i],i=0..L[k]),j=1.. nops(B1))]:
end:



 





###From C1.txt
#C1.txt: Maple Code for ExpMath Spring 2021

Help1:=proc(): print(` LC(p) , IsDer(pi), RandPer(n) `): end:

#LC(p): Inputs a RATIONAL number p and outputs a pseudo-random number
#1 with probability p and 2 with probability 1-p
LC:=proc(p) local m,n,r:

if not ( type(p,numeric) and p>=0  and p<=1) then
 RETURN(FAIL):
fi:

if p=0 then
 RETURN(2):
fi:

if p=1 then
 RETURN(1):
fi:

if not type(p,fraction) then
 RETURN(FAIL):
fi:

m:=numer(p):
n:=denom(p):
r:=rand(1..n)():

if r<=m then
  1:
else
 2:
fi:

end:


#DEF: A derangement of {1, ...,n} is a permutation such that pi[i]<>i for every i
#IsDer(pi): inputs a permutation of {1,...,n} pi (n=nops(pi))
#and outputs true iff it is a derangement
IsDer:=proc(pi) local n,i:
n:=nops(pi):
for i from 1 to n do
 if pi[i]=i then
    RETURN(false):
 fi:
od:
true:
end:

#RandDer(n): Generates a random derangement using the NAIVE approach suggested by
#Alon Itai in his not entirely-raving Math review of the Nijenhuius-Wilf classic
RandDer:=proc(n) local pi:

pi:=randperm(n):

while  not IsDer(pi) do
pi:=randperm(pi):
od:
pi:
end:
#END C1.txt