2
$\begingroup$

Consider the set $T^{2,3}_n$ of all non-planar rooted trees with $n$ leaves labelled by $1,2,\ldots,n$ where each internal vertex can have two or three children. If we think of the binary / ternary vertices as operations, one looks at monomials in the free algebra with $n$ generators with one commutative [nonassociative] binary operation and one totally commutative ternary operation (not satisfying any relations either) which have degree one in each generator. Or, if you prefer (I certainly do), the arity $n$ operations in the free operad generated by one binary symmetric operation and one ternary symmetric operation.

Let $a^{2,3}_n=\# T^{2,3}_n$ (this sequence starts 1, 1, 4, 25, 220, 2485), and consider the generating function $$F(t)=\sum_{n\ge 1}a^{2,3}_n\frac{t^n}{n!}.$$ A simple combinatorial argument (or Koszul duality for operads) immediately tells us that $F(t)$ satisfies the functional equation $$ F(t)=t+(F(t))^2/2+(F(t))^3/6. $$ On the other hand, the OEIS entry http://oeis.org/A268163 for the corresponding sequence has a recurrence relation $$ a^{2,3}_n = \frac{(24n-36)a^{2,3}_{n-1}+(3n-5)(3n-7)a^{2,3}_{n-2}}{11}, \quad n>2 . $$ The right-hand side of this equation has a sum of positive quantities, and because of that I was curious if it admits any reasonably direct combinatorial interpretation.

Of course, there is one standard way to convince ourselves that this recurrence relation holds. First, it can be converted into the following differential equation for $F(t)$: $$ (11-24t-9t^2)F''(t)-(12-9t)F'(t)+F(t)+1=0 , $$ showing that the series $F(t)$ is D-finite. (Of course, it is not surprising, since it is well known that every formal power series which is algebraic (over the field of rational functions) is D-finite / holonomic.) Next, once this differential equation is written down, proving it from the functional equation above is an easy exercise: the functional equation implies that
$$ F'(t)=\frac{1}{1-F(t)-(F(t))^2/2}, \quad F''(t)=\frac{1+F(t)}{(1-F(t)-(F(t))^2/2)^3} , $$ and substituting these into the differential equation above we get a rational function in $t$ and $F(t)$ whose numerator is divisible by $t+(F(t))^2/2+(F(t))^3/6-F(t)$.

Is there a more combinatorial way to establish the recurrence relation above?

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't see what exactly is the question. 1) The algebraic equation (AE) is easy, as you write. 2) Getting ODE from AE is easy - it's repeated differentiation + linear algebra (see Stanley, Enumerative Combinatorics, Ch. 6). So getting the ODE in class explicitly is just as instructional as inverting a matrix or multiplying large numbers. I usually do this for somewhat simpler examples and leave such calculations to a computer or for students to do at home. Why would there be another way? $\endgroup$
    – Igor Pak
    Commented Jan 29, 2016 at 19:53
  • $\begingroup$ @IgorPak I tried to rewrite the question a little bit to make it clearer. I agree that the ODE itself is unlikely to be established easier. But the recurrence relation (to me) looks like it has features distinguishing it from a generic recurrence relation for problems like that, and this made me curious, I suppose. $\endgroup$
    – Vladimir Dotsenko
    Commented Jan 29, 2016 at 20:54
  • $\begingroup$ So, essentially you want a bijection between $11$ trees of size $n$ and the union of $12(2n-3)$ trees of size $n-1$ and $(3n-5)(3n-7)$ trees of size $n-2$? :-) $\endgroup$
    – Martin Rubey
    Commented Jan 29, 2016 at 21:12
  • $\begingroup$ @MartinRubey or something a bit less direct. I realise that division by 11 is a rare thing to happen :) $\endgroup$
    – Vladimir Dotsenko
    Commented Jan 29, 2016 at 21:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .