Results 1 to 5 of 5

Thread: Fix point (arithmetic mean)

  1. #1
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    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}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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$.
    Last edited by Shanks; Jan 6th 2010 at 09:44 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: May 16th 2011, 04:57 AM
  2. Replies: 9
    Last Post: Jul 20th 2010, 08:00 AM
  3. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Oct 8th 2009, 12:36 AM
  4. IEEE floating point arithmetic
    Posted in the Math Software Forum
    Replies: 1
    Last Post: Mar 13th 2009, 02:18 PM
  5. Replies: 3
    Last Post: Feb 20th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum