# Fix point (arithmetic mean)

• Jan 2nd 2010, 04:46 AM
Also sprach Zarathustra
Fix point (arithmetic mean)
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}
• Jan 5th 2010, 08:21 AM
emakarov
I have not tried all the way though, but here is a way to start. Let $N_n=\{1,\dots,n\}$ for any $n$. Note that $\sum_{f\in T_n}|\text{fix}(f)|=\sum_{i=1}^n i\cdot\big|\{f\in T_n:|\text{fix}(f)|=i\}\big|$. Now, $\big|\{f\in T_n:|\text{fix}(f)|=i\}\big|=\sum_{A\subseteq N_n,|A|=i}|\{f\in T_n:\text{fix}(f)=A\}|$. It is easy to see that $|\{f\in T_n:\text{fix}(f)=A\}|$ does not depend on $A$ itself, but only on $|A|$, so the last sum is equal to $|\{f\in T_n:\text{fix}(f)=N_i\}|\cdot|\{A\subseteq N_n:|A|=i\}|$. Both of these factors are easy to compute.
• Jan 5th 2010, 11:57 PM
Shanks
emakarov, I totally agree with what you posted.
But the $|\{f\in T_n:\text{fix}(f)=N_i\}|$ is not that easy to compute as you imagine when n is larger number.
• Jan 6th 2010, 01:23 AM
emakarov
Well, if $fix(f)=N_i$, then $f(1),\dots,f(i)$ are fixed, while $f(i+1),\dots,f(n)$ can be anything different from the argument. So for $i, there are $n-1$ options for $f(j)$. Therefore, the number of such functions is $(n-1)^{n-i}$, isn't it?

I don't know right away how to compute the sum $\sum_{i=1}^n i{n\choose i}(n-1)^{n-i}$, though...
• Jan 6th 2010, 02:54 AM
Shanks
first, here is a different problem:
how many permutations in $S_n$ are there which has $i,i=0,1,...n$ fix points?
second, to compute $\sum_{i=1}^n i{n\choose i}(n-1)^{n-i}$, we can consider the derivative of $(x+(n-1))^n$. expand the bracket, find the derivative and then let x=1, we get
$\sum_{i=1}^n i{n\choose i}(n-1)^{n-i}=n^n$.