Number of functions such that $f(f(f(x)))=f(f(x))$

Question

If $A=\left\{1,2,3,4,5\right\}$, then find the number of functions satisfying $$f(f(f(x)))=f(f(x)), \forall x \in A \to (1)$$ Related: Number of functions satisfying $f(f(x))=f(x)$.

I actually took the help from the thread above and tried as follows: From $1$ we see that if $y \in \operatorname{im}(f)$, then $$f(f(y))=f(y) \to (2).$$ Now consider the following cases:

Case $1.$ If $\operatorname{im}(f)$ contains only one element, then trivially its a constant function and satisfies $(1)$. Number of such functions is $\binom{5}{1}=5$.

Case $2.$ Let $\operatorname{im}(f)$ contains only two elements. WLOG let us assume $\operatorname{im}(f)=\left\{1,2\right\}$

From $(2)$ we have $$f(f(1))=f(1), f(f(2))=f(2)$$ $\implies$ $$f(f(f(1)))=f(f(1)), \:f(f(f(2)))=f(f(2))$$

Now if $f(1)=2$ then it implies $f(2)=2$ and let $f(3)=1, f(4)=2,f(5)=2$, then we have $$f(f(f(3)))=2=f(f(3))$$ $$f(f(f(4)))=2=f(f(4))$$ $$f(f(f(5)))=2=f(f(5))$$ So definitely this is one of the function which satisfies the hypothesis. But how to count number of such functions? What about the upcoming cases?

Answer 1

Assume the set is $\{1,\dots,n\}$. Define the resistance of an element as the lowest $k$ such that $f^k(x) = f^{k+1}(x)$, We require that each element has resistance $0,1$ or $2$.

How many such functions exist with $a$ elements of resistance $0$ and $b$ elements of resistance $1$?

There are $\binom{n}{a,b,n-a-b}$ ways to select the elements of resistance $0,1$ and $2$.

Then there are $a^b$ ways to assign $f(x)$ for every element of resistance $1$, and there are $b^{n-a-b}$ ways to assign $f(x)$ for every element of resistance $2$.

Therefore we have that the number of functions is equal to $$\sum\limits_{i=1}^n\sum\limits_{j=0}^{n-i}\binom{n}{a,b,n-a-b} a^b b^{n-a-b}$$

Looking at OEIS we get https://oeis.org/A000949 where the same formula is provided.

The following C++ code evaluates this for $n=5$ and give 756.

#include<iostream>
using namespace std;

const int MAX = 10;
int F[MAX];

long long pot(long long b, long long e){//calculate b^e
        long long res = 1;
        while(e){
                if(e%2) res = res*b;
                b=b*b;
                e/=2;
        }
        return res;
}

int main(){
        F[0] = 1;
        for(int i=1;i<MAX;i++){
                F[i] = F[i-1]*i;
        }
        int n = 5;
        long long res = 0;
        for(int a=0;a<=n;a++){
                for(int b=0;a+b <= n;b++){
                        res += pot(a,b)*pot(b,n-a-b)*(F[n]/F[a]/F[b]/F[n-a-b]);
                }
        }
        cout << res << endl;

}

Brute force checker:

#include<iostream>
using namespace std;

const int n = 5;
int f[n];

int next(){
        for(int i=n-1;i>=0;i--){
                if( f[i]+1 < n ){
                        f[i]++;
                        for(int j=i+1;j<n;j++){
                                f[j] = 0;
                        }
                        return 1;
                }
        }
        return 0;
}

int main(){
        int res = 0;
        int start = 1;
        while( start || next() ){
                start = 0;
                int allgood = 1;
                for(int i=0;i<n;i++){
                        if( f[f[f[i]]] != f[f[i]] ) allgood = 0;
                }
                res += allgood;
        }
        cout << res << endl;

}

Answer 2

We may visualize a function on $A=\{1,2,3,4,5\}$ as a directed graph where each node is an element of $A$, and there is exactly one edge coming out of each element.

The composite of a function with itself may be regarded as the "composite" of these digraphs with each other, where $u\to v$ is in the composite if there is some $x\in A$ with $u \to x$ and $x \to v$. These are the length-two paths in the directed graph. Since each node has exactly one arrow coming out of it, the length-$n$ path starting at any given node is uniquely defined, and we may identify the arrows in $f^{n}$ with the length-$n$ paths in this graph of $f$. (The arrow in the graph of $f^{n}$ coming out of $x$ is the one that goes from $x$ to the final vertex in the length-$n$ path starting from $x$.)

So, we want the functions such that their length-3 paths end at the same place as their length-$2$ paths. This is only possible if all length-$2$ paths end on a vertex that has a self-loop.

So, consider all the functions that have exactly $k$ self-loops. The $2$-paths from these vertices all trivially end in a self loop; there are $5-k$ vertices left to worry about.

There are two cases: either the remaining vertex heads directly to a self-loop, or it heads to a vertex that heads directly to a self-loop. We can choose each of these stages arbitrarily.

Suppose $m \leq 5-k$ vertices head directly to a self loop. There are $k$ choices for each of these, and so $k^m$ choices in general. For the remaining $5-k-m$ vertices, they must all head to one of the $m$ vertices, so there are $m^{5-k-m}$ choices.

There were $\binom{5}{k}$ possible ways to choose a set of $k$ vertices to be self-loops in the first place, and $\binom{5-k}{m}$ ways to choose the set of $m$ vertices that will head directly to self-loops So, the total number of functions is $$\sum_{k=0}^5\sum_{m=0}^{5-k}\binom{5}{k}\binom{5-k}{m}k^m m^{5-k-m}$$ which gives 756, as expected.

Here's the Mathematica code:

(* Evaluate formula: *)

power[0, 0] = 1; power[n_, k_] := n^k

count[n_] := 
 Sum[Sum[Binomial[n, k] Binomial[5 - k, m] power[k, m] power[m, (n - k - m)], {m, 0, n - k}], {k, 0, n}]

count[5]

(* Out: 756 *)

(* Check by enumeration: *)

(* A function is a list of length 5 such that f(n) is the nth element in the list *)

compose[f1_List] := f1

compose[f1_List, f2_List] := f1[[f2]]

compose[f1_List, f2_List, fs__List] := f1[[compose[f2, fs]]]

composepower[f_List, n_Integer] := compose @@ ConstantArray[f, n]

functions = Tuples[Range[5], 5];

Length @ Select[functions, composepower[#, 3] == composepower[#, 2] &]

(* Out: 756 *)

(* Just for fun, draw a graph of a random function: *)

DrawGraph[f_List] := Graph[MapThread[Rule, {Range[Length[f]], f}], VertexLabels -> Automatic]

f0 = RandomInteger[{1, 5}, 5]

DrawGraph[f0]