# An enumeration problem for Dyck paths from homological algebra

In their article "On n-Gorenstein rings and Auslander rings of low injective dimension" Fuller and Iwanaga gave a homological characterisation of 2-Gorenstein Nakayama algebras with global dimension at most three, see theorem 3.16. there. Now Nakayama algebras (we always assume they are acyclic) are in natural bijection to Dyck paths. Call a Dyck path nice in case the corresponding Nakayama algebra is 2-Gorenstein with global dimension at most 3, see below for an elementary combinatoria description. I noticed with the computer that nice Dyck paths seem to be enumerated by $$2^{n-2}$$ (thats why I call them nice) and the subclass of nice Dyck paths with global dimension at most two by the Fibonacci numbers. This leads to the following question:

Question 1: Is there is a bijective proof mapping nice Dyck paths to some known/nice combinatorial objects?

Furthermore, to every nice Dyck path there is associated a canonical bijection and I wonder what this bijection is (there is a motivation to call this bijection homological rowmotion as it generalises the classical rowmotion from certain posets to more general combinatorial objects such as certain Dyck paths).

Question 2: What is the associated bijection to a nice Dyck path?

I currently have no elementary description so question 2, is more of a guess from the data what it might be.

An $$n$$-Kupisch series (which we can identify with a Dyck path via its area sequence) is a list of $$n$$ numbers $$c:=[c_1,c_2,...,c_n]$$ with $$c_n=1$$, $$c_i \ge 2$$ for $$i \neq n$$ and $$c_i-1 \leq c_{i+1}$$ for all $$i=1,...,n-1$$ and setting $$c_0:=c_n$$. The number of such $$n$$-Kupisch series is equal to $$C_{n-1}$$ (Catalan numbers).

Here are some examples of the nice Dyck paths for small $$n$$ together with the bijection on $$\{1,..,n\}$$.

$$n=2$$:

   [ [ 2, 1 ], [ [ 1, 2 ], [ 2, 1 ] ] ]


$$n=3$$:

  [ [ 2, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 2 ] ] ],

[ [ 3, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ] ]


n=4:

   [ [ 2, 2, 2, 1 ], [ [ 1, 4 ], [ 2, 1 ], [ 3, 2 ], [ 4, 3 ] ] ],

[ [ 3, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 4 ], [ 3, 1 ], [ 4, 3 ] ] ],

[ [ 2, 3, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 4 ], [ 4, 2 ] ] ],

[ [ 4, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ] ]


n=5:

   [ [ [ 3, 2, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 5 ], [ 3, 1 ], [ 4, 3 ], [ 5, 4 ] ] ],

[ [ 2, 3, 2, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 5 ], [ 4, 2 ], [ 5, 4 ] ] ],

[ [ 4, 3, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 5 ], [ 4, 1 ], [ 5, 4 ] ] ],

[ [ 2, 2, 3, 2, 1 ], [ [ 1, 4 ], [ 2, 1 ], [ 3, 2 ], [ 4, 5 ], [ 5, 3 ] ] ],

[ [ 3, 2, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 4 ], [ 3, 1 ], [ 4, 5 ], [ 5, 3 ] ] ],

[ [ 3, 3, 3, 2, 1 ], [ [ 1, 5 ], [ 2, 4 ], [ 3, 1 ], [ 4, 2 ], [ 5, 3 ] ] ],

[ [ 2, 4, 3, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 4 ], [ 4, 5 ], [ 5, 2 ] ] ],

[ [ 5, 4, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5, 1 ] ] ]


n=6:

   [ [ 2, 3, 2, 2, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 6 ], [ 4, 2 ], [ 5, 4 ], [ 6, 5 ] ] ],

[ [ 4, 3, 2, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 6 ], [ 4, 1 ], [ 5, 4 ], [ 6, 5 ] ] ],

[ [ 2, 2, 3, 2, 2, 1 ], [ [ 1, 4 ], [ 2, 1 ], [ 3, 2 ], [ 4, 6 ], [ 5, 3 ], [ 6, 5 ] ] ],

[ [ 3, 2, 3, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 4 ], [ 3, 1 ], [ 4, 6 ], [ 5, 3 ], [ 6, 5 ] ] ],

[ [ 2, 4, 3, 2, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 4 ], [ 4, 6 ], [ 5, 2 ], [ 6, 5 ] ] ],

[ [ 5, 4, 3, 2, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 6 ], [ 5, 1 ], [ 6, 5 ] ] ],

[ [ 3, 2, 2, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 5 ], [ 3, 1 ], [ 4, 3 ], [ 5, 6 ], [ 6, 4 ] ] ],

[ [ 2, 3, 2, 3, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 5 ], [ 4, 2 ], [ 5, 6 ], [ 6, 4 ] ] ],

[ [ 4, 3, 2, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 5 ], [ 4, 1 ], [ 5, 6 ], [ 6, 4 ] ] ],

[ [ 3, 3, 3, 3, 2, 1 ], [ [ 1, 5 ], [ 2, 6 ], [ 3, 1 ], [ 4, 2 ], [ 5, 3 ], [ 6, 4 ] ] ],

[ [ 4, 3, 3, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 6 ], [ 3, 5 ], [ 4, 1 ], [ 5, 3 ], [ 6, 4 ] ] ],

[ [ 2, 2, 4, 3, 2, 1 ], [ [ 1, 4 ], [ 2, 1 ], [ 3, 2 ], [ 4, 5 ], [ 5, 6 ], [ 6, 3 ] ] ],

[ [ 3, 2, 4, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 4 ], [ 3, 1 ], [ 4, 5 ], [ 5, 6 ], [ 6, 3 ] ] ],

[ [ 3, 3, 4, 3, 2, 1 ], [ [ 1, 5 ], [ 2, 4 ], [ 3, 1 ], [ 4, 2 ], [ 5, 6 ], [ 6, 3 ] ] ],

[ [ 2, 5, 4, 3, 2, 1 ], [ [ 1, 3 ], [ 2, 1 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 2 ] ] ],

[ [ 6, 5, 4, 3, 2, 1 ], [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 1 ] ] ] ]


In the following I give the elemenatary combinatorial description of nice Dyck paths. Sadly, it is quite complicated at the moment despite the possibly very nice enumeration.

I found the following combinatorial characterisation of those Dyck paths (compare with Combinatorics problem related to Motzkin numbers with prize money I ):

The CoKupisch series $$d$$ of $$c$$ is defined as $$d=[d_1,d_2,...,d_n]$$ with $$d_i:= \min \{k | k \geq c_{i-k} \}$$ and $$d_1=1$$. One can show that the $$d_i$$ are a permutation of the $$c_i$$. A number $$a \in \{1,...,n \}$$ is a descent if $$a=1$$ or $$c_a >c_{a-1}$$. Define a corresponding set, indexed by descents: $$X_1 := \{1,2,...,c_1-1 \}$$, and $$X_a := \{ c_{a-1}, c_{a-1}+1 ,..., c_a -1 \}$$ for descents $$a > 1$$.

A $$n$$-Kupisch series is called $$2-$$Gorenstein if it satisfies the following condition:

1. condition: for each descent $$a$$, and each $$b \in X_a$$: either $$c_{a+b} \geq c_{a+b-1}$$ or $$d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$$ is satisfied.

Now an $$n$$-Kupisch path is nice if and only if it is 2-Gorenstein and it has global dimension at most 3. Sadly there is no nice formal description of global dimension at most 3 but it can be pictured in a nice way in a Dyck path.

Call an $$i$$ with $$1 \leq i \leq n-1$$ good in case one of the following three conditions hold:

• $$c_{i+1}=c_i -1$$ (equivalent to the simple module $$S_i$$ having projective dimension one)

• ($$c_{i+1}>c_i-1$$ and $$c_{i+c_i}=c_{i+1}-c_i+1$$) (equivalent to $$S_i$$ having projective dimension two)

• ($$c_{i+1}>c_i-1$$ and $$c_{i+c_i}>c_{i+1}-c_i+1$$ and $$c_{i+c_{i+1}+1}=c_{i+c_i}-c_{i+1}+c_i-1$$) (equivalent to $$S_i$$ having projective dimension three)

Now the 2. condition is:

1. condition: Every $$i$$ with $$1 \leq i \leq n-1$$ is good.

So an n-Kupisch series (=Dyck path) is nice if and only if it satisfies condition 1. and 2.

This is a conjectural answer.

Let $$w = 0\dots01$$ be a binary word of length $$n$$. Then $$\phi(w)$$ is the Dyck path $$U^{(n+1)/2} (UD)^{(n-1)/2} D^{(n+1)/2}$$ if $$n$$ is odd and $$U^{n/2} (UD)^{n/2} D^{n/2}$$ if $$n$$ is even.

Let $$w = 0^{n_1} 1 0^{n_2} 1 \dots 0^{n_k} 1$$ be any binary word ending with a $$1$$. Then $$\phi(w) = \phi(0^{n_1} 1) \phi(0^{n_2} 1)\dots \phi(0^{n_k} 1)$$.

Finally, to obtain the nice Dyck path, apply the Lalanne-Kreweras involution https://www.findstat.org//Mp00120.

• I don't know what to make of all these answers by FindStat, but I think the correct link for this answer is findstat.org/MapsDatabase/Mp00120 – David White Jul 19 '20 at 18:16
• @DavidWhite Thank you for noticing it! The initial link did not work, I changed it and checked, but now my version does not work either, don't know why. – მამუკა ჯიბლაძე Jul 19 '20 at 19:28
• Seems to work now – მამუკა ჯიბლაძე Jul 19 '20 at 19:36
• @DavidWhite there should be a redirect, for me both versions work. I use the shorter version, because it is shorter. Concerning "FindStat answers": I like to post answers under this name if my scripts find the answer essentially automatically. – Martin Rubey Jul 19 '20 at 19:58
• @MartinRubey, I think the issue is that the other user edited to change your // to / in the URL. Also, I didn't mean to be accusatory about the FindStat user, but at first glance I thought it odd to see so many links to the same domain. Instead of flagging as spam, I followed one and learned about your project, which seemed legit. I leave it to the experts to decide if it answers the present question. – David White Jul 19 '20 at 20:06