Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By johnsomeone

Thread: Flat functions on a finite set

  1. #1
    Member
    Joined
    Sep 2012
    From
    Planet Earth
    Posts
    217
    Thanks
    56

    Flat functions on a finite set

    Let X be a set such that |X|= n, where n is a positive integer. Call a function f: X -> X flat if some iterate of it is constant.

    For example, if f^{(2)}(x) denotes f(f(x)), and f^{(3)}(x) denotes f(f(f(x))), a function is flat if there exists a positive integer k such that f^{(k)}(x) is a constant function on X.

    In terms of n, how many flat functions are there on X?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: Flat functions on a finite set

    Nice problem. I get that the answer is n^{n-1}. (That checks for n = 1, 2, 3, 4 by looking at the corresponding cases in Rooted Tree -- from Wolfram MathWorld )

    The idea is:

    the set of flat functions on X

    (1) is bijective with

    the set of labelled digraph trees on n vertices having the property that their induced poset contains a maximum element

    (2) is bijective with

    the set of rooted labelled trees on n vertices

    (3) is bijective with

    X cross the set of labelled trees on n vertices.

    The bijection for (1) is f \leftrightarrow D_f where the digraph D_f is given by V(D_f) = X, E(D_f) = \{ (x, f(x)) \in V(D_f) \times V(D_f) \ : \ x \in X-\{a_f\} \},

    where a_f \in X which is the eventual constant value of f, the labelling is given by vertex, and the maximum element property is just a restatement of the flatness of the function.

    The bijection for (2) is just by setting the root equal to the maximum element, and conversely, given the root, directing the edges so that they flow towards it. And the labelling just carries over.

    The bijection for (3) is just by using that rooted labelled trees are nothing more than labelled trees with a choice of a single vertex.

    Then use that the count of labelled trees on n vertices is given by by Cayley's formula, n^{n-2}.

    Thus the cardnality of X cross the set of labelled trees on n vertices is just (n)(n^{n-2}) = n^{n-1}.
    Last edited by johnsomeone; Jul 8th 2015 at 04:14 PM.
    Thanks from SworD
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2012
    From
    Planet Earth
    Posts
    217
    Thanks
    56

    Re: Flat functions on a finite set

    Yes, that was exactly the same solution I used. Congrats!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: May 28th 2013, 07:40 PM
  2. Finite Difference of Polynomial Functions..
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: Aug 9th 2009, 05:17 PM
  3. Replies: 1
    Last Post: Mar 25th 2009, 10:09 PM
  4. Flat
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Jun 29th 2008, 09:20 AM
  5. Replies: 5
    Last Post: May 11th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum