The crossing-nesting enumeration conjecture for the forest-matrix first column

Proof of the forest-matrix crossing–nesting conjecture

We prove Conjecture 6.16 of T. Gilmore, Trees, Forests, and Total Positivity: I. $q$-Trees and $q$-Forests Matrices, Electronic Journal of Combinatorics 28 (2021), #P3.54, doi:10.37236/10465. The same statement is Conjecture 6.11 in the earlier arXiv version. In fact, the argument identifies the complete matrix, not merely its first nonzero column, for an arbitrary sequence of weights.

Let $R$ be any commutative ring and fix arbitrary elements

$$\alpha_1,\alpha_2,\ldots\in R. \tag{1}$$

Define the unit lower-triangular matrix $T=(T_{i,j})_{i,j\geq0}$ by

$$T_{i,j}= \begin{cases} \displaystyle\prod_{h=j+1}^{i}\alpha_h,&i\geq j,\\ 0,&i<j. \end{cases} \tag{2}$$

For $a\geq1$, put $E_a=I_a\oplus T$. The infinite product

$$A=\cdots E_3E_2E_1 \tag{3}$$

is well defined entrywise, since $E_a$ fixes the first $a$ rows and columns. Removing its rightmost factor and shifting the remaining factors one index gives

$$A=(1\oplus A)(1\oplus T)=1\oplus(AT). \tag{4}$$

Consequently, $A_{0,0}=1$, $A_{n,0}=0$ for $n>0$, and, whenever $n,k\geq1$,

$$A_{n,k} =\sum_{j=k-1}^{n-1} A_{n-1,j}\prod_{h=k}^{j}\alpha_h. \tag{5}$$

An empty product equals one. The initial transition is therefore $0\to1$, with weight one. Every subsequent transition $j\to k$ has $1\leq k\leq j+1$ and weight

$$w(j,k)=\prod_{h=k}^{j}\alpha_h. \tag{6}$$

Represent state $j\geq1$ by height $j-1$. Replace the transition $j\to k$ by one up-step followed by $j-k+1$ down-steps:

$$j\longrightarrow k \quad\longleftrightarrow\quad U D^{\,j-k+1}. \tag{7}$$

Assign weight one to every up-step and weight $\alpha_h$ to a down-step from height $h$ to height $h-1$. The block in (7) then has weight precisely (6). All its intermediate heights are nonnegative because its final height is $k-1\geq0$. Conversely, every nonnegative up/down path decomposes uniquely into blocks consisting of an up-step and all subsequent down-steps before the next up-step. Thus (5) yields the stronger complete-matrix formula

$$A_{n,k} =\sum_{\substack{P\text{ nonnegative up/down path}\\ \#U(P)=n-1,\ \#D(P)=n-k}} \prod_{D:h\to h-1}\alpha_h, \qquad 1\leq k\leq n. \tag{8}$$

In particular, $k=1$ gives Dyck paths of semilength $n-1$. First-return decomposition therefore gives

$$\sum_{n\geq1}A_{n,1}z^{n-1} =\cfrac{1}{1-\cfrac{\alpha_1z}{1-\cfrac{\alpha_2z}{1-\cfrac{\alpha_3z}{\ddots}}}}. \tag{9}$$

Now specialize to $R=\mathbb Z[r,s]$ and

$$\alpha_h=[h]_{r,s} =\sum_{a=0}^{h-1}r^{h-1-a}s^a. \tag{10}$$

Gilmore’s published equations (6.107)–(6.109), specialized at $\mu=y=1$, give exactly the factorization (3), because every inverse-bidiagonal factor has entries

$$T_{i,j} =\frac{[i]_{r,s}!}{[j]_{r,s}!} =\prod_{h=j+1}^{i}[h]_{r,s}. \tag{11}$$

The quotient notation in (11) denotes the displayed polynomial product; no division or invertibility in $R$ is required. Hence

$$A_{n,k}=m_{n,k}(r,s,1,1). \tag{12}$$

Finally, encode a perfect matching on $[2m]$ by scanning its vertices from left to right. An opening endpoint gives an up-step; a closing endpoint gives a down-step. Suppose a closing endpoint occurs while $h$ arcs are open, and its matching opener is the $(a+1)$-st open arc from the left. Its closure creates $a$ nestings and $h-1-a$ crossings. Summing its weight over the $h$ possible open arcs gives

$$\sum_{a=0}^{h-1}r^{h-1-a}s^a=[h]_{r,s}. \tag{13}$$

Each crossing or nesting is counted exactly when the first of its two arcs closes. Thus, for every $m\geq0$,

$$\sum_{M\in\mathcal M_{2m}}r^{\operatorname{cr}(M)}s^{\operatorname{ne}(M)} =\sum_{\substack{P\text{ Dyck}\\operatorname{semilength}(P)=m}} \prod_{D:h\to h-1}[h]_{r,s}. \tag{14}$$

Combining (8), (12), and (14) proves, for every $n\geq1$,

$$\boxed{\displaystyle m_{n,1}(r,s,1,1) =\sum_{M\in\mathcal M_{2(n-1)}} r^{\operatorname{cr}(M)}s^{\operatorname{ne}(M)}.} \tag{15}$$

The conjecture asks for $n>1$; the proof also includes the empty matching at $n=1$. Equation (9) additionally corrects the index shift in the published equation (6.131): the appropriate continued-fraction coefficient is $[z^{n-1}]$, not $[z^n]$. Formula (8) establishes the strictly stronger identification of every matrix entry with a weighted ballot-path enumerator, valid for arbitrary weights over any commutative ring.