# Thread: Flat functions on a finite set

1. ## 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?

2. ## 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}$.

3. ## Re: Flat functions on a finite set

Yes, that was exactly the same solution I used. Congrats!