# This program chooses a random permutation sigma of the
# numbers from 1 to n and counts the number of fixed points 
# (i.e., values of i so that sigma(i) = i) of that permutation.
# The function makehist(n,count) runs count trials of
# the process and then tabulates the distribution. Finally, we
# print the average number of fixed points. What do you think
# the true answer is?

import random

def fixedpoints(n):
    x = range(n)
    random.shuffle(x)
    fp = 0
    for i in range(n):
        if x[i] == i:
            fp += 1
    return fp

def makehist(n, count):
    histcount = {}
    for _ in range(count):
        b = fixedpoints(n)
        if b in histcount:
            histcount[b] += 1
        else:
            histcount[b] = 1
    keys = [i for i in histcount]
    keys = sorted(keys)
    hist = [(key, histcount[key]) for key in keys]
    return hist

hist = makehist(100,1000)
print hist
print sum(key[0]*key[1] for key in hist)/1000.