Open in CoCalc

Here is some code for analyzing the questions raised in your first Sage homework.

#############################
# 1. Average number of cycles
#############################
# we will look at SymmetricGroup(n) for various values of n
nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:

G = SymmetricGroup(n)
total = 0 # sum of cycle lents
for _ in range(nTrials):
t = G.random_element()
tc = t.cycle_tuples()
total += len(tc) #add to total
avg = float(total/nTrials)  #compute average
averageCycleLengths.append(avg) #store average in list
# now print results
print n, avg


5 1.256 10 1.892 20 2.562 50 3.358 100 4.362 200 5.07 1000 6.516
# It looks vaguely logarithmic, as Sarah M. observed.

#############################
# 2. Probability of derangement
#############################

# A permutation is a derangement if it has no fixed points.  So we need a fixed point calculator function
def nFixedPts(perm,n):
#it is understood that perm is an element of SymmetricGroup(n)
nFP=0 #this is the output which we will iterate
for i in [1..n]:
if perm(i)==i:
nFP += 1
return nFP

# Now we do the same statistical analysis with the same values of n as in the previous problem
nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:
G = SymmetricGroup(n)
total = 0 # the number of derangements
for _ in range(nTrials):
t = G.random_element()
if nFixedPts(t,n)==0: #a derangement!
total += 1
avg = float(total/nTrials)  #compute fraction of derangements

# now print results
print n, avg

5 0.39 10 0.338 20 0.362 50 0.382 100 0.356 200 0.394 1000 0.37
# Notice the surprising fact that the fraction of permutations that are derangements appears to be around 0.38 or so, independent of n!


#############################
# 3. average number of fixed points
#############################

#we already have the fixed point calculator function, so we can just apply it using virtually the same code.

nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:
G = SymmetricGroup(n)
total = 0 # the sum of number of fixed points
for _ in range(nTrials):
t = G.random_element()
total += nFixedPts(t,n)
avg = float(total/nTrials)  #compute average number of fixed points

# now print results
print n, avg

5 1.034 10 1.028 20 0.94 50 1.024 100 1.036 200 0.978 1000 0.926
# Once again, a surprising result:  the average number of fixed points seems to be 1, no matter what n is!