2
$\begingroup$

This is a continuation of my post Number of bounded Dyck paths with "negative length".

Let $C_{n}^{(2k+1)}$ be the number of Dyck paths of semilength $n$ bounded by $2k+1.$ They satisfy a recursion of order $2k + 1.$

Let $C_{ - n}^{(2k + 1)}$ be the numbers obtained by extending the sequence $C_{n}^{(2k+1)}$ to negative $n$ using this recursion.

Computations suggest that this extension can also be obtained via Hankel determinants: $$C_{ - n}^{(2k + 1)} = \det \left( {C_{n + 1 + i + j}^{(2k + 1)}} \right)_{i,j = 0}^{k - 1}.$$ For $k=1$ this reduces to $C_{ - n}^{(3)} = C_{n + 1}^{(3)}.$ This can easily be verified since the sequence $(\dots 34, 13, 5, 2 |1,1,2,5,13,34,\dots$ satisfies $a(n)-3a(n-1)+a(n-2)=0.$

For $k = 2$ we get the sequence $\left( { \cdots ,70,14,3,\left| {1,1,2,5,14,42,131, \cdots } \right.} \right).$ For example $C_{ - 1}^{(5)} = \det \left( {\begin{array} \\ 2 &5 \\ 5&{14} \end{array}} \right) = 3,$ This has been observed by Michael Somos, cf. OEIS A080937.

Any idea how to prove the general case?

$\endgroup$
2
  • $\begingroup$ These kind of Hankel determinants have a nonintersecting lattice path interpretation (see Section 3.1.6, Example 4 of arxiv.org/abs/1409.2562); maybe that could be helpful here. $\endgroup$ – Sam Hopkins Sep 28 '20 at 16:18
  • $\begingroup$ Maybe you should update the question to mention the combinatorial interpretation of $C^{(2k+1)}_{-n}$ proved by Richard Stanley in the linked question. $\endgroup$ – Sam Hopkins Sep 30 '20 at 19:53
2
$\begingroup$

Here's how I think this can be proved based on what Richard Stanley already did in your previous question.

If we take the network in Section 3.1.6, Example 4 part (a) of https://arxiv.org/abs/1409.2562 and remove everything above height $2k+1$, then the entries of your Hankel determinant count the paths from sources to sinks for this network, and hence by the Lindström-Gessel-Viennot lemma, the determinant is the number of nonintersecting families of paths. These nonintersecting families of paths in turn correspond to $k$-fans of $3$-bounded Dyck paths of semilength $n$ (see the explanation/terminology in Ardila). And $k$-fans of $3$-bounded Dyck paths of semilength $n$ are easily seen to be the the same thing as $k$-bounded $P$-partitions where $P$ is the $2n-1$-element zigzag poset. In his answer to your previous question, Richard Stanley explained why these $P$-partitions are enumerated by $C^{(2k+1)}_{-n}$.

EDIT:

For clarity, here's an example of the kind of network + families of nonintersecting paths:

enter image description here

This depicts the things counted by $C^{(7)}_{-4}$. We convert the nonintersecting lattice paths to the sequences mentioned in Richard Stanley's answer by stacking the $k$ orange $3$-bounded Dyck paths on top of one another (they are a fan, i.e., nest, by the nonintersecting condition), and then reading off $1$ plus the number of Dyck paths below the "circles" (which form a length $2n-1$ zigzag poset). In the depicted case we have $(a_1,\ldots,a_7)=(3,4,1,1,1,2,1)$.

This raises an interesting possibility:

Let's let $\mathcal{D}_k$ denote the infinite network where we take a diagonal slice of width $2k+1$ of the 2D grid, with all edges directed right and up. The above discussion explains that there is a relationship (in fact, a "reciprocity" relationship) between counting families of nonintersecting paths in this network with $1$ source and $1$ sink (these are what $C^{(2k+1)}_{n}$ count), and counting such families with $k$ sources and $k$ sinks (these are what $C^{(2k+1)}_{-n}$ count).

Question: Is there a similar "reciprocity" relationship between counting families of nonintersecting lattice paths in $\mathcal{D}_k$:

  • when we have $i$ consecutive sources, then a gap of some size, then $i$ consecutive sinks;
  • and when we have $k+1-i$ consecutive sources, then a gap of some size, then $k+1-i$ consecutive sinks?

Note that when we have $k+1$ consecutive sources and then a gap and then $k+1$ consecutive sinks, there's a unique family of nonintersecting lattice paths in $\mathcal{D}_k$; this "agrees" with the fact that there is a unique such family when we have 0 sources and sinks as well. In other words, we can say yes to this question when $i=0,1$.

(UPDATE: I asked this as a separate question - Reciprocity for fans of bounded Dyck paths - and it got a wonderful positive answer by Gjergji Zaimi.)

EDIT 2:

I have to mention that this set up bears a lot of similarity to another context in which reciprocity results are studied: namely, for dimer coverings (a.k.a. perfect matchings) of linearly growing graphs. Some papers in that vein are:

et cetera. Dimer coverings are not exactly the same as nonintersecting paths, but the two can often be related, and so it is possible the counting problems under consideration here could be understood in terms of that existing literature.

$\endgroup$
8
  • $\begingroup$ This looks very nice, but I do not see how to place the circles to get (3,4,1,1,1,2,1) in your figure. $\endgroup$ – Johann Cigler Oct 1 '20 at 15:06
  • $\begingroup$ If we draw the full staircase of boxes above the Dyck paths, the circles are the two bottom/largest ranks; they make up a zigzag poset: en.wikipedia.org/wiki/Fence_(mathematics) $\endgroup$ – Sam Hopkins Oct 1 '20 at 15:08
  • $\begingroup$ @JohannCigler: You should also see my follow-up question for a more general result (and I think the right context for understanding your original observation): mathoverflow.net/questions/373030/… $\endgroup$ – Sam Hopkins Oct 1 '20 at 15:12
  • $\begingroup$ Sorry, I am confused. I still don't see it. $\endgroup$ – Johann Cigler Oct 1 '20 at 15:25
  • $\begingroup$ Do you see how the "orange" portions of the 3 nonintersecting lattice paths become 3 Dyck paths which form a fan, i.e., nest inside of one another? $\endgroup$ – Sam Hopkins Oct 1 '20 at 15:29
1
$\begingroup$

As stated in the previous question, $C_n^{(2k+1)}$ satisfies $$\sum_{j=0}^{k+1} (-1)^j \binom{2k+2-j}{j} C_{n-j}^{(2k+1)}=0.$$ The formula $$C_{ - n}^{(2k + 1)} = \det \left( {C_{n + 1 + i + j}^{(2k + 1)}} \right)_{i,j = 0}^{k - 1}$$ now follows from my answer to the recent question by Johann. Perhaps, this formula was the motivation for this new question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.