Number of possible functions satisfying the given conditions I Have to find the number of functions $f(x)$ from {1,2,3,4,5} to {1,2,3,4,5} that satisfy $ f(f(x)) = f(f(f(x)))$ for all $x$ in {1,2,3,4,5}.
However I am unable to understand from where to start. The number of cases I am trying to analyze is too much. I tried classifying it into functions which are onto, which are not unto wherein only 1 image appears twice and so on but I am realising that the list is becoming too huge. Can anyone help me with a simpler analysis of this question.
 A: Permit me to remark on  the connection to Analytic Combinatorics. It
is known that all endofunctions on $[n]$ are sets of cycles of labeled
trees.  This follows from the fact  that when we iterate $f$ we obtain
a path that terminates in a cycle and is documented in Random Mapping
Statistics by P.   Flajolet, where the asymptotics  are then derived.
The      construction     also      appeared     at      this     MSE
link.          The
combinatorial class is then given by
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{F} = \textsc{SET}(\textsc{CYC}(\mathcal{T}))
\quad\text{where}\quad
\mathcal{T} = \mathcal{Z} \textsc{SET}(\mathcal{T}).$$
Now in the present case there can be no cycles of two or more elements
because the  values on those cycles  would not fit the  condition that
$f(f(x)) =  f(f(f(x))).$ This leaves sets  of trees, with the  root of
the tree being  a fixed point.  Observe  that any leaf with  a path to
the root including  the root that contains more than  three nodes also
breaks the requirement that $f(f(x)) = f(f(f(x))).$ This restricts the
class of  trees to those  where the path from  every leaf to  the root
including the root contains at  most three nodes.  Now to characterize
these trees they are first, a  singleton node (fixed point) or second,
a singleton node (also a fixed  point) with a set of subtrees attached
to  it, which  are in  turn  either leaves  or  have a  set of  leaves
attached to them.  With the combinatorial class $\mathcal{T}$ of these
trees we thus obtain
$$\mathcal{T} = \mathcal{Z} + 
\mathcal{Z}\textsc{SET}_{\ge 1}
(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
The desired combinatorial class $\mathcal{F}$ is a forest of these trees
given by
$$\mathcal{F} = \textsc{SET}(\mathcal{T}) = 
\textsc{SET}(\mathcal{Z} + 
\mathcal{Z}\textsc{SET}_{\ge 1}
(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z}))).$$
Observe  that the  distinction  between nodes  that  have no  subtrees
attached to them and  nodes with a set of subtrees  as a feature which
appears during the  study of the problem givens is  not essential here
and we may use the convenient fact that
$$\mathcal{E} + \textsc{SET}_{\ge 1}(\mathcal{Q})
= \textsc{SET}(\mathcal{Q}).$$
We thus have for the class in question that it is
$$\mathcal{F} = 
\textsc{SET}(\mathcal{Z}\textsc{SET}(\mathcal{Z}
\textsc{SET}(\mathcal{Z}))).$$
What is happening here is that for  rooted trees of height at most $h$
we have $\mathcal{T}_{\le 0} = \mathcal{Z}$ and for $h\ge 1$
$$\mathcal{T}_{\le h} = 
\mathcal{Z} \textsc{SET}(\mathcal{T}_{\le h-1}).$$
We instantly obtain the EGF
$$F(z) = \exp(z\exp(z\exp(z))).$$
Extracting coeffficients here we find
$$n! [z^n] F(z) =
n! [z^n] \sum_{q=0}^n \frac{1}{q!} 
z^q \exp(qz\exp(z))
\\ = n! \sum_{q=0}^n \frac{1}{q!} 
[z^{n-q}] \exp(qz\exp(z))
\\ = n! \sum_{q=0}^n \frac{1}{q!} 
[z^{n-q}] \sum_{p=0}^{n-q} \frac{1}{p!} 
q^p z^p \exp(pz)
\\ = n! \sum_{q=0}^n \frac{1}{q!} 
\sum_{p=0}^{n-q} \frac{1}{p!} 
q^p [z^{n-q-p}]  \exp(pz)
\\ = n! \sum_{q=0}^n \frac{1}{q!} 
\sum_{p=0}^{n-q} \frac{1}{p!} 
q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$
This    is    the    formula    that    is    presented    at    OEIS
A000949. Apparently they  chose to simplify
by  omitting the  term for  $q=0$ ($q^p=1$  only when  $p=0$ but  then
$p^{n-q-p} = 0$)  and extracting the term for  $q=n$ (which simplifies
to $1$) to get
$$1 + n! \sum_{q=1}^{n-1} \frac{1}{q!} 
\sum_{p=0}^{n-q} \frac{1}{p!} 
q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$
A: Hint:
If $x=f^2(c)$ for some $c$, then you have $f(x) = x$.
This means that every $x \in \text{Im}(f^2)$ is a fixed point of $f$. Do you think you can conclude?

We can build $f$ as follows.
$\quad\mathbf{(1)}$: $f$ must contain exactly $k$ fixed points in $\{1,2,\dots,5\}$ for some $k$ with $1\leqslant k\leqslant 5$.
$\quad\quad\mathbf{(1.1)}$: If $k=5$, then there is only one possibility: $f$ is the identity.
$\quad \mathbf{(2)}$: For $k<5$, consider the set $S$ of points that are not fixed and that are mapped to one of the $k$ fixed points.
It is not empty, for otherwise we could iterate some non-fixed $x$ under $f$ and find a contradiction with $f^2 = f^3$.
Let $j=|S|$, so that $1\leqslant j\leqslant 5-k$.
$\quad \mathbf{(3)}$: The remaining points, if any, must map to one of the $j$ points in $S$.
Indeed, let $x$ be one such point, and consider $f(x)$.
We have that $f(f(x)) = f^2(x)$ is a fixed point of $f$ $($because $f^2 = f^3)$, so either $f(x)\in S$ or $f(x)$ is itself a fixed point.
The latter would in turn imply either $x\in S$ or else $x$ is itself a fixed point, but we've excluded these possiblities (the 'remaining' points).
We hence have
$$1 + \sum_{k=1}^4\left(\binom{5}{k}\cdot\sum_{j=1}^{5-k}\,\binom{5-k}{j}k^jj^{5-k-j}\right) = 756$$
possibilities.
Let's explain the formula.


*

*The lone $1$ before the summation over $k$ is the identity $\mathbf{(1.1)}$.

*$\binom{5}{k}$ is the number of ways to choose $k$ of the points in $\{1,2,\dots,5\}$ to be fixed.

*$\binom{5-k}{j}$ is the number of ways to choose $j$ of the remaining $5-k$ points to be the points in $\mathbf{(2)}$, which map to fixed points.

*$k^j$ is the number of ways to choose, for each of the $j$ points above, to which of the $k$ fixed points it is mapped.

*$j^{5-k-j}$ is the number of ways to choose, for each of the remaining $5-k-j$ points, to which of the $j$ points in $\mathbf{(2)}$ it is mapped.


Notice that cancellations lead to the formula in Somos's answer, so here's a combinatorial interpretation for it.

It is easy to generalize this procedure for other values of $m$ with $f^m = f^{m+1}$, and this is basically a tiered approach.
For some $x\in\text{Dom}(f)$, let $\text{ord}(x)$ be the smallest non-negative integer $n$ with $f^n(x) = f^{n+1}(x)$, where $f^0(x) = x$.
Then it's easy to check that:


*

*$\text{ord}(x) = 0 \iff f(x) = x$

*$0 < \text{ord}(x) < \infty  \implies \text{ord}(f(x)) = \text{ord}(x) - 1$

*$\text{ord} \leqslant m$


In this way, we can build $f$ from the ground up.
Mimicking the bullet points above, we proceed as follows:


*

*We start with those $x$ with $\text{ord}(x) = 0$, ie, the fixed points.

*If we've defined $f$ on the set of points with $\text{ord} \leqslant k < m$, we may define $f$ on the set of points with $\text{ord} = k+1$ by mapping each of those points to some point with $\text{ord} = k$.

*This procedure must terminate, because $\text{ord} \leqslant m$.

A: The enumeration problem is solved by OEIS sequence A000949. The comment states "Equivalently, the number of mappings from a set of n elements into itself where f(f(x)) = f(f(f(x)))." The exponential generating function is  $\, \exp(x \exp(x \exp(x))). \,$ A formula as a summation is
 $$\, a(n) = 1 + n! \sum_{m=1}^{n-1} \frac1{m!} \sum_{k=1}^{n-m}
  \frac{k^{n-m-k} m^k}{k! (n-m-k)!}. \,$$
A: This is a bad bad answer. No math at all. Just as a check on whatever solution you end up with, it seems the answer is 756.
Brute-force Python.
def funcs(N):
  "Construct a list of all N-tuples of elements of range(N):"
  res = [()]
  for j in range(N):
    res = [(a,) + f for a in range(N) for f in res]
  return res

def check(f,N):
  "Test whether f^2=f^3 for a given f"
  for j in range(N):
    if not(f[f[j]] == f[f[f[j]]]): return 0
  return 1

count =  0
for f in funcs(5):
  if check(f,5):
    count = count + 1

print count

