Reciprocity for fans of bounded Dyck paths

Question

This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel determinants.

Let $\mathcal{D}(k,n)$ denote the following planar directed graph: It has $k+1$ vertices in the leftmost column and $n+1$ vertices in the bottom row. It always has an odd number of columns, and even number of rows. Also, all edges are directed from left to right.

For $0\leq i \leq k+1$, let $C(k,i;n)$ denote the number of $i$-tuples of nonintersecting lattice paths in $\mathcal{D}(k,n)$ which connect the bottom $i$ vertices of the leftmost column to the bottom $i$ vertices of the rightmost column.

Note that these tuples of nonintersecting lattice paths could also be called $i$-fans of $(2k+1-2(i-1))$-bounded Dyck paths of semilength $n$.

There is of course a Lindström-Gessel-Viennot determinantal expression for $C(k,i;n)$.

Conjecture/Proposition: As a function of $n$, $C(k,i;n)$ satisfies a linear recurrence with constant coefficients.

The reason this should be true is via a "transfer matrix"-style argument. We can make $\mathcal{D}(k,n+1)$ from $\mathcal{D}(k,n)$ by adding two columns on the right; and if we consider $i$-tuples of nonintersecting lattice paths in $\mathcal{D}(k,n)$ that start at the bottom $i$ vertices of the leftmost column, there are finitely many patterns of sinks at which they could terminate at; and in turn there are a fixed number of ways to continue these patterns for the two additional columns.

If that is indeed so, then we can define $C(k,i;-n)$ at negative values via the recurrence.

Question: Do we have the "reciprocity" result that $C(k,i;-n)=C(k,k+1-i;n+1)$?

The resolution of the previous questions implies that this is true for $i=1$ (and it is trivially true for $i=0$).

EDIT: Gjergji and I have now written a paper -- on the arXiv at https://arxiv.org/abs/2301.00405 -- explaining the general combinatorial reciprocity result for nonintersecting paths in a growing network, and going over some applications including to these bounded Dyck paths.

Answer 1

Let's say we have $n+1$ sets of vertices $V_t$, and for each $0\le t\le n$ we have $|V_t|=k+1$. The subsets of $V_t$ will often be identified with subsets of $\{1,2,\dots,k+1\}$.

Given some directed graph $G$ with $k+1$ sources and $k+1$ sinks satisfying the conditions of Lindström–Gessel–Viennot, we can form a graph $\widehat{G}_n$ by gluing together $n$ copies of $G$ as follows: for all $t$, the $t$-th copy has its sources identified with $V_{t-1}$ and its sinks identified with $V_t$.

Let $A$ be the $(k+1)\times (k+1)$ matrix whose $(i,j)$ entry counts the number of paths from source $i$ to sink $j$ in $G$. Let's denote by $A_s$ the matrix of $s\times s$-minors of $A$. The Lindström–Gessel–Viennot lemma tells us that the number of non-intersecting paths connecting $s$ sinks to $s$ sources in $G$ is the appropriate entry in $A_s$. Therefore the generating function for non-intersecting s-tuples of paths in graphs $\widehat{G}_n$ is given by $$\sum_{n\geq 0} C(k,s,n)x^n=(I-xA_s)^{-1}$$ where $C(k,s,n)$ denotes the $\binom{k+1}{s}\times\binom{k+1}{s}$ matrix where each entry counts the number of nonintersecting paths connecting the appropriate subsets of sinks and sources. This is just a rephrasing of the transfer matrix argument, and we see that each entry of $C(k,s,n)$ satisfies a linear recurrence. For the negative extension we obtain the generating function $$\sum_{n\geq 1} C(k,s,-n)x^n=-(I-x^{-1}A_s)^{-1}=xA_s^{-1}(I-xA_s^{-1})^{-1}$$ therefore $\sum_{n\geq 0} C(k,s,-n)=(I-xA_s^{-1})^{-1}$. Now up to a factor of $\det A$ (which for your original graph is 1) the inverse of the s-compound matrix is the s-adjugate matrix. When you unpack what this means for our situation it says that $$C(k,s,-n)_{I,J}=(-1)^{\sigma(I)+\sigma(J)}C(k,k+1-s,n)_{J^{c}, I^{c}}$$ where $I,J$ are subsets of size $s$ that index the sources/sinks and $\sigma(I)$ is the sum of the elements in $I$. This reciprocity is true for all graphs $G$ that have $\det A=1$.

Now returning to your graph, we have another symmetry at our disposal. Choosing $I$ to be be the lowest $s$ vertices we obtain from the argument above that $C_{I,I}(k,s,-n)=C_{I^c,I^c}(k,k+1-s,n)$. We observe that there is a very easy bijection between the non-intersecting family of paths joining the lowermost $k+1-s$ sources/sinks in $\mathcal D(k,n+1)$ and the non-intersecting family of paths joining the uppermost $k+1-s$ sources/sinks in $\mathcal D(k,n)$ (erase the first and last column and flip everything upside down). This proves the statement in your question.