Counting some binary trees with lots of extra stucture

Question

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.

Answer 1

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.