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.

mightallow us to treat both $t \dfrac{\partial}{\partial t}$ and $t + t^{-1}$ as some kind of scalars). $\endgroup$ – darij grinberg Jul 4 '17 at 10:12