MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?
share|cite|improve this question
For the general theory of the formal power series identity $f(f(t))=t$, see Enumerative Combinatorics, vol. 1, Exercise 1.168. – Richard Stanley Jul 17 '14 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. – Lev Borisov Jul 17 '14 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$. – Ira Gessel Jul 17 '14 at 1:28
Thank you, I somehow overlooked that OEIS info :( – Lev Borisov Jul 17 '14 at 1:29
up vote 9 down vote accepted

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.

share|cite|improve this answer
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$). – Lev Borisov Jul 17 '14 at 1:24

It seems solutions of the functional equation $g(g(t))=t$ are related to pseudo-involutions of the Riordan group. See (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.

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Ira Gessel Jul 17 '14 at 13:32
You must mean "operads" not "operas" ---- though seeing the latter as a maths term would be quite curious. – NAME_IN_CAPS Jul 17 '14 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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