13
$\begingroup$

A sequence $[c_0,c_1,...,c_{n-1}]$ with $n \geq 2$ is called a Dyck path in case $c_{n-1}=1$, $c_i \geq 2$ for $i \neq n-1$ and $c_i-1 \leq c_{i+1}$ for each $i$. For example the Dyck paths for $n=4$ are the 5 sequences [ 2, 2, 2, 1 ], [ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ], [ 4, 3, 2, 1 ]. In general they are enumerated by the Catalan sequence. Note that those sequences are just the area sequence in the classical definition of Dyck paths, see https://arxiv.org/pdf/1811.05846.pdf page 6. One also has the coarea sequence associated to a Dyck path $[d_0,d_1,...,d_{n-1}]$ which can be formally defined via $d_0=1, d_1=2$ and $d_i = \min \{k \geq 2 | k \geq c_{i-k} \}$ for $i \geq 1$.

A module of a Dyck path $[c_0,c_1,...,c_{n-1}]$ is a tuple $(i,m)$ with $0 \leq i \leq n-1$ and $1 \leq m \leq c_i$.

We call a Dyck path $[c_0,c_1,...,c_{n-1}]$ shod in case the following is satisfied: For each tuple $(i,m)$ with $1 \leq m \leq c_i -1$ and $m < c_{i-1}$ we have (($c_i-m=c_{i+m}$) or ($d_{i-1}=d_{i+m-1}-m$)).

This condition looks complicated but has a nice pictorial interpretation in a Dyck path.

Question 1: Is there a nice combinatorial description of shod Dyck paths?

Question 2: Is it true that the number of shod Dyck paths is equal to $\frac{(n-2)^3+2(n-2)}{3}+1$, which is also equal to the number of permutations of length n which avoid the patterns 321, 2143, 3124 , see https://oeis.org/A116731 . This is true for $n \leq 9$. So the sequence starts with 1,2,5,12,25,46,77,120....

Question 2' (equivalent to Question 2): Call a shod Dyck path special in case it additionally satisfies that there exists an $i \neq n-1$ such that $c_{i+1}>c_i-1$ and $c_{i+c_i}>c_{i+1}-c_i+1$. Then the number of special shod Dyck paths $[c_0,c_1,...,c_{n+2}]$ seems to be given by the Square pyramidal numbers $\sum\limits_{k=0}^{n}{k^2}$, see https://oeis.org/A000330. It counts for example the Number of permutations avoiding 13-2 that contain the pattern 32-1 exactly once.Is this true?

Background: A finite dimensional algebra is called shod, in case each indecomposable module has projective dimension at most one or injective dimension at most one. Recently in https://www.sciencedirect.com/science/article/pii/S0001870815300219 such algebras are characterised as endomorphism algebras of 2-term silting complexes in derived categories of Ext-finite hereditary abelian categories. Dyck paths correspond to Nakayama algebras with a linear quiver (which are also exactly the admissible quotient algebras of the algebra of upper triangular matrices) and the elementary question asks for a combinatorial classification of Nakayama algebras that are shod. Note also that Dyck paths are in bijection with permutations of length n which avoid the pattern 321 and maybe viewing Dyck paths as such pattern avoiding permutations might be better for this question. But there are various bijections from Dyck paths to 321 avoiding permutations and it is not clear what is the "best" one for such questions.

edit: Here is another approach to question 2 leading to a possibly much nicer enumeration result, namely the sum of all squares: Call a shod Dyck path special in case it additionally satisfies that there exists an $i \neq n-1$ such that $c_{i+1}>c_i-1$ and $c_{i+c_i}>c_{i+1}-c_i+1$. Then the number of special shod Dyck paths $[c_0,c_1,...,c_{n-1}]$ seems to be given by the Square pyramidal numbers $\sum\limits_{k=0}^{n-3}{k^2}$: https://oeis.org/A000330 , which is a much more well known sequence. They enumerate for example according to oeis "Number of rhombi in an n X n rhombus" and "Number of permutations avoiding 13-2 that contain the pattern 32-1 exactly once". I can classifly the shod non-special Dyck paths, so it would be enough to solve question 1 and 2 for special shod Dyck paths.

For $n=4$ the unique special shod Dyck path is [2,2,2,1], for $n=5$ we have [ [ 3, 2, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ] ] and for $n=6$ we got [ [ 4, 3, 2, 2, 2, 1 ], [ 4, 3, 3, 2, 2, 1 ], [ 4, 4, 3, 2, 2, 1 ], [ 3, 2, 2, 3, 2, 1 ], [ 3, 3, 2, 3, 2, 1 ], [ 3, 2, 3, 3, 2, 1 ], [ 4, 3, 3, 3, 2, 1 ], [ 4, 4, 3, 3, 2, 1 ], [ 2, 2, 4, 3, 2, 1 ], [ 2, 3, 4, 3, 2, 1 ], [ 3, 3, 4, 3, 2, 1 ], [ 2, 4, 4, 3, 2, 1 ], [ 3, 4, 4, 3, 2, 1 ], [ 4, 4, 4, 3, 2, 1 ] ].

$\endgroup$
  • $\begingroup$ In the definition of coareas sequence, are $c$ with negatove indices assumed to be zeroes? $\endgroup$ – Ilya Bogdanov Oct 12 at 23:32
  • $\begingroup$ @IlyaBogdanov We set $c_i = c_j$ in case $i=j$ mod $n$. But other than $c_{-1}=1$ this can not occur or? $\endgroup$ – Mare Oct 12 at 23:53
  • 1
    $\begingroup$ Have you tried any of the standard bijections from Dyck paths to 321 avoiding permutations to see if the image of a shod Dyck path avoids the permutations 2143 and 3124 as well? $\endgroup$ – Zachary Hamaker Oct 14 at 20:35
  • $\begingroup$ @ZacharyHamaker I have this problem for a long time now and tried that for some bijections without success. But also my programming skills are very limited to do a much higher number of tests (like composing such bijections with other famous selfbijections of Dyck paths or 321- avoiding permutations). $\endgroup$ – Mare Oct 14 at 20:54
  • 1
    $\begingroup$ @ZacharyHamaker I tired some standard bijections (= already implemented bijections) I found consistency with pattern avoidance (for other patterns). I posted an answer with specific conjectures. $\endgroup$ – John Machacek Oct 19 at 3:24
3
+50
$\begingroup$

Here are some conjectures each of which would answer the question. There are lots of ways to map Dyck paths to permutations as well as many Wilf equivalent pattern avoidance classes. Hence, these conjectures may not be the "right" way or the "best" way to go. But I did some computations and these conjectures fit with bijections already implemented in SageMath (see the documentation on Dyck Words).

Conjecture A: Applying to_132_avoiding_permutation() takes shod Dyck paths to $Av(132, 4321, 4213)$.

Conjecture B: Applying to_312_avoiding_permutation() takes shod Dyck paths to $Av(312, 1234, 1324)$.

Conjecture C: Applying to_321_avoiding_permutation() takes shod Dyck paths to $Av(321, 2134, 2143)$.

Here $Av(\pi_1, \dots, \pi_k)$ denotes all permutations which avoid each of the patterns $\{\pi_1, \dots, \pi_k\}$. I came to these conjectures by looking at the two non-shod Dyck paths which map to permutations of length $4$. Provided my code is correct, each conjecture is checked for permutations up to (and including) length $12$.

I should also note the numbers come out to suggest Wilf equivalence between all these, but I don't know whether or not that is known. I'm not sure of the status of the literature on avoiding one pattern of length $3$ and two patterns of length $4$. (Edit: The Wilf equivalence classes for one pattern of length $3$ and two patterns of length $4$ are known from Systematic Studies in Pattern Avoidance . Hence, it is known the sets in Conjecture A, B, and C have the same number of permutations of each length. However, it would still be nice to understand them bijectively of see the connection to shod Dyck paths.)

$\endgroup$
  • $\begingroup$ That is very interesting, thank you very much! $\endgroup$ – Mare Oct 19 at 9:59
1
$\begingroup$

(too long for a comment and too ugly for an edit) Here are the special shod Dyck paths in a form readable in SAGE for $n=4,5,6,7,8$. You can go to http://www.findstat.org/StatisticFinder/DyckPaths (and use "all-at-once") and then enter the values and search to get a picture of all those Dyck paths when you click on them. The statistic suggests that all special shod Dyck paths have exactly 3 peaks.
As there seems to be $1^2+2^2+3^2+4^2+....+(n-3)^2$ many such shod Dyck paths for a given $n$, there should be a nice general pattern but I can not see it at the moment. (you can go to the edit of this answer and copy the following, I do not know how to make MO display it correctly)

[1, 0, 1, 0, 1, 0] => 3
[1, 1, 0, 0, 1, 0, 1, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 0, 1, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0] => 3
[1, 1, 0, 1, 0, 0, 1, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0] => 3
[1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0] => 3
[1, 0, 1, 0, 1, 1, 0, 0] => 3
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0] => 3
[1, 1, 0, 1, 0, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0] => 3
[1, 0, 1, 1, 0, 1, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0] => 3
[1, 1, 0, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0] => 3
[1, 0, 1, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0] => 3
[1, 0, 1, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 0, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0] => 3
[1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0] => 3
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] => 3
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0] => 3
[1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0] => 3
$\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.