# Arboretum for a generalization of Ramanujan polynomials

Lucas Randazzo<EMAIL_ADDRESS>
###### Abstract

In this paper, we expand on the work of Guo and Zeng from 2007 on a
generalization of the Ramanujan polynomials and planar trees. We manage to
find combinatorial interpretations of this family of polynomials in terms of
Greg trees, Cayley trees, and planar trees by constructing bijections that
preserve relevant tree statistics.

##  1 Introduction

Study of the Ramanujan’s sequence (1) has led to findings regarding
refinements to Cayley’s formula (see [1, 8, 14]). This formula gives us that
the number of _rooted labelled trees_ with $\displaystyle n$ vertices is
$\displaystyle n^{n-1}$. As an example of refinement, we have the polynomials
$\displaystyle C_{n}$ defined as follows

$\displaystyle C_{1}=1,\hskip
14.22636ptC_{n+1}(y)=\left[n(1+y)+y^{2}\partial_{y}\right]C_{n}$

and verifying (see [14]) $\displaystyle C_{n}(1)=n^{n-1}$. We have
$\displaystyle C_{2}=y+1$ and $\displaystyle C_{3}=3y^{2}+4y+2$. It has been
proven by Shor [12] and Dumont and Ramamonjisoa [6] that the coefficient of
$\displaystyle y^{k}$ in $\displaystyle C_{n}(y)$ counts rooted labelled trees
with $\displaystyle n$ vertices and $\displaystyle k$ _improper edges_ (see
A217922). These polynomials originate from the polynomials $\displaystyle
P_{n}$, defined as

$\displaystyle P_{1}=1,\hskip
14.22636ptP_{n+1}(x,y)=\left[x+n+y(n+y\partial_{y})\right]P_{n}$

which verifies $\displaystyle P_{n}(0,y)=C_{n}(y)$. The polynomials
$\displaystyle P_{n}$ are called the _Ramanujan’s polynomials_ [4, 5]. Indeed,
originally Ramanujan [10] introduced the following double sequence
$\displaystyle\psi_{k}(r,x)$ as follows

$\sum_{k=0}^{+\infty}\frac{(x+k)^{r+k}e^{-u(x+k)}u^{k}}{k!}=\sum_{k=1}^{r+1}\frac{\psi_{k}(r,x)}{(1-u)^{r+k}}.$
(1)

Berndt et al. [1, 2] would then define the $\displaystyle P_{n}$ polynomials
as

$\displaystyle P_{n}(x,y)=\sum_{k=0}^{n-1}\psi_{k+1}(n-1,x+n)y^{k}.$

Following this, Guo and Zeng study in [8] the following polynomial sequence,
credited to Chapoton, as a generalization of the previous sequence

$Q_{1}=1,\hskip
14.22636ptQ_{n+1}(x,y,z,t)=[x+nz+(y+t)(n+y\partial_{y})]Q_{n},$ (2)

verifying $\displaystyle Q_{n}(x,y,0,1)=P_{n}(x,y)$. We have for instance
$\displaystyle Q_{2}=x+y+t+z$ and

$\displaystyle Q_{3}=x^{2}+3xy+3xz+3xt+3y^{2}+4yz+5yt+2z^{2}+4zt+2t^{2}.$

They find a combinatorial interpretation of this sequence in terms of _planar
labelled trees_. However, as stated by Josuat-Vergès in [9], the Ramanujan
polynomials seem to also be correlated to _Greg trees_. Initially defined by
Flight in [7] to represent genealogical trees for manuscripts, Greg trees are
trees with both labelled and unlabelled nodes, the unlabelled ones being of
degree at least three.

Our goal is to relate the polynomials $\displaystyle Q_{n}$ with _Greg trees_
and _Cayley trees_ , and give a simple expression of $\displaystyle Q_{n}$
using different tree statistics. In Section 2 we introduce the different
notions and definitions needed throughout this article, in particular we will
define a sequence $\displaystyle R_{n}$ that will be key to most of our
proofs. In Section 3, we will express $\displaystyle R_{n}$ in terms or
relevant statistics on Greg trees using a recurrence relation for
$\displaystyle R_{n}$. Section 4 will give a similar result for Cayley trees,
by using a bijection between Greg trees and Cayley trees. Finally in Section 5
we will show how this relates to $\displaystyle Q_{n}$ by introducing a
bijection between Cayley trees and planar labelled trees.

##  2 Preliminaries

We recall that a _Cayley tree_ is a tree with $\displaystyle n$ labelled
vertices on $\displaystyle[n]$ such that no two vertices are labelled the
same. Let $\displaystyle\mathcal{C}_{n}$ be the set of Cayley trees of size
$\displaystyle n$ rooted at $\displaystyle 1$, we have
$\displaystyle|\mathcal{C}_{n}|=n^{n-2}$. A _planar tree_ is a rooted labelled
tree in which the children of each vertex are linearly ordered. We denote by
$\displaystyle\mathcal{O}_{n}$ the set of planar trees rooted at
$\displaystyle 1$ and labelled on $\displaystyle[n]$. The following
definition, coined by Flight in [7], gives us an interesting generalization of
Cayley trees.

######  Definition 2.1 (Flight, [7]).

Let $\displaystyle n\geq 1$. A _Greg tree_ of size $\displaystyle n$ is a tree
such that exactly $\displaystyle n$ of its vertices are labelled in
$\displaystyle[n]$, and the unlabelled vertices are of degree at least
$\displaystyle 3$.

Let $\displaystyle\mathcal{G}_{n}$ be the set of Greg trees of size
$\displaystyle n$ rooted at $\displaystyle 1$. Let
$\displaystyle\operatorname{unl}(T)$ denote the number of unlabelled vertices
of $\displaystyle T\in\mathcal{G}_{n}$. If
$\displaystyle\operatorname{unl}(T)=0$, then $\displaystyle
T\in\mathcal{C}_{n}$. See Figure 1 for an example of a Greg tree.

For a labelled tree $\displaystyle T$, especially for Greg trees, it is
convenient to introduce $\displaystyle\lambda_{T}$ the labelling function of
$\displaystyle T$. As a convention, we choose for $\displaystyle\lambda_{T}$
to not be defined over unlabelled vertices in a Greg tree.

Figure 1: An example of a Greg tree of size 9, with one unlabelled vertex
$\displaystyle u$. The improper edges are doubled.

Since all the trees we consider are rooted, we will use oriented edges, with
the following notation: if $\displaystyle(i,j)$ is an edge of $\displaystyle
T$, then $\displaystyle i$ is the parent of $\displaystyle j$.

In an alternative proof of Cayley’s formula [12], Shor introduced an
interesting categorization of edges in a Cayley tree, which can be generalized
to Greg trees.

######  Definition 2.2 (Shor, [12]).

Let $\displaystyle T\in\mathcal{C}_{n}\cup\mathcal{G}_{n}\cup\mathcal{O}_{n}$,
and $\displaystyle i$ a labelled vertex of $\displaystyle T$. We define
$\displaystyle\beta_{T}(i)$ to be the smallest label in the descendants of
$\displaystyle i$. If $\displaystyle T\in\mathcal{C}_{n}\cup\mathcal{G}_{n}$,
let $\displaystyle e=(i,j)$ be an edge of $\displaystyle T$. We say that
$\displaystyle e$ is an _improper edge_ , or $\displaystyle j$ is an _improper
child_ of $\displaystyle i$, if $\displaystyle i$ is labelled and
$\displaystyle\lambda_{T}(i)>\beta_{T}(j)$. Otherwise, $\displaystyle e$ is a
_proper edge_ , and $\displaystyle j$ is a _proper child_ of $\displaystyle
i$.

For instance in Figure 1, improper edges are represented with double lines,
and we have $\displaystyle\beta_{T}(4)=2$ and $\displaystyle\beta_{T}(7)=6$.
Naturally, $\displaystyle\beta_{T}$ is also defined on unlabelled vertices,
and here we have $\displaystyle\beta_{T}(u)=6$. Remark that an unlabelled
vertex cannot be an improper parent, even though it can be an improper child.

Regarding planar trees, we need to use Guo and Zeng’s generalization from [8].

######  Definition 2.3.

Let $\displaystyle T\in\mathcal{O}_{n}$.

  * •

Let $\displaystyle j$ be a vertex of $\displaystyle T$. $\displaystyle j$ is
_elder_ if it has a brother $\displaystyle k$ to its right such that
$\displaystyle\beta_{T}(k)<\beta_{T}(j)$. Otherwise, we say that
$\displaystyle j$ is _younger_. Let $\displaystyle\operatorname{young}_{T}(i)$
be the number of younger children of $\displaystyle i$ in $\displaystyle T$,
and $\displaystyle\operatorname{eld}(T)$ be the number of elder vertices of
$\displaystyle T$.

  * •

Let $\displaystyle e=(i,j)$ be an edge of $\displaystyle T$. We say that
$\displaystyle e$ is an _improper edge_ , or $\displaystyle j$ is an improper
child of $\displaystyle i$, if $\displaystyle j$ is a younger child of
$\displaystyle i$ and $\displaystyle\lambda_{T}(i)>\beta_{T}(j)$. Otherwise,
$\displaystyle e$ is a _proper edge_ , and $\displaystyle j$ is a _proper
child_ of $\displaystyle i$.

Figure 2: An example of a planar tree of size 14. The improper edges are shown
doubled.

We show an example of a planar tree, with improper edges doubled, in Figure 2.
In either case, let $\displaystyle\operatorname{impe}(T)$ be the number of
improper edges of $\displaystyle T$. Remark that if $\displaystyle T$ is a
planar tree with no elder child, its siblings are ordered by increasing order
of $\displaystyle\beta_{T}$. In this case, the improper edges are the same as
if we removed the order on the siblings of $\displaystyle T$.

Finally, we can extend the definition of _improper_ to vertices, when we want
to know whether a vertex has improper outgoing edges or not.

######  Definition 2.4.

We say that a parent $\displaystyle i$ is _proper_ if it has no improper
child. Otherwise we say that $\displaystyle i$ is an _improper parent_.
Equivalently, a vertex $\displaystyle i$ is an improper parent if and only if
it is labelled and $\displaystyle\beta_{T}(i)\neq\lambda_{T}(i)$. We denote by
$\displaystyle\operatorname{impp}(T)$ the number of improper parents of
$\displaystyle T$.

We can now introduce the main theorem of Guo and Zeng in [8]. It gives a
combinatorial interpretation of $\displaystyle Q_{n}$ in terms of planar
trees.

######  Theorem 2.5 (Guo and Zeng, [8]).

$Q_{n}(x,y,z,t)=\sum_{T\in\mathcal{O}_{n+1}}x^{\operatorname{young}_{T}(1)-1}t^{\operatorname{eld}(T)}y^{\operatorname{impe}(T)}z^{n-\operatorname{young}_{T}(1)-\operatorname{eld}(T)-\operatorname{impe}(T)}.$

Our goal is to find a similar equality for Greg trees and Cayley trees. Let us
consider the following polynomials.

######  Definition 2.6 (Josuat-Vergès, [9]).

$H_{1}=1,\hskip
14.22636ptH_{n+1}(y)=(2n-1+(n+1)y)H_{n}(x)+(1+y)^{2}H_{n}^{\prime}(x).$ (3)

These polynomials count the number of Greg trees with $\displaystyle n$
labelled vertices (A048159). Using (2) and (3), we obtain

$H_{n+1}(y)=Q_{n}(1,y+1,1,0).$ (4)

This suggests that there is a correlation between Greg trees and planar trees.
Moreover, we have

######  Proposition 2.7 (Josuat-Vergès, [9]).

$H_{n}(y)=\sum_{T\in\mathcal{G}_{n}}y^{\operatorname{unl}(T)}=\sum_{T\in\mathcal{C}_{n}}(1+y)^{\operatorname{impe}(T)}.$
(5)

The original paper asks about the existence of a bijective proof for (5). In
the Section 4 we will indeed construct such a bijection. We will actually find
a bijection that generalizes Proposition 2.7 for the following polynomials in
4 variables.

######  Definition 2.8.

$R_{n}(x,y,z,t)=Q_{n}(x,y+1,z,t-1)$ (6)

$\displaystyle R_{n}$ allows us to bridge the gap between $\displaystyle
H_{n}$ and $\displaystyle Q_{n}$, since we can see $\displaystyle R_{n}$ as a
generalization of $\displaystyle H_{n}$, as we have $\displaystyle
R_{n}(1,y,1,1)~{}=~{}H_{n}(y)$. In particular we have $\displaystyle
R_{n+1}(0,y,0,1)=(2n-1)!!(y+1)^{n}$, and $\displaystyle R_{n}(0,y,0,0)$ gives
the Ward numbers (A134991). We will explain in more details why this last
property is true at the end of Section 3.

Before moving on to the next section, we need to introduce one more statistic
that will be useful in the next section.

######  Definition 2.9.

Let $\displaystyle T$ be a Greg or Cayley tree. Let $\displaystyle i$ be a
labelled vertex of $\displaystyle T$. Let $\displaystyle
L(i)=(1=a_{0},a_{1},\ldots,a_{k}=i)$ be the only path through $\displaystyle
T$ from the root $\displaystyle 1$ to $\displaystyle i$. We define the
_greater ancestors path_ of $\displaystyle i$, noted
$\displaystyle\operatorname{gap}(i)=(a_{p},a_{p+1},\ldots,i)$, the longest
path in $\displaystyle T$ included in $\displaystyle L(i)$ and containing
$\displaystyle i$ such that, for every labelled vertex $\displaystyle
j\in\operatorname{gap}(i)$, $\displaystyle\lambda_{T}(j)\geq\lambda_{T}(i)$.

For example, in Figure 1, we have
$\displaystyle\operatorname{gap}(3)=(4,5,3)$,
$\displaystyle\operatorname{gap}(2)=(4,2)$ and
$\displaystyle\operatorname{gap}(6)~{}=~{}(6)$.

######  Definition 2.10.

Let $\displaystyle i\in T$ and
$\displaystyle\operatorname{gap}(i)=(a_{p},\ldots,i)$. $\displaystyle i$ is a
_leading vertex_ if $\displaystyle\beta_{T}(a_{p})~{}=~{}\lambda_{T}(i)$.

Remark that $\displaystyle 1$ and $\displaystyle 2$ are always leading
vertices. Also remark that if $\displaystyle i$ is a leading vertex, then for
all $\displaystyle j\in\operatorname{gap}(i)$,
$\displaystyle\beta_{T}(j)=\lambda_{T}(i)$. This also implies with Definition
2.4 that $\displaystyle i$ is a proper parent.

We will see that the number of leading vertices is relevant for Greg trees,
but not in Cayley or planar trees. Hence we need the following Lemma.

######  Lemma 2.11.

Let $\displaystyle T\in\mathcal{C}_{n}$. We have

$\operatorname{lead}(T)=n-\operatorname{impe}(T).$ (7)

###### Proof.

Since every edge is either proper or improper, we have that $\displaystyle
n-1-\operatorname{impe}(T)$ is the number of proper edges of $\displaystyle
T$. Hence to prove the lemma, we can find a bijection between the set of
leading vertices except $\displaystyle 1$, and the proper edges of
$\displaystyle T$.

Let $\displaystyle i$ be a leading vertex of $\displaystyle T$ that is not
$\displaystyle 1$. Let $\displaystyle\operatorname{gap}(i)=(a_{p},\ldots,i)$.
Since $\displaystyle i$ is not $\displaystyle 1$, let $\displaystyle a_{p-1}$
be the parent of $\displaystyle a_{p}$. Let
$\displaystyle\phi(i)=(a_{p-1},a_{p})$.

$\displaystyle\phi$ is injective. Indeed, let $\displaystyle u$ be another
leading vertex of $\displaystyle T$, and assume that
$\displaystyle\phi(u)=\phi(i)$. We would have $\displaystyle
a_{p}\in\operatorname{gap}(i)\cap\operatorname{gap}(u)$, hence verifying both
$\displaystyle\beta_{T}(a_{p})=\lambda_{T}(i)$ and
$\displaystyle\beta_{T}(a_{p})=\lambda_{T}(u)$, which is impossible.

$\displaystyle\phi$ is surjective. Let $\displaystyle(a,b)$ be a proper edge
of $\displaystyle T$. From $\displaystyle b$, we can go down the tree by
choosing the child with the smallest value for $\displaystyle\beta_{T}$, until
we find a proper parent $\displaystyle u$, which we can always find since
leaves are. On this path, $\displaystyle\beta_{T}$ is constant, equal to
$\displaystyle\lambda(u)$. Hence this path is a suffix of
$\displaystyle\operatorname{gap}(u)$. Since $\displaystyle(a,b)$ is a proper
edge, $\displaystyle a\not\in\operatorname{gap}(u)$, so the path from
$\displaystyle b$ to $\displaystyle u$ is
$\displaystyle\operatorname{gap}(u)$, and $\displaystyle\phi(u)=(a,b)$.

Hence, $\displaystyle\phi$ is bijective, which proves the lemma. ∎

##  3 Greg Trees and $\displaystyle R_{n}$

The first result we show is that $\displaystyle R_{n}$ can be seen as a
generating function for Greg trees. This is a generalization of the first
equality of Proposition 2.7.

######  Theorem 3.1.

$R_{n}(x,y,z,t)=\sum_{T\in\mathcal{G}_{n+1}}y^{\operatorname{unl}(T)}t^{\operatorname{impp}(T)}x^{\deg_{T}(1)-1}z^{\operatorname{lead}(T)-\deg_{T}(1)-1}.$
(8)

###### Proof.

The definition of $\displaystyle R_{n}$ (6) gives us the following recurrence:

$R_{1}=1,\hskip 14.22636ptR_{n+1}=[x+nz+(y+t)(n+(y+1)\partial_{y})]R_{n}.$ (9)

Now we just need to prove that the right hand side in (8) is a solution to
(9). We define a weight function over Greg trees as

$\displaystyle\omega(T)=y^{\operatorname{unl}(T)}t^{\operatorname{impp}(T)}x^{\deg_{T}(1)-1}z^{\operatorname{lead}(T)-\deg_{T}(1)-1}.$

The recurrence can be interpreted as the weighted sum of the different ways to
add a $\displaystyle n+2$-labelled vertex to a Greg tree of size
$\displaystyle n+1$. In the following, we denote by $\displaystyle T$ the base
tree of size $\displaystyle n+1$, and $\displaystyle T^{\prime}$ the result of
adding a vertex labelled $\displaystyle n+2$ to $\displaystyle T$. We have
eight distinct operations, noted $\displaystyle f_{i}$ for $\displaystyle
i\in[1,8]$:

  1. 1.

$\displaystyle\textstyle\sum_{T^{\prime}\in
f_{1}(T)}\omega(T^{\prime})=x\omega(T)$.

We add the new vertex labelled $\displaystyle n+2$ as a child of
$\displaystyle 1$. This new vertex has to be leading, since its parent is
smaller that itself, and $\displaystyle\beta_{T}(n+2)~{}=~{}n~{}+~{}2$, so
$\displaystyle\operatorname{lead}(T^{\prime})~{}=~{}\operatorname{lead}(T)~{}+~{}1$.
We also increase the degree of $\displaystyle 1$, so we have
$\displaystyle\deg_{T^{\prime}}(1)~{}=~{}\deg_{T}(1)~{}+~{}1$. Since

$\displaystyle\operatorname{lead}(T^{\prime})-\deg_{T^{\prime}}(1)=\operatorname{lead}(T)+1-(\deg_{T}(1)+1)=\operatorname{lead}(T)-\deg_{T}(1),$

the degree of $\displaystyle z$ in $\displaystyle\omega(T^{\prime})$ does not
change.

  2. 2.

$\displaystyle\textstyle\sum_{f_{2}(T)}\omega(T^{\prime})=nz\omega(T)$.

We add the new vertex labelled $\displaystyle n+2$ as a child to another
labelled vertex that is not $\displaystyle 1$, which makes $\displaystyle n$
distinct vertices to chose from. Like in the previous case, this new vertex is
leading, but the degree of $\displaystyle 1$ does not change, so we need to
multiply by $\displaystyle z$ instead of $\displaystyle x$ in this case.

  3. 3.

$\displaystyle\textstyle\sum_{f_{3}(T)}\omega(T^{\prime})=y\partial_{y}\omega(T)$.

We add the vertex labelled $\displaystyle n+2$ as a child to an existing
unlabelled vertex $\displaystyle u$. Here we choose amongst the unlabelled
vertices of $\displaystyle T$, which are counted by the degree of
$\displaystyle y$ in $\displaystyle\omega(T)$. Multiplying by the degree of
$\displaystyle y$ in the equation translates to deriving with respect to
$\displaystyle y$, then multiplying by $\displaystyle y$ the weight function.
In this case, the new vertex is not leading. Indeed, its parent $\displaystyle
u$ is unlabelled, so it has at least two other descendants smaller than
$\displaystyle n+2$, so $\displaystyle\beta_{T^{\prime}}(u)=\beta_{T}(u)\neq
n+2$. The degree of $\displaystyle 1$ also stays unchanged.

  4. 4.

$\displaystyle\textstyle\sum_{f_{4}(T)}\omega(T^{\prime})=t\partial_{y}\omega(T)$.

We relabel an unlabelled vertex with $\displaystyle n+2$. Since we remove an
unlabelled vertex from $\displaystyle T$, we do not have $\displaystyle y$ as
a factor here in the recursion. However,
$\displaystyle\beta_{T^{\prime}}(n+2)\neq n+2$, so $\displaystyle n+2$ is a
new improper parent and it is not a leading vertex, so we only add a factor
$\displaystyle t$.

  5. 5.

$\displaystyle\textstyle\sum_{f_{5}(T)}\omega(T^{\prime})=tn\omega(T)$.

We add the vertex $\displaystyle n+2$ in the middle of an existing edge
$\displaystyle(i,j)$, where $\displaystyle j$ is labelled. We have
$\displaystyle n$ choices of edges, as $\displaystyle j$ can be any labelled
vertex of $\displaystyle T$ except $\displaystyle 1$. We have that
$\displaystyle\beta_{T^{\prime}}(n+2)=\beta_{T^{\prime}}(j)=\beta_{T}(j)\neq
n+2$, so $\displaystyle n+2$ is a new improper parent and not a leading
vertex.

  6. 6.

$\displaystyle\textstyle\sum_{f_{6}(T)}\omega(T^{\prime})=ty\partial_{y}\omega(T)$.

We add the vertex $\displaystyle n+2$ in the middle of an existing edge
$\displaystyle(i,j)$, where $\displaystyle j$ is unlabelled. The same
reasoning as the previous case applies to this one, so $\displaystyle n+2$ is
a new improper parent and not a leading vertex.

  7. 7.

$\displaystyle\textstyle\sum_{f_{7}(T)}\omega(T^{\prime})=yn\omega(T)$.

We add an unlabelled vertex $\displaystyle u$ in the middle of an edge
$\displaystyle(i,j)$ where $\displaystyle j$ is labelled, then add the vertex
$\displaystyle n+2$ as its second child. $\displaystyle u$ cannot be an
improper parent, since it is not labelled. Moreover, similarly to case
$\displaystyle 3$, as the highest labelled child of an unlabelled vertex,
$\displaystyle n+2$ is not leading.

  8. 8.

$\displaystyle\textstyle\sum_{f_{8}(T)}\omega(T^{\prime})=y^{2}\partial_{y}\omega(T)$.

We add an unlabelled vertex $\displaystyle u$ in the middle of an edge
$\displaystyle(i,j)$ where $\displaystyle j$ is unlabelled, then add the
vertex $\displaystyle n+2$ as its second child. The same reasoning as the
previous case applies.

We also needed to verify that this construction does not change the number of
improper parents or leading vertices among the first $\displaystyle n+1$
vertices. However, it is easy to prove since for any vertex $\displaystyle
i\in T$, $\displaystyle\beta_{T}(i)=\beta_{T^{\prime}}(i)$. Moreover, in cases
$\displaystyle 4$ and $\displaystyle 5$, we introduce a vertex $\displaystyle
a$ in the middle of an edge $\displaystyle(i,j)$, so
$\displaystyle\beta_{T^{\prime}}(a)=\beta_{T^{\prime}}(j)$, and the edge
$\displaystyle(i,a)$ in $\displaystyle T^{\prime}$ is improper if and only if
$\displaystyle(i,j)$ was improper in $\displaystyle T$, while the edge
$\displaystyle(a,j)$ is always proper. Another consequence is that any
descendant of $\displaystyle a$ that was leading in $\displaystyle T$ is still
leading in $\displaystyle T^{\prime}$.

To conclude, let $\displaystyle f(T)=\cup f_{i}(T)$, we have

$\displaystyle\sum_{T^{\prime}\in
f(T)}\omega(T^{\prime})=[x+nz+(y+t)(n+(y+1)\partial_{y})]\omega(T).$

Since it is clear that $\displaystyle\\{f(T),T\in\mathcal{(}G)_{n+1}\\}$ is a
partition of $\displaystyle\mathcal{G}_{n+2}$, we only need to sum the above
equation over $\displaystyle T\in\mathcal{G}_{n+1}$ to obtain (9).

∎

As pointed out in the previous section, the sequence of polynomials
$\displaystyle R_{n}(0,y,0,0)$ have positive coefficients, and gives the
triangle of Ward numbers A134991. It first means that $\displaystyle
Q_{n}(0,y+1,0,-1)$ has positive coefficients, which was not immediate from
Theorem 2.5. This sequence can be interpreted as the face numbers of the space
of _phylogenetic trees_ , introduced by Billera, Holmes and Vogtmann in [3],
which is also the tropical Grassmannian of lines
$\displaystyle\mathcal{G}_{2,n}$ (see [13]). The faces of the space of
phylogenetic trees can be seen as unrooted Greg trees which only labelled
vertices are its leaves. The degree of each face is the number of unlabelled
vertices of the Greg tree. Remark that maximal faces are trivalent trees, of
which there are $\displaystyle(2n-3)!!$. This definition, along with Theorem
3.1, is enough to prove our claim. Indeed, $\displaystyle
R_{n}(0,y,0,0)=\sum_{T}y^{\operatorname{unl}(T)}$, where $\displaystyle
deg_{1}(T)=1$, $\displaystyle\operatorname{impp}(T)=0$, and $\displaystyle
lead(T)=2$. Recall that $\displaystyle 1$ and $\displaystyle 2$ are always
leading vertices in $\displaystyle T$. Now assume that $\displaystyle T$ has
at least one internal labelled vertex, and let $\displaystyle j\neq 1$ be one.
Let us assume that $\displaystyle j$ is not an improper parent. Let
$\displaystyle k$ be the smallest strict descendant of $\displaystyle j$, then
we can easily see that $\displaystyle k$ is leading. Hence $\displaystyle T$
cannot have internal labelled vertices, which proves our claim.

##  4 A bijection for Cayley Trees

We now give a new interpretation of $\displaystyle R_{n}$, with Cayley trees
this time. The proof builds on the previous theorem, and gives a statistics
preserving bijection between Greg trees ans Cayley trees. This is a
generalization of the second equality of Proposition 2.7.

######  Theorem 4.1.

$R_{n}(x,y,z,t)=\sum_{T\in
C_{n+1}}(y+1)^{\operatorname{impe}(T)-\operatorname{impp}(T)}(y+t)^{\operatorname{impp}(T)}x^{\deg_{T}(1)-1}z^{\operatorname{lead}(T)-\deg_{T}(1)-1}.$
(10)

Figure 3: Illustration of the operation $\displaystyle\varphi_{a,S(a)}$.
Children are shown ordered with increasing values of $\displaystyle\beta_{T}$.

###### Proof.

To prove (10), we will use Theorem 3.1, and find an application between Cayley
trees and Greg trees that behaves nicely with our statistics. We first need to
have some definitions.

Let $\displaystyle T\in\mathcal{G}_{n+1}$, for a vertex $\displaystyle a\in
T$, we denote by $\displaystyle I(a)=\\{b_{1},b_{2},\ldots,b_{k}\\}$ its set
of improper children, ordered so that
$\displaystyle\beta_{T}(b_{1})~{}<~{}\beta_{T}(b_{2})~{}<~{}\ldots~{}<~{}\beta_{T}(b_{k})$.
Let $\displaystyle m(a)\in I(a)$ be so that
$\displaystyle\beta_{T}(m(a))=\max_{b\in I(a)}\\{\beta_{T}(b)\\}$. We define a
_selection function_ $\displaystyle S$ over the improper parents of
$\displaystyle T$ so that, for $\displaystyle a\in\operatorname{impp}(T)$,
$\displaystyle S(a)\subset I(a)$. Let $\displaystyle\operatorname{Sel}(T)$ be
the set of such functions. Choosing a selection function for a tree
$\displaystyle T$ is exactly like choosing a subset of the improper edges of
$\displaystyle T$, hence
$\displaystyle\operatorname{Sel}(T)\cong\mathcal{P}(impe(T))$.

We construct a bijection between Greg trees and the set
$\displaystyle\\{(T,S)|S\in\operatorname{Sel}(T)\\}$ of Cayley trees with
pointed improper edges. Let $\displaystyle a\in\operatorname{impp}(T)$ and
$\displaystyle S(a)=\\{b_{i_{1}},\ldots,b_{i_{j}}\\}$ with $\displaystyle
i_{1}<\ldots<i_{j}$. The idea of the bijection is to divide the set of
improper children for every improper parent of $\displaystyle T$, creating an
unlabelled vertex for every subdivision we create. We define the
transformation $\displaystyle\varphi_{a,S(a)}(T)$ as follows: in
$\displaystyle T$, add a chain of $\displaystyle|S(a)|$ unlabelled vertices as
direct antecedents of $\displaystyle a$, and for every child $\displaystyle c$
of $\displaystyle a$, if
$\displaystyle\beta_{T}(b_{i_{m-1}+1})\leq\beta_{T}(c)\leq\beta_{T}(b_{i_{m}})$,
then remove the edge $\displaystyle(a,c)$ and add an edge between
$\displaystyle c$ and the $\displaystyle m$-th unlabelled vertex, as
illustrated in Figure 3. It is important to note that if $\displaystyle
m(a)\in S(a)$, then $\displaystyle a$ is no longer an improper parent in the
resulting tree. Also note that if $\displaystyle
a_{1},a_{2}\in\operatorname{impp}(T)$, then
$\displaystyle\varphi_{a_{1},S(a_{1})}\circ\varphi_{a_{2},S(a_{2})}=\varphi_{a_{2},S(a_{2})}\circ\varphi_{a_{1},S(a_{1})}$
for any $\displaystyle S$. Finally, let
$\displaystyle\varphi(S,T)=\left(\underset{a\in\operatorname{impp}(T)}{\circ}\varphi_{a,S(a)}\right)(T)$.
We have

$\operatorname{unl}(\varphi(S,T))=\sum_{a\in\operatorname{impp}(T)}|S(a)|,\text{
and}$ $\operatorname{impp}(\varphi(S,T))=\\#\\{a|m(a)\not\in S(a)\\}.$

Also note that the degree of $\displaystyle 1$ and the number of leading
vertices is unchanged by the transformation. So for $\displaystyle
T\in\mathcal{C}_{n}$, we have

$\sum_{S\in\operatorname{Sel}(T)}y^{\operatorname{unl}(\varphi(S,T))}t^{\operatorname{impp}(\varphi(S,T))}=(y+1)^{\operatorname{impe}(T)-\operatorname{impp}(T)}(y+t)^{\operatorname{impp}(T)}.$

This operation is reversible, for every Greg tree we can find the only Cayley
tree from which it can be obtained. Formally, we introduce a rewriting system
$\displaystyle\rightarrow$ over Greg trees. Let $\displaystyle
G\in\mathcal{G}_{n+1}$, let $\displaystyle i\in G$ be an unlabelled vertex,
and let $\displaystyle j$ be its only child that verifies
$\displaystyle\beta_{G}(i)=\beta_{G}(j)$. Let $\displaystyle G^{\prime}$ be
the tree we obtain by merging $\displaystyle i$ and $\displaystyle j$. Then
$\displaystyle G\rightarrow G^{\prime}$. For example, if $\displaystyle
S\in\operatorname{Sel}(T)$, and $\displaystyle S^{\prime}$ is obtained from
removing one element from $\displaystyle S$, we have
$\displaystyle\varphi(S,T)\rightarrow\varphi(S^{\prime},T)$.

This rewriting system is locally confluent, since rewriting an unlabelled
vertex is a local operation within the tree and does not impact the rest of
the tree, and this system is terminating, since it removes an unlabelled
vertex each step. By Newman’s Lemma (see for instance [11]), this system is
confluent, hence we can define $\displaystyle\psi(G)$ as the only minimal tree
of $\displaystyle G$ in this system, verifying $\displaystyle
G\rightarrow^{*}\psi(G)$ and $\displaystyle\psi(G)\in\mathcal{C}_{n+1}$.

Another approach to finding the inverse of $\displaystyle\varphi$ would have
been to invert each $\displaystyle\varphi_{a,S(a)}$. The idea here is that all
unlabelled vertices introduced by the transformation are such that their child
with the largest value for $\displaystyle\beta_{T}$ is an ancestor to
$\displaystyle a$, are the only ones that verify such property, and form a
path in the tree. This can be easily seen in Figure 3, since we ordered
children with increasing values of $\displaystyle\beta_{T}$. So instead of
inverting for each unlabelled vertex, we would do so for each labelled vertex
that is the highest $\displaystyle\beta_{T}$-valued child of an unlabelled
vertex.

######  Lemma 4.2.

Let $\displaystyle T,T^{\prime}\in\mathcal{C}_{n}$, $\displaystyle
S\in\operatorname{Sel}(T)$ and $\displaystyle
S^{\prime}\in\operatorname{Sel}(T^{\prime})$. We have

$\varphi(S,T)=\varphi(S^{\prime},T^{\prime})\Rightarrow T=T^{\prime}\text{ and
}S=S^{\prime}.$ (11)

###### Proof.

First, remark that by construction, $\displaystyle\psi(\varphi(S,T))=T$ for
any $\displaystyle S\in\operatorname{Sel}(T)$, which proves the first
implication of (11). For the second part, we want to prove that we cannot make
the same Greg tree from a Cayley tree and two different selection functions.
At first glance, when looking at a chain of unlabelled vertices, one cannot
say if it comes from one or multiple $\displaystyle\varphi_{a,S(a)}$. However,
when looking at each improper vertex of $\displaystyle T$ one at a time, we
see that there is only one way to revert $\displaystyle\varphi_{a,S(a)}$. The
idea is then to build a recursive proof on the size of $\displaystyle S$. Let
$\displaystyle T\in\mathcal{C}_{n}$ and $\displaystyle
S,S^{\prime}\in\operatorname{Sel}(T)$. For $\displaystyle
I\subset\operatorname{impp}(T)$, we define $\displaystyle S_{|I}$ as the
restriction of $\displaystyle S$ over $\displaystyle I$, which means, for
$\displaystyle a\in\operatorname{impp}(T)$,

$\displaystyle S_{|I}(a)=\left\\{\begin{array}[]{l}S(a)\text{ if }a\in I\\\
\emptyset\text{ otherwise.}\end{array}\right.$

We prove by induction over the size of $\displaystyle I$ that

$\varphi(S_{|I},T)=\varphi(S^{\prime}_{|I},T)\Rightarrow
S_{|I}=S^{\prime}_{|I}.$ (12)

If $\displaystyle I=\\{a\\}$, we have
$\displaystyle\varphi(S_{|\\{a\\}},T)=\varphi_{a,S(a)}(T)$. However,
$\displaystyle J\mapsto\varphi_{a,J}(T)$ is injective, so
$\displaystyle\varphi(S_{|\\{a\\}},T)=\varphi(S^{\prime}_{|\\{a\\}},T)\Rightarrow
S(a)=S^{\prime}(a)\Rightarrow S_{|\\{a\\}}=S^{\prime}_{|\\{a\\}}$. Let
$\displaystyle n\geq 0$ and assume that (12) is true for any $\displaystyle
I\subset\operatorname{impp}(T)$, with $\displaystyle|I|\leq n$. Let
$\displaystyle J=\\{a\\}\cup I$ with $\displaystyle|J|=n+1$ and $\displaystyle
a\not\in I$. Then we have

$\displaystyle\varphi(S_{|J},T)=\varphi_{a,S(a)}(\varphi(S_{|I},T))=\varphi(S_{|\\{a\\}},\varphi(S_{|I},T)).$

Hence

$\displaystyle\begin{array}[]{r
l}&\varphi(S_{|J},T)=\varphi(S^{\prime}_{|J},T)\\\
\Rightarrow&\varphi(S_{|\\{a\\}},\varphi(S_{|I},T))=\varphi(S^{\prime}_{|\\{a\\}},\varphi(S^{\prime}_{|I},T))\\\
\Rightarrow&S_{|\\{a\\}}=S^{\prime}_{|\\{a\\}}\text{ and
}\varphi(S_{|I},T)=\varphi(S^{\prime}_{|I},T)\\\
\Rightarrow&S_{|\\{a\\}}=S^{\prime}_{|\\{a\\}}\text{ and
}S_{|I}=S^{\prime}_{|I}\\\ \Rightarrow&S_{|J}=S^{\prime}_{|J}.\par\end{array}$

We conclude by taking $\displaystyle I=\operatorname{impp}(T)$ in (12). ∎

Hence with Lemma 4.2,
$\displaystyle\\{\\{\varphi(S,T),S\in\operatorname{Sel}(T)\\},T\in\mathcal{C}_{n+1}\\}$
is a partition of $\displaystyle\mathcal{G}_{n+1}$. So we have

$\begin{array}[]{c c
c}\sum_{G\in\mathcal{G}_{n+1}}y^{\operatorname{unl}(G)}t^{\operatorname{impp}(G)}&=&\sum_{T\in\mathcal{C}_{n+1}}\sum_{S\in\operatorname{Sel}(T)}y^{\operatorname{unl}(\varphi(S,T))}t^{\operatorname{impp}(\varphi(S,T))}\\\
&=&\sum_{T\in\mathcal{C}_{n+1}}(y+1)^{\operatorname{impe}(T)-\operatorname{impp}(T)}(y+t)^{\operatorname{impp}(T)}.\par\end{array}$

Finally, $\displaystyle\varphi$ changes neither the degree of $\displaystyle
1$, nor the number of leading vertices, which can easily be verified. Hence we
can add the other two variables $\displaystyle x$ and $\displaystyle z$ to the
equation, and conclude. ∎

##  5 Between Cayley trees and planar trees

Using a variable change and working with $\displaystyle R_{n}$, we were able
to make sense of the multivariate Ramanujan polynomials in terms of Greg trees
and Cayley trees. We now need to link our results back to the original
observation from Guo and Zeng on the polynomials $\displaystyle Q_{n}$. Using
definition 2.8, we have a relation between labelled trees and planar labelled
trees. In particular, we have the following equation.

######  Proposition 5.1.

Let $\displaystyle n>1$. We have

$\begin{array}[]{l}\sum_{T\in\mathcal{C}_{n+1}}y^{\operatorname{impe}(T)}(t+1)^{\operatorname{impp}(T)}x^{\deg_{T}(1)-1}z^{\operatorname{lead}(T)-\deg_{T}(1)-1}\\\
\hskip
40.0pt=\sum_{T\in\mathcal{O}_{n+1}}y^{\operatorname{impe}(T)+\operatorname{eld}(T)}t^{\operatorname{eld}(T)}x^{\operatorname{young}_{T}(1)-1}z^{n-\operatorname{impe}(T)-\operatorname{young}_{T}(1)-\operatorname{eld}(T)}.\\\
\end{array}$ (13)

Indeed, with a change of variables, the definition of $\displaystyle R_{n}$
gives us

$\displaystyle R_{n}(x,y-1,z,yt+1)=Q_{n}(x,y,z,yt).$

Equality (13) is an immediate corollary from the definition of $\displaystyle
R_{n}$, and the Theorems 2.5 and 4.1. However, its summatory nature calls for
a bijective proof. First, let us use Lemma 2.11 and shift the indexes to
obtain the following equivalent formula

$\begin{array}[]{l}\sum_{T\in\mathcal{C}_{n}}y^{\operatorname{impe}(T)}(t+1)^{\operatorname{impp}(T)}x^{\deg_{T}(1)-1}z^{n-\operatorname{impe}(T)-\deg_{T}(1)}\\\
\hskip
40.0pt=\sum_{T\in\mathcal{O}_{n}}y^{\operatorname{impe}(T)+\operatorname{eld}(T)}t^{\operatorname{eld}(T)}x^{\operatorname{young}_{T}(1)-1}z^{n-\operatorname{impe}(T)-\operatorname{eld}(T)-\operatorname{young}_{T}(1)}.\\\
\end{array}$

Figure 4: Illustration of the bijective operation $\displaystyle\zeta_{i}$.
The vertices from $\displaystyle e_{1}$ to $\displaystyle k$ are moved as a
singular block from being leftmost children to right siblings of
$\displaystyle i$, et vice versa.

Let $\displaystyle T\in\mathcal{O}_{n}$. Let $\displaystyle i$ be a young
vertex and improper parent of $\displaystyle T$. Since $\displaystyle 1$ is a
proper parent, $\displaystyle i$ cannot be labelled $\displaystyle 1$, and we
can introduce $\displaystyle j$ as the parent of $\displaystyle i$.

######  Definition 5.2.

Let $\displaystyle\zeta_{i}(T)$ be the following transformation: if
$\displaystyle k$ is the child of $\displaystyle i$ that verifies
$\displaystyle\beta_{T}(i)=\beta_{T}(k)$, then we take $\displaystyle k$, its
left siblings and all their respective subtrees, detach them from
$\displaystyle i$ and attach them to $\displaystyle j$ in the same order
directly on the right of $\displaystyle i$.

See Figure 4 for an illustration of this definition. Note that $\displaystyle
k$ is the first younger child of $\displaystyle i$, so all of its left
siblings are elders. Since $\displaystyle i$ was young, all its left siblings
have a greater value for $\displaystyle\beta_{T}$ than $\displaystyle k$, so
they remain elders. Moreover,
$\displaystyle\beta_{zeta_{i}(T)}(i)>\beta_{zeta_{i}(T)}(k)$, so
$\displaystyle i$ becomes an elder. Since $\displaystyle i$ was young,
$\displaystyle k$ is still young in $\displaystyle\zeta_{i}(T)$. The rest of
the tree remains unchanged. Hence we have increased by one the number of
elders.

However, $\displaystyle(i,k)$ was an improper edge, which has been removed.
There are two cases to consider, first if $\displaystyle(j,i)$ was proper,
itself and the other newly created edges are proper. Otherwise, if
$\displaystyle(j,i)$ was improper, it is now proper since $\displaystyle i$ is
now elder, but $\displaystyle(j,k)$ is improper in its stead, since
$\displaystyle\beta_{T}(i)=\beta_{\zeta_{i}(T)}(k)$. In any case, the number
of improper edges decreases by exactly one. So this transformation keeps the
sum $\displaystyle\operatorname{impe}+\operatorname{eld}$ constant, and
creates exactly one elder. It does not change the number of younger children
of $\displaystyle 1$. Finally, this operation is easily reversible: for an
elder vertex $\displaystyle i$ in $\displaystyle T$, take all its right
siblings up to the first younger, and move them as its leftmost children.

Note that if $\displaystyle i$ and $\displaystyle j$ are two improper parents
of $\displaystyle T$, then
$\displaystyle\zeta_{i}\circ\zeta_{j}(T)=\zeta_{j}\circ\zeta_{i}(T)$. Hence we
can define, for $\displaystyle
S\subset\operatorname{impp}(T)\cap\operatorname{young}(T)$,

$\zeta(S,T)=\left(\underset{a\in S}{\circ}\zeta_{a}\right)(T).$

Similarly, for $\displaystyle S\subset\operatorname{eld}(T)$,

$\zeta^{-1}(S,T)=\left(\underset{a\in S}{\circ}\zeta^{-1}_{a}\right)(T).$

######  Definition 5.3.

For $\displaystyle T\in\mathcal{C}_{n}$, let the _canonical planar tree_ of
$\displaystyle T$ $\displaystyle\operatorname{R}(T)\in\mathcal{O}_{n}$ be the
only planar tree whose underlying Cayley tree is $\displaystyle T$ with only
younger vertices. In other words, its siblings are ordered from left to right
with increasing values for $\displaystyle\beta_{T}$.

Note that
$\displaystyle\deg_{T}(1)=\operatorname{young}_{\operatorname{R}(T)}(1)$. Let
$\displaystyle
Z(T)=\\{\zeta(S,\operatorname{R}(T)),S\subset\operatorname{impp}(\operatorname{R}(T))\\}$.
We can now properly prove the proposition presented at the beginning of this
section.

###### Proof of Proposition 5.1.

By construction of $\displaystyle\zeta$ as a bijection between $\displaystyle
Z(T)$ and $\displaystyle\\{(S,T),~{}S~{}\subset~{}\operatorname{impp}(T)\\}$,
for all $\displaystyle T\in\mathcal{C}_{n}$, we have

$\begin{array}[]{l}y^{\operatorname{impe}(\operatorname{R}(T))}(t+1)^{\operatorname{impp}(\operatorname{R}(T))}x^{\operatorname{young}_{\operatorname{R}(T)}(1)-1}z^{-\operatorname{impe}(\operatorname{R}(T))-\operatorname{young}_{\operatorname{R}(T)}(1)}\\\
\hskip 40.0pt=\sum_{U\in
Z(T)}y^{\operatorname{impe}(U)+\operatorname{eld}(U)}t^{\operatorname{eld}(U)}x^{\operatorname{young}_{U}(1)-1}z^{-\operatorname{impe}(U)-\operatorname{eld}(U)-\operatorname{young}_{U}(1)}.\\\
\end{array}$ (14)

Moreover, for all $\displaystyle U\in\mathcal{O}_{n}$, we have

$\displaystyle\exists
T\in\mathcal{C}_{n},\zeta^{-1}(\operatorname{eld}(U),U)=\operatorname{R}(T).$

The idea is to apply $\displaystyle\zeta^{-1}$ to every elder vertex of
$\displaystyle U$, so that the resulting tree only has younger vertices, which
means it is a canonical planar tree for some Cayley tree. This also implies
that $\displaystyle T$ is the only Cayley tree such that $\displaystyle U\in
Z(T)$. Hence, $\displaystyle\\{Z(T),T\in\mathcal{C}_{n}\\}$ is a partition of
$\displaystyle\mathcal{O}_{n}$. We conclude by summing (14) over
$\displaystyle\mathcal{C}_{n}$.

∎

##  6 Acknowledgements

We thank Matthieu Josuat-Vergès for his invaluable help and support. This
research did not receive any specific grant from funding agencies in the
public, commercial, or not-for-profit sectors.

## References

  * [1] B. Berndt.  Ramanujan’s second notebooks, part i, chap. 3: Combinatorial analysis and series inversions, 1985.
  * [2] B. C. Berndt.  of ramanujan’s second notebook.  Bulletin of the London Mathematical Society, 15(4):273–320, 1983\.
  * [3] L. J. Billera, S. P. Holmes, and K. Vogtmann.  Geometry of the space of phylogenetic trees.  Advances in Applied Mathematics, 27(4):733–767, 2001.
  * [4] F. Chapoton.  Opérades différentielles graduées sur les simplexes et les permutoedres.  Bulletin de la société mathématique de France, 130(2):233–252, 2002.
  * [5] W. Y. Chen and V. J. Guo.  Bijections behind the ramanujan polynomials.  arXiv preprint math/0107024, 2001.
  * [6] D. Dumont and A. Ramamonjisoa.  Grammaire de ramanujan et arbres de cayley.  Electron. J. Combin, 3(2), 1996.
  * [7] C. Flight.  How many stemmata?  Manuscripta, 34(2):122–128, 1990.
  * [8] V. J. Guo and J. Zeng.  A generalization of the ramanujan polynomials and plane trees.  Advances in Applied Mathematics, 39(1):96–115, 2007.
  * [9] M. Josuat-Vergès.  Derivatives of the tree function.  The Ramanujan Journal, 38(1):1–15, 2015.
  * [10] S. Ramanujan et al.  Notebooks of Srinivasa Ramanujan, volume 2.  Springer, 2013.
  * [11] U. S. Reddy.  Term rewriting induction.  In International Conference on Automated Deduction, pages 162–177. Springer, 1990.
  * [12] P. W. Shor.  A new proof of cayley’s formula for counting labeled trees.  Journal of Combinatorial Theory, Series A, 71(1):154–158, 1995\.
  * [13] D. Speyer and B. Sturmfels.  The tropical grassmannian.  Advances in Geometry, 4(3):389–411, 2004.
  * [14] J. Zeng.  A ramanujan sequence that refines the cayley formula for trees.  The Ramanujan Journal, 3(1):45–54, 1999.