#OK to post homework
#George Spahn, 1/24/2021, Assignment 1

#FP(pi): inputs a permutation of {1,...,n} pi (n=nops(pi))
#and outputs the number of fixed points
FP:=proc(pi) local n,m,i:
n:=nops(pi):
m:=0:
for i from 1 to n do
 if pi[i]=i then
    m:=m+1
 fi:
od:
m:
end:


#RandAlmostDer(n,k): Generates a random permutation with at most k fixed points
RandAlmostDer:=proc(n,k) local pi:

pi:=randperm(n):

while FP(pi) > k do
pi:=randperm(pi):
od:
pi:
end:

#EstimateAveFP(n,K): Estimates the average number of fixed points of a 
#permutation of length n using K random samples.

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

#My guess is that the exact value for the average number of fixed points is 1.
#Proof:
#The random variable for the number of fixed points is the sum of indicator 
#variables for each element 1,2...n, that take the value 1 iff that
#element is fixed. Each indicator variable has expectation 1/n. The sum of 
#them thus has expectation 1/n * n = 1 by linearity of expectation.

#EstimateMomFP(n,r,K): Estimates the average of FP(pi)^r
EstimateMomFP:=proc(n,r,K) local i,pi,sum:
sum:=0:
for i from 1 to K do
pi:=randperm(n):
sum:=sum+FP(pi)^r:
od:
sum/K:
end:

#My guess is that the exact value for the average of FP(pi)^2 is 2.
#Proof:
#Again write it out as the sum of indicator values and then distribute the
#product. Break up the sum into sum x_i^2 + sum x_ix_j.
#Expectation of sum x_i^2 = expectation of sum x_i = 1.
#Expectation of sum x_ix_j = n(n-1) * expectation x_ix_j.
#Expectation x_ix_j is the probability that i and j are fixed. 1/n that i 
# is fixed, times 1/(n-1) that j is fixed given that i is also fixed.
# 1 + n(n-1) * 1/n *1/(n-1) = 2