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!