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

• For context until these go live on OEIS see oeis.org/A181162 Mar 26, 2014 at 19:02

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.