I have not tried all the way though, but here is a way to start. Let for any . Note that . Now, . It is easy to see that does not depend on itself, but only on , so the last sum is equal to . Both of these factors are easy to compute.
WE mark:
* For every function f:A-->A we mark fix(f):={a in A|f(a)=a} all sets of fix points of f.
* In S_n we mark all the sets of permutations on {1,2,3,...,n}
* In T_n we mark all functions f:{1,2,3,...,n}-->{1,2,3,...,n}.
Questions:
1. How many fix points in arithmetic mean there is to function f:{1,2,3,...,n}-->{1,2,3,...,n}?
In other words, compute the {sigma{ f in T_n, |fix(f)|}}/|T_n|
a. Compute top of fraction with changing order of sum.
b. Compute top of fraction with using Newton's binomial formula.
2. Compute:
sigma{( f in S_n, |fix(f) ) CHOOSE 2}
first, here is a different problem:
how many permutations in are there which has fix points?
second, to compute , we can consider the derivative of . expand the bracket, find the derivative and then let x=1, we get
.