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

• Interesting. Just as a check on whatever the final answer is, I computed it in Mathematica, and as long as I didn't make a mistake there, the answer should be $756$. Apr 7, 2021 at 21:29

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]


• can this question be solved using recursion? I gave it a thought but could not proceed Feb 13, 2023 at 6:11

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;

}