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](https://math.stackexchange.com/questions/2331695/solve-a-first-order-non-linear-pde-or-just-find-a-residue-of-the-solution), 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.



Counting some binary trees with lots of extra stucture
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.


