TransWikia.com

An enumeration problem for Dyck paths from homological algebra

MathOverflow Asked on November 3, 2021

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.

One Answer

This is a conjectural answer.

Let $w = 0dots01$ 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.

Answered by FindStat on November 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP