3
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 27, 2014 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.