Combinatorial interpretation of composition of power series?

This is a minor curiosity that came up in a joint project recently.

Consider the sequence $a_n=3\frac {(2n)!}{(n+2)!(n-1)!}$ (A000245 in OEIS). It has multiple combinatorial descriptions.

One can write the corresponding generating function, but I will do it with an extra sign. $$f(t) = -\sum_{n=0}^{\infty} a_n t^n = -t-3t^2-9t^3-28t^4-90t^5 -...$$ which has a simple though inelegant description $$f(t) = \frac {(1-t)\sqrt{1-4t}-1+3t}{2t^2}.$$

So far it is all perfectly boring. But the interesting thing is that this $f$ satisfies the identity $$f(f(t))=t.$$ My questions are:

1. Has this been observed before?
2. Are there any combinatorial interpretations of this identity in terms of the combinatorial descriptions of the sequence $a_n$?
• For the general theory of the formal power series identity $f(f(t))=t$, see Enumerative Combinatorics, vol. 1, Exercise 1.168. Jul 17, 2014 at 1:13
• Thank you. While not directly related to the question, it was interesting to learn that, given the even terms, one can adjust the odd terms to ensure the involution property. Jul 17, 2014 at 1:28
• This was observed by Michael Somos in 2004, as noted in the OEIS entry. As also noted in the OEIS entry, $f(t) = - tc(t)^3$, where $c(t)$ is the generating function for Catalan numbers. More generally, the compositional inverse of $xc_r(x^a)^b$ is $xc_{ab-r+1}(-x^a)^b$, where $c_r(x)$ is the generalized Catalan number generating function satisfying $c_r(x) = 1+xc_r(x)^r$; the OP's formula is the case $a=1$, $b=3$, $r=2$. Jul 17, 2014 at 1:28

Basically $f(f(t)) = t$ is related to the fact that $y = f(t)$ and $t$ satisfy an algebraic relation $$y^2 t^2 - 3 y t + y + t = 0$$ which is symmetric in $y$ and $t$ and its graph passes through $(0,0)$ tangent to the line $y=-t$. That relation corresponds to the identity $$\sum_{j=1}^{n-1} a_j a_{n-j} + 3 a_{n+1} - a_{n+2} = 0$$ I don't know if this has a combinatorial interpretation.

• Thanks! It is a nice clean way of seeing the relation, and it may lead to a combinatorial description (the objects for $n+2$ being counted in terms of the objects for smaller $n$). Jul 17, 2014 at 1:24

It seems solutions of the functional equation $g(g(t))=t$ are related to pseudo-involutions of the Riordan group. See http://www.sciencedirect.com/science/article/pii/S0166218X0900016X (Riordan group involutions and the $\Delta$-sequence, by Gi-Sang Cheon, Sung-Tae Jin, Hana Kim and Louis W. Shapiro). From the paper we can get about ten more solutions of this functional equation (Table 1 in the paper). Note that $g(t)=-f(t)$, where $f(t)$ is the generating function from Table 1. The simplest example is $f(t)=\frac{t}{1-t}$ related to the Pascal triangle.

When rephrased (using the positive generating series $g=-f$) as the identity $g(-g(-t))=t$, this suggests that there may exist a quadratic nonsymmetric operad with this generating series, which is Koszul and whose Koszul dual is itself.

I do not know such an operad. Looking at Loday's encyclopedia of operads, a possible candidate could have been the operad of Malcev algebras, but Loday only gives the first three terms $1,3,9$, which is probably not enough to draw any conclusion. And moreover, this is not a nonsymmetric operad. It may be possible to try to find one, maybe being guided by the existing combinatorics.

To illustrate, the simpler case of $g(t)=t/(1-t)$ is related to the Associative operad, which is Koszul and self-dual.

• There is a very nice combinatorial interpretation of identities $g(-f(-t))=t$ in terms of trees, which is related to operas (which I don't know anything about), due by S. Parker (but not published) and rediscovered by J.-L. Loday. (See also R. Bacher and R. Bacher and G. Schaeffer.) However, I couldn't get it to work for this problem. Jul 17, 2014 at 13:32
• You must mean "operads" not "operas" ---- though seeing the latter as a maths term would be quite curious. Jul 17, 2014 at 14:09