# Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem.

Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ internal nodes (internal node = node with children), with each node labeled by an integer (labels need not be unique, negatives are allowed), with the root labeled $k$, and the label of each internal node is equal to the sum of the labels of the children, and each leaf is labeled either $1$ or $-1$. The weight (which may be negative) assigned to such a tree is the product of the labels of the internal nodes. Furthermore, there is an ordering of the internal nodes such that a parent always comes before a child.

For example, $D(1,2) = 4$, with the trees

      1
2  -1
1 1


and

     1
-1  2
1 1


each counted with weight 2 (and each of these has only one possible ordering of the internal nodes).

In the end, I'm actually only interested in the sequence $D(1,2i)$. This sequence appears to be http://oeis.org/A151403, which counts a certain type of lattice paths in the first quadrant, and is equal to $4^i$ times the $i^{th}$ Catalan number.

But I defined $D(k,n)$ because then you can get the recurrence relation $$D(k,n) = k \sum_{a+b=k} \sum_{c+d=n-1} \binom{n-1}{c} D(a,c) D(b,d)$$ where $c,d \ge 0$ but $a,b$ are any integers. We have initial conditions $D(\pm1,0) = 1$ and $D(k,0) = 0$ otherwise. It is easy to see that $D(k,n) = 0$ if $|k| > n+1$, so the sum here is finite.

(Each child node starts a new tree, the factor of $k$ takes care of the weight, and the $\binom{n-1}{c}$ is the number of ways of "interweaving" the ordering.)

With some computation, I was able to guess the formula for $D(k,n)$. We have $$D(k,k-1) = 2 (2k)^{k-2}$$ and if $n-k+1 \neq 0$, then $$D(k,n) = (2k)^n \binom{n}{\frac{n-k-1}{2}} \frac{2}{n-k+1}$$ (where the binomial coefficient is 0 if $\frac{n-k-1}{2}$ is not an integer or is negative).

How can I prove the formula for $D(1,2i)$?

(1) I could try to use induction and the recurrence formula, but that seems messy.

(2) It seems more nice to provide a bijection between these funny trees and the lattice paths or something on the A151403 page. But this seems tricky with the weights (especially since some are negative).

(3) I can turn the recurrence relation into a two variable generating function and get a PDE, but it doesn't look like I can get a solution explicit enough to be useful.

I though I would ask in case this is well known to someone with more experience in tree/lattice path counting.

• If I define a power series $R\in \mathbb{Q}\left[t,t^{-1}\right]\left[\left[x\right]\right]$ by $R = \sum\limits_{n=1}^\infty \sum\limits_{k\in\mathbb{Z}} Q\left(n,k\right) t^k \dfrac{x^n}{\left(n-1\right)!}$, then it satisfies $R = x \left(t \dfrac{\partial}{\partial t} R^2 + \left(t + t^{-1}\right)\right)$, right? Maybe Lagrange inversion is not totally hopeless (particularly since there is such a thing as noncommutative Lagrange inversion, which might allow us to treat both $t \dfrac{\partial}{\partial t}$ and $t + t^{-1}$ as some kind of scalars). Jul 4 '17 at 10:12
• By $Q(n,k)$ you mean $D(k,n)$? I don't think that is quite right, e.g. R should have some degree 0 part in $x$. I believe the equation in the link is correct. In particular, I don't know how to get away with a derivative in only one variable.
– Drew
Jul 11 '17 at 22:36
• Oops, yes, I mean $D\left(k,n\right)$. But the differential equation looks right to me; it follows straight from your recursing. Why should there be a constant term? Jul 13 '17 at 1:14
• I was thinking that $D(\pm1,0)$ should give terms $x^0t$ and $x^0t^{-1}$. But I guess you are starting your sum at $n=1$? Another question: From your differential equation, it seems that the term $xt$ appears in $R$, which implies that $D(1,1)=1$. But $D(1,1)=0$.
– Drew
Jul 13 '17 at 16:24
• Oh! Maybe it should be $R = x \left( t \dfrac{\partial}{\partial t} R^2 + \left(t^2 + t^{-2}\right) \right)$. Sorry for this! Jul 13 '17 at 16:27

I was able to find an interesting generalization of your formula, but I'm having trouble finding a reference in the literature.

Let's call a 0-1-2 tree, a rooted tree where every vertex can have no child, a left child, a right child, or both. Let's call such a tree increasing if we also have a total ordering on the vertices where each parent is less than their child. We will denote by $B_n$ the set of increasing 0-1-2 trees on $n$ vertices. There is an obvious way to append $n+1$ new leaves to a tree $T\in B_n$ to make it a full binary tree where the internal vertices correspond exactly to the vertex set of $T$. Let's call this binary tree $\tilde{T}$.

Suppose we associate a variable $x_1,x_2,\dots,x_{n+1}$ to each leaf. Then every vertex in $\tilde{T}$ has a weighted hook-length given by the sum of the variables associated to each leaf it covers (i.e., to each leaf that is a descendant of this vertex). The weight of $\tilde{T}$ is the product of these hook-lengths over all internal vertices. Let's define a polynomial $\tilde{T}(x_1,x_2,\dots,x_{n+1})$ to be the sum of the weight of $\tilde{T}$ over all permutations of $x_1,\dots,x_{n+1}$.

For example starting with the tree in $B_2$

      1
2


we can extend it to

      1          1          1          1          1          1
2  z   ,   2  z   ,   2  y   ,   2  y   ,   2  x   ,   2  x
x y        y x        x z        z x        y z        z y


so its polynomial is $$\tilde{T}(x,y,z)=\sum_{\text{Sym}}(x+y)(x+y+z)=4(x+y+z)^2.$$ We can define $$F_n(x_1,x_2,\cdots,x_{n+1})=\sum_{T\in B_n}\tilde{T}(x_1,x_2,\dots,x_{n+1}),$$ so that, for example, $F_2(x_1,x_2,x_3)=8(x_1+x_2+x_3)^2$, by the above. We also regard the empty graph as a 0-1-2 tree, with weight $1$.

Now we can state the result in general:

Theorem: For all $n\in \mathbb N$ we have the following identity $$F_n(x_1,x_2,\dots,x_{n+1})=2^n n!(x_1+x_2+\cdots+x_{n+1})^{n}.$$

Proof: Let $\mathcal P'$ be the set of subsets of $\{x_1,x_2,\dots,x_{n+1}\}$ except for the empty set and the full set. First we notice that the root of a binary tree $\tilde{T}$ always has hook-length $(x_1+\cdots +x_{n+1})$. Next notice that two increasing 0-1-2 trees of sizes $a,b$, respectively, combine together to form another 0-1-2 tree of size $a+b+1$, but the ordering can be extended in $\frac{(a+b)!}{a!b!}$ ways. This gives us the recurrence $$F_n(x_1,x_2,\cdots,x_{n+1})=(x_1+x_2+\cdots+x_{n+1})\sum_{S\in \mathcal P'}\binom{n-1}{|S|-1}F_{|S|-1}(S)F_{n-|S|}(S^{c}).$$

This will allow us to prove our theorem inductively.

From here we will make use of the weighted Cayley formula for labeled trees on a set $S={1,2,\dots,p}$, which can be obtained from the matrix tree theorem. It says that $$y_1y_2\cdots y_p(y_1+y_2+\cdots+y_p)^{p-2}=\sum_{T}y_1^{\deg 1}\cdots y_p^{\deg p}$$ where the sum on the right runs over all labeled trees and keeps track of the degree of each vertex. If instead we enumerated rooted labeled trees and thought of the root as having a "half edge" (so its degree is increased by 1) then we get $y_1y_2\cdots y_p(y_1+y_2+\cdots+y_p)^{p-1}$. Now a tree on the vertex set $\{1,2,\dots,n+1\}$ can be constructed by making a rooted tree on vertex sets $S\in \mathcal P$ and $S^{c}$ and then joining the roots. This way a tree is constructed exactly $2n$ times: because there are $n$ edges to choose for the splitting, and then ordering the two subsets.

So by Cayley's formula we get $$\sum_{S\in \mathcal P}\left(\prod_{i\in S}x_i\left(\sum_{i\in S}x_{i}\right)^{|S|-1}\cdot\prod_{i \in S^c}x_i\left(\sum_{i\in S^{c}}x_i\right)^{n-|S|}\right)=2nx_1x_2\cdots x_{n+1}(x_1+\cdots+x_{n+1})^{n-1}$$ $$\iff \sum_{S\in \mathcal P}\left(\left(\sum_{i\in S}x_{i}\right)^{|S|-1}\cdot\left(\sum_{i\in S^{c}}x_i\right)^{n-|S|}\right)=2n(x_1+\cdots+x_{n+1})^{n-1}$$ which tells us $$(x_1+x_2+\cdots+x_{n+1})\sum_{S\in \mathcal P'}\binom{n-1}{|S|-1}F_{|S|-1}(S)F_{n-|S|}(S^{c})=2^nn!(x_1+x_2+\cdots+x_{n+1})^n$$ giving us the induction step. $\blacksquare$

Now to get to your problem we will put $\frac{n+k+1}{2}$ of the variables equal to $1$, and the remaining ones to $-1$. This is equivalent to enforcing the root to be labeled $k$ in your notation. However my function $$F_n(1,\dots,1,-1,\dots,-1)=2^nn!k^n$$ enumerates the variables as distinct so we have to divide by $\left(\frac{n+k+1}{2}\right)!\left(\frac{n-k+1}{2}\right)!$ in order to make the 1's indistinguishable, and similarly for the -1's. Finally we can say for your function $$D(k,n)=\frac{(2k)^nn!}{\left(\frac{n+k+1}{2}\right)!\left(\frac{n-k+1}{2}\right)!}$$ as you had predicted.

• There may be an issue in the proof of the Theorem, due to the fact that binary trees are not exactly trees; they also have a left-right distinction for the two children of each vertex. Maybe there are some missing $2^n$ factors around, although I think the tweaks should be easy. (Sorry for vagueness; I'm time-constrained.) Jul 16 '17 at 13:13
• @darijgrinberg In the proof of the theorem we only use binary trees for setting up the recursive identity, which does depend on the left/right distinction. Then after stating the identity we need to prove, we use calculations with general labeled trees. Jul 16 '17 at 16:55
• I haven't had the leisure to think carefully about the combinatorics here, but I just wanted to mention that there is an alternative pathway from the recurrence in the proof of your Theorem to your Theorem. Namely, once you have that recurrence for $F_n$, it suffices to prove that the right hand side satisfies a ... Jul 21 '17 at 16:48
• ... parallel recurrence: parallel recurrence: $2^n n! \left(x_1+x_2+\cdots+x_{n+1}\right)^n$ $= \left(x_1+x_2+\cdots+x_{n+1}\right)$ $\sum_{S \in \mathcal{P}'} \dbinom{n-1}{\left|S\right|-1} 2^{\left|S\right|-1} \left(\left|S\right|-1\right)! \left(\sum_{x \in S} x\right)^{\left|S\right|-1} 2^{\left|S^c \right|-1} \left(\left|S^c\right|-1\right)! \left(\sum_{x \in S^c} x\right)^{\left|S^c\right|-1}$. This recurrence easily boils do the following ... Jul 21 '17 at 16:49
• Darij, thanks! I was really hoping there was a quicker algebraic proof. Jul 21 '17 at 16:50