Number of functions such that $f(f(f(x)))=f(f(x))$ 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?
 A: 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]


A: 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;

}

