# Reciprocity for fans of bounded Dyck paths

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$$).

• You can safely drop the word "conjecture" from "Conjecture/Proposition" - its argument is valid. Furthermore, the reciprocity in question would follow from the relationship between the transfer matrices for $(k,i)$ and $(k,k+1-i)$ -- their characteristic polynomials appear to be negated reciprocals of each other. I've tested this for many small values of $k,i$. – Max Alekseyev Oct 1 at 4:53
• I wonder what this might mean in terms of semistandard tableaux! (I can only look into it later today) – Martin Rubey Oct 1 at 6:10
• The sequence $n \mapsto |SSYT(n\lambda,m)|$ is a polynomial in n, and thus satisfies a linear recursion. Perhaps its something like this? – Per Alexandersson Oct 1 at 6:54
• What I meant to ask is: what does the reciprocity mean in terms of semistandard tableaux. – Martin Rubey Oct 1 at 7:01
• If you're a fan of bounded Dyck paths, have I got some reciprocity for you! – LSpice Oct 1 at 13:46

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.