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 $\displaystyle N_n=\{1,\dots,n\}$ for any $\displaystyle n$. Note that $\displaystyle \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, $\displaystyle \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 $\displaystyle |\{f\in T_n:\text{fix}(f)=A\}|$ does not depend on $\displaystyle A$ itself, but only on $\displaystyle |A|$, so the last sum is equal to $\displaystyle |\{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 $\displaystyle |\{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 $\displaystyle fix(f)=N_i$, then $\displaystyle f(1),\dots,f(i)$ are fixed, while $\displaystyle f(i+1),\dots,f(n)$ can be anything different from the argument. So for $\displaystyle i<j\le n$, there are $\displaystyle n-1$ options for $\displaystyle f(j)$. Therefore, the number of such functions is $\displaystyle (n-1)^{n-i}$, isn't it?

I don't know right away how to compute the sum $\displaystyle \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 $\displaystyle S_n$ are there which has $\displaystyle i,i=0,1,...n$ fix points?
second, to compute $\displaystyle \sum_{i=1}^n i{n\choose i}(n-1)^{n-i}$, we can consider the derivative of $\displaystyle (x+(n-1))^n$. expand the bracket, find the derivative and then let x=1, we get
$\displaystyle \sum_{i=1}^n i{n\choose i}(n-1)^{n-i}=n^n$.