Double Deficiencies of Dyck Paths via the Billey-Jockusch-Stanley Bijection

Martin Rubey Fakultät für Mathematik und Geoinformation Technische Universität Wien Wiedner Hauptstr. 8-10 1040 Wien Austria

               martin.rubey@tuwien.ac.at

Christian Stump Institut für Mathematik Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Germany

                stump@math.tu-berlin.de

Abstract

We prove a recent conjecture by Marczinzik involving certain statistics on Dyck paths that originate in the representation theory of Nakayama algebras of a linearly oriented quiver. We do so by analyzing the effect of the Billey-Jockusch-Stanley bijection between Dyck paths and 321-avoiding permutations on these statistics, which was suggested by the result of a query issued to the online database FindStat.

1 Introduction

This paper serves two purposes. The first is to demonstrate the power of the online database FindStat [4] to help with explaining and recognizing combinatorial parameters (also known as ‘combinatorial statistics’) which occur in perhaps surprising locations.

The second purpose, achieving the first, is to prove a refinement of the combinatorial part of the following conjecture of Marczinzik [3]:

Conjecture. The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths (sequence \underline{A001006} in the OEIS [5]) of length n.

Moreover, the number of such algebras having the double centralizer property with respect to a minimal faithful projective-injective module equals the number of Riordan paths (sequence \underline{A005043} in the OEIS [5]), that is, Motzkin paths without level-steps at height zero, of length n.

Let us stress that we do not attempt to explain the algebraic significance of this conjecture. Instead, we refer to the book [6] for the definitions of a Nakayama algebra, quiver of an algebra and the double centralizer property. Indeed, the part of reducing the algebraic statement to a problem in enumerative combinatorics, reproduced as Conjecture 1 below, is Marczinzik’s achievement.

2 Combinatorial background

Consider a square array with columns labelled 1 through n from left to right and rows labelled 1 through n from bottom to top. A Dyck path of semilength n is a lattice path with north and east steps running along the edges of the array, starting at the lower left corner, ending at the upper right corner, and never going below the diagonal y = x. We refer to Figure 2 for an illustration of our conventions. Since all of the notions defined below depend on a Dyck path, we do not indicate the Dyck path in the notation to avoid clutter.

In the following we use two variants of the area sequence associated with a Dyck path: the row-area sequence (r_{0}, r_{1}, …, r_{n}) is obtained by setting r_{0} = −1 and r_{k}, for 1 ≤ k ≤ n, to the number of full squares in the row of the k-th north step between the path and the main diagonal. For example, the row-area sequence of the Dyck path in Figure 2 is

(−1, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 7, 8, 4, 4, 3, 2, 2).

Similarly, the column-area sequence (c_{1}, …, c_{n+1}) is obtained by setting c_{k}, for 1 ≤ k ≤ n, to the number of full squares in the column of the k-th east step between the path and the main diagonal. Additionally, we set c_{n+1} = −1. In the example in Figure 2, the column-area sequence is

(1, 3, 2, 8, 7, 6, 5, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0, −1).

The additional −1 at the beginning of the row- and at the end of the column-area sequence can be interpreted as prepending a north step and appending an east step to the Dyck path, without shifting the main diagonal. It turns out that several properties below are easier to describe with this convention.

Finally, a valley of a Dyck path is an east step directly followed by a north step. In terms of the array, it is the cell enclosed by the two steps. Explicitly, if the east step of the valley is the k-th east step of the path, and the north step is the ℓ-th north step of the path, the position of the valley is (k, ℓ).

3 Marczinzik’s conjecture and its refinement

The following notions on Dyck paths are due to Marczinzik and originate in the representation theory of Nakayama algebras of a linearly oriented quiver on n vertices. We refer to the MathOverflow discussion [3] for further background. For a Dyck path D with row-area sequence (r_{0}, r_{1}, …, r_{n}) and column-area sequence (c_{1}, …, c_{n+1}),

• D is the set of indices k with c_{k+1} = c_{k} − 1,

• F, is the set of indices k with r_{k+1+c_{k+1}} = r_{k−1} + c_{k+1} + 2, and

• N be the set of rows which do not contain a valley.

We can now state Marczinzik’s conjecture. Recall that a Motzkin path of length n is a lattice path from (0, 0) to (n, 0) consisting of up-steps (1, 1), down-steps (1, −1) and levelsteps (1, 0) that never goes below the x-axis.

Conjecture 1 (Marczinzik [3]). The number of Dyck paths such that N ∩ D is contained in F equals the number of Motzkin paths of length n.

Moreover, the number of Dyck paths such that N ∩ D is empty equals the number of Riordan paths of length n, that is, Motzkin paths without level-steps at height zero.

The case n = 3 is illustrated in Figure 1.

Upon seeing this conjecture, our immediate reaction was to transform the condition into a ‘combinatorial statistic’ on Dyck paths, and query the online database FindStat. Indeed, this approach was doubly successful: first, the result of the database query, reproduced in the conjecture below, is a substantial common refinement of both parts of Conjecture 1, and makes a proof strategy suggest itself. Second, the references linked in the result provide already all the tools we need.

Conjecture 2. For a Dyck path D, an index k is in F but not in N ∩ D if and only if it is a double deficiency (see www.findstat.org/St000732) in the 321-avoiding permutation associated with D using the Billey-Jockusch-Stanley bijection (see www.findstat.org/Mp00129).

This conjecture is verified in the following section. In the final section, we use Elizalde’s description [2] of the Foata-Zeilberger bijection between 321-avoiding permutations and bicolored Motzkin paths to deduce Conjecture 1.

1 1 2 2 3 3  1 1 2 2 3 3  1 1 2 2 3 3  1 1 2 2 3 3  1 1 2 2 3 3
r_{0}, r_{1}, r_{2} (−1, 0, 1, 2) (−1, 0, 1, 1) (−1, 0, 1, 0) (−1, 0, 0, 1) (−1, 0, 0, 0)
c_{1}, c_{2}, c_{3} (2, 1, 0, −1) (1, 1, 0, −1) (1, 0, 0, −1) (0, 1, 0, −1) (0, 0, 0, −1)
N {1, 2, 3}  {1, 2}  {1, 2}  {1, 3}  {1}
D {1, 2, 3}  {2, 3}  {1, 3}  {2, 3}  {3}
F {1, 2, 3}  ∅  {1}  {3}  ∅
Motzkin path  -

Figure 1: The case n = 3.

4 Dyck paths and 321-avoiding permutations

The Billey-Jockusch-Stanley bijection [1], sending a Dyck path D of semilength n to a 321avoiding permutation π of the numbers {1, …, n}, goes as follows: first, put crosses into the cells corresponding to the valleys of D. Then, working from the left to the right, for each column not yet containing a cross we put a cross into the lowest cell whose row does not yet contain a cross. This yields the permutation matrix of the permutation π.

An example is given in Figure 2, where the displayed Dyck path of semilength 17 is sent to the permutation

[ 3, 1, 6, 2, 4, 5, 7, 13, 14, 8, 15, 9, 16, 17, 10, 11, 12 ]

on {1, …, 17}, in one-line notation.

For a permutation π of {1, …, n} and an index 1 ≤ k ≤ n, we say that k is

• an exceedance if π(k) > k,

• a fixpoint if π(k) = k,

• a deficiency if π(k) < k, and

• a double deficiency if π(k) < k < π^{−1}(k).

Let us first record two general properties of the bijection.

\begin{matrix}1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \\ 11 \\ 11 \\ 12 \\ 12 \\ 13 \\ 13 \\ 14 \\ 14 \\ 15 \\ 15 \\ 16 \\ 16 \\ 17 \\ 17 \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ r_{k−1} + 1 \\ r_{k+1+c_{k+1}} \\ c_{k+1} + 1 \end{matrix}

Figure 2: A detailed example.

Lemma 3. The crosses in the valleys of D are exceedances of π, whereas all others are fixpoints or deficiencies of π.

Proof. The first statement is true because Dyck paths stay above the main diagonal. To see the second statement, note that to the left of column k there are only k − 1 crosses, so at least one of the bottom k rows cannot contain a cross to the left of column k.

Lemma 4. An index k is a fixpoint of π if and only if D does not have a valley in any position (i, j) with i ≤ k and j ≥ k.

Proof. Let k be a fixpoint of π. The construction of π implies that column k does not contain a valley of D. Moreover, for every ℓ < k there is an ℓ′ < k with π(ℓ′) = ℓ. In other words π restricts to a permutation of {1, …, k − 1}, implying that D does not have a valley in position (i, j) for i ≤ k and j ≥ k. As both implications in the argument are equivalences, the statement follows.

Conjecture 2 is now an immediate consequence of the following three statements.

Lemma 5. An index k is in D if and only if it is a fixpoint or a deficiency of π.

Proof. By definition, k is in D if and only if there is no valley in column k. Thus the claim is the statement of Lemma 3.

Lemma 6. An index k is in F if and only if it is a fixpoint of π.

Proof. Let us first remark that an index k in F is an index for which D does not have a valley between the (k − 1)-st north step and the (k + 1)-st east step.

This is best understood by looking at an example: in Figure 2 the index k = 7 is in F because

r_{6} + c_{8} + 2 = 2 + 4 + 2 = 8 = r_{12} = r_{8+c_{8}}.

On the other hand, k = 15 is not in F, since

r_{14} + c_{16} + 2 = 5 + 2 + 2 = 9 ≠ 2 = r_{17} = r_{16+c_{16}}.

Suppose now that k is a fixpoint of π. Then k + 1 + c_{k+1} is the index of the row just below the (k + 1)-st east step. The number of full squares in this row between the Dyck path and strictly to the left of column k is, by Lemma 4, precisely r_{k} = r_{k−1} + 1. Moreover, the number of remaining full squares in this row, towards the main diagonal, is precisely c_{k} = c_{k+1} + 1. Observe that in this case, we are just rewriting the equality in the definition of F as r_{k+c_{k}} = r_{k} + c_{k}.

On the other hand, if the cross in column k is not a fixpoint, there must be a valley to the left and above (k, k), which entails that the number of full squares in row k + 1 + c_{k+1} will be strictly smaller than r_{k+1} + c_{k−1} + 2. Observe that in this case, it is not in general possible to rewrite the equality in the definition of F as above. For example, this is the case with the index k = 6 in Figure 2.

Lemma 7. An index k is in N if and only if π^{−1}(k) is a fixpoint or a deficiency of π.

Proof. By definition, k ∈ N if and only if row k does not contain a valley of D. This is the same as saying that the cross in row k is not to the left of the main diagonal, in symbols, π^{−1}(k) ≥ k.

Proof of Conjecture 2. This is a direct consequence of Lemmas 5, 6, and 7.

5 321-avoiding permutations and Motzkin paths

Recall that a bicolored Motzkin path is a Motzkin path where level-steps not at height zero come in two colors, say blue and red. To prove Conjecture 1, we follow Elizalde’s description [2] of the Foata-Zeilberger bijection restricted to 321-avoiding permutations and bicolored Motzkin paths: from each cross in the array draw a horizontal and a vertical line to the diagonal. Then, looking at these lines as emanating from the diagonal, there are five possibilities, which are translated into up, down, level-steps at height zero, blue level-steps and red level-steps of the Motzkin path as follows:

×

We can now deduce Conjecture 1 from Conjecture 2:

Proof of Conjecture 1. Let D be a Dyck path, π the corresponding permutation and M the corresponding bicoloured Motzkin path.

The construction of the Motzkin path is such that double deficiencies of π correspond to red level-steps of M. Bicoloured Motzkin paths without any red level-steps are simply Motzkin path. Together with Conjecture 2 this implies the first part of Conjecture 1.

By Lemma 6, F is precisely the set of fixpoints of π, by Lemma 5 F is contained in D, and by Lemma 7 F is contained in N. Therefore, the statement that N does not contain D is equivalent to the statement that π does neither have double deficiencies nor fixpoints. The second part of the conjecture thus follows from the first, together with the observation that level-steps at height zero correspond to fixpoints of π.

6 Acknowledgments

The authors would like to thank the referee for suggesting to include a reference to [6]. M. Rubey was supported by the the Austrian Science Fund (FWF): P 29275. C. Stump was supported by the DFG grants “Coxeter-Catalan combinatorics” and “Noncrossing phenomena in Algebra and Geometry”.

\begin{matrix}1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \\ 11 \\ 11 \\ 12 \\ 12 \\ 13 \\ 13 \\ 14 \\ 14 \\ 15 \\ 15 \\ 16 \\ 16 \\ 17 \\ 17 \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \end{matrix}

Figure 3: The associated bicolored Motzkin path.

References

[1] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubert polynomials. J. Algebraic Combin. 2 (1993), 345–374.

[2] S. Elizalde. Continued fractions for permutation statistics, preprint, 2017,

   https://arxiv.org/abs/1703.08742v2.

[3] R. Marczinzik. Combinatorics problem related to Motzkin numbers, MathOverflow.

   Available at https://mathoverflow.net/q/278284.

[4] M. Rubey, C. Stump, et al. FindStat — The combinatorial statistics database,

   http://www.FindStat.org.

[5] N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences. Available at

   http://oeis.org.

[6] A. Skowroński and K. Yamagata. Frobenius Algebras. I. EMS Textbooks in Mathematics. European Mathematical Society (EMS), 2011.

2010 Mathematics Subject Classification: Primary 05A19. Keywords: bijective combinatorics, combinatorial statistic, Dyck path, Motzkin path, Riordan path, pattern-avoiding permutation.

(Concerned with sequences \underline{A001006} and \underline{A005043}.)

Received August 17 2017; revised versions received October 19 2017; October 22 2017. Published in Journal of Integer Sequences, October 27 2017.

Return to Journal of Integer Sequences home page.