10
$\begingroup$

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$?
Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ For the general theory of the formal power series identity $f(f(t))=t$, see Enumerative Combinatorics, vol. 1, Exercise 1.168. $\endgroup$
    – Richard Stanley
    Commented Jul 17, 2014 at 1:13
  • $\begingroup$ 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. $\endgroup$
    – Lev Borisov
    Commented Jul 17, 2014 at 1:28
  • 7
    $\begingroup$ 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$. $\endgroup$
    – Ira Gessel
    Commented Jul 17, 2014 at 1:28

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$). $\endgroup$
    – Lev Borisov
    Commented Jul 17, 2014 at 1:24
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Commented Jul 17, 2014 at 13:32
  • $\begingroup$ You must mean "operads" not "operas" ---- though seeing the latter as a maths term would be quite curious. $\endgroup$
    – NAME_IN_CAPS
    Commented Jul 17, 2014 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .