<p>More generally, you can consider the identity
$$ f(g(x)) = g^{(n)}(x), $$
which generalizes your identities, in which $n=3,1,2$ (respectively).</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-27T00:50:43.117Z
Good catch! Feel free to annotate it when it goes live with any formulas. I'm too busy for the next week cranking out related families of sequences to work on closed forms.
Chad Brewbaker
CC BY-SA 3.0
2014-03-27T00:19:48.810Z
2014-03-27T00:19:48.810Z
Yuval Filmus
<p>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))$$</p>

<p>There is a deep theorem on trees in there but it isn't jumping out at me. Anyone have a reference in the literature?</p>

CC BY-SA 3.0
2014-03-26T19:02:46.803Z
For context until these go live on OEIS see https://oeis.org/A181162
Chad Brewbaker
<reference-request><circuit-complexity><functional-programming>
A curious Wilf equivalence class of function compositions
Chad Brewbaker
# A curious Wilf equivalence class of function compositions

(Asked by: username_0 on 2014-03-26)

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?

**Tags:** reference-request, circuit-complexity, functional-programming

> **Comments:**
> **username_0**: For context until these go live on OEIS see https://oeis.org/A181162  

---

## 1 answers

### Answer by username_1 on 2014-03-27. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: Good catch! Feel free to annotate it when it goes live with any formulas. I'm too busy for the next week cranking out related families of sequences to work on closed forms.  

---

