#OK to post homework
#Wanying Rao, 01/23/2021, assignment 1

Help := proc(): print(`FP(pi), RandAlmostDer(n,k), EstimateAveFP(n,K), EstimateMomFP(n,r,K)`): end:

with(combinat):


#FP(pi): Inputs a permutation pi of {1,…,n} and outputs the number of fixed points

FP := proc(pi) local i,s:
s := 0:
for i from 1 to nops(pi) do 
if pi[i] = i then s := s+1: fi:
od:
RETURN(s):
end:


#RandAlmostDer(n,k): Inputs positive integers n,k and outputs a random permutation 
#whose number of fixed points is <=k

RandAlmostDer := proc(n,k) local pi:
pi := randperm(n):
while FP(pi)>k do
pi := randperm(n):
od:
pi:
end:


#EstimateAveFP(n,K): Inputs a positive integer n and a large positive integer K and
#outputs the average number of fixed points

EstimateAveFP := proc(n,K) local pi,s,i:
s := 0:
for i from 1 to K do
pi := randperm(n):
s := s+FP(pi):
od:
RETURN(s/K):
end:


#The exact value of the average is 1.
#Pick one permutation pi from all permutations of {1,...,n}. 
#If pi[i]=i, it contributes 1 to the value of FP.
#And there are (n-1)! permutations with i as a fixed point.
#ave = (1/n!)*\sum_{i=1}^{n} (n-1)!
#    = 1


#EstimateMomFP(n,r,K): Inputs positive integers n,r,K and outputs the average number of #FP(pi)^r

EstimateMomFP := proc(n,r,K) local pi,s,i:
s := 0:
for i from 1 to K do
pi := randperm(n):
s := s+FP(pi)^r:
od:
RETURN(s/K):
end:

#My Guess (Don't have a proof yet): the exact value of the average of FP(pi)^2 is 2.