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)!}.$$
Best Answer
A hint: You can encode each such function as a binary word containing five stars and four bars, like so: $$*\>|\ |**\>|**|\quad.$$