# 3.

FP := proc(pi)
    add(ifelse(pi[k] = k, 1, 0), k=1..nops(pi)):
end:

# 4.

with(combinat):

RandAlmostDer := proc(n, k)
    local pi:

    pi := randperm(n):

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

    pi:
end:

# 5 / 7. Estimate FP(pi)^r for k randomly chosen permutations pi.
EstimateAveFPr := proc(n, r, k)
    evalf(add(FP(randperm(n))^r, j=1..k) / k):
end:

# 6.

(*
    Doing EstimateAveFPr(n, 1, 1000) for different values of n seems to produce
    a number somewhere around 1. So, I conjecture that it *is* 1. (This fact
    sounds familiar.)

    How do we prove this? One way is to use some group theory, but I remember
    that whatever theorem I'm thinking of is actually a simple idea.

    What is the average number of fixed points?

        A(n) = sum(FP(p), p) / n!.

    The key observation is that

        FP(p) = sum([p(k) = k], 1 <= k <= n),

    so we actually have a double sum:

        n! A(n) = sum([p(k) = k], p, 1 <= k <= n)
                = sum(sum([p(k) = k], p), 1 <= k <= n).

    The inner sum counts how many permutations on n-letters fix k, which is (n
    - 1)!. Therefore

        n! A(n) = n * (n - 1)! = n!,

    giving A(n) = 1.

*)

# 7.

(*

    Using the same idea as before, I conjecture that E[Fp(pi)^2] = 2.

    The same proof works!

        n! B(n) = sum(FP(pi)^2, p)
                = sum(sum([p(k) = k], 1 <= k <= n)^2, p)
                = sum(sum([p(k) = k], k) + sum([p(k) = k, p(j) = j], k != j), p)
                = n! + sum(sum([p(k) = k][p(j = j)], p), k != j)
                = n! + n (n - 1) (n - 2)!
                = 2n!

    Thus B(n) = 2. (For n sufficiently large, I suppose. Probably n >= 2.)

    This gets too messy to generalize.

    Let M(n, r) be E[FP(pi)^r] where pi is a permutation on n letters.

    Conjectures:

        M(n, 1) = 1 (proven)
        M(n, 2) = 2 (proven)
        M(n, 3) = 5 (?)
        M(n, 4) in [14, 15] (?)

    I conjecture maybe M(n, r) = the rth Bell number for sufficiently large n.
    Some googling convinces me that this is true, but I don't want to think
    about a proof right now.
*)

M := proc(n, r)
    p := firstperm(n):
    s := 0:
    while p <> FAIL do
        s := s + FP(p)^r:
        p := nextperm(p):
    od:

    s / n!:
end: