A curious Wilf equivalence class of function compositions I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero:  1, 1, 6, 87, 2200, 84245. $$f(f(f(x))) = g(f(x))$$
$$f(g(x)) = g(x)$$
$$f(g(x)) = g(g(x))$$

There is a deep theorem on trees in there but it isn't jumping out at me. Anyone have a reference in the literature?
More generally, you can consider the identity
$$ f(g(x)) = g^{(n)}(x), $$
which generalizes your identities, in which $n=3,1,2$ (respectively).

For a given function $g$, this identity states that $f$ needs to have given values on $\operatorname{ran} g$, and is free otherwise. The specific value of $n$ doesn't matter, in fact we can put whatever we want on the right-hand side as long as it doesn't involve $f$. Using inclusion-exclusion, you can come up with an explicit formula for the number of solutions, but I'll leave that to you.