Results 1 to 5 of 5

Math Help - 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,517
    Thanks
    771
    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.
    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 |\{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,517
    Thanks
    771
    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<j\le n, 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...
    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 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.
    Last edited by Shanks; January 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: July 20th 2010, 08:00 AM
  3. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 12:36 AM
  4. IEEE floating point arithmetic
    Posted in the Math Software Forum
    Replies: 1
    Last Post: March 13th 2009, 02:18 PM
  5. Replies: 3
    Last Post: February 20th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum