Séminaire Lotharingien de Combinatoire 79 (2018), Article B79b

A NOTE ON: RECTANGULAR SCHRÖDER PARKING FUNCTIONS COMBINATORICS

JEAN-CHRISTOPHE AVAL AND FRANÇOIS BERGERON

Abstract. We study Schröder paths drawn in an (m, n) rectangle, for any positive integers m and n. We get explicit enumeration formulas, closely linked to those for the corresponding (m, n)-Dyck paths. Moreover, we study a Schröder version of (m, n)-parking functions, and associated (q, t)-analogs.

Contents

1. Introduction

2. Schröder path enumeration  2
3. Constant term formula  10
4. Schröder parking functions  11
References  13

1. Introduction

Many objects are enumerated by Schröder numbers:

1, 2, 6, 22, 90, 394, 1806, … (sequence A006318 in [13]),

but the most classical are probably paths from (0, 0) to (n, n) with steps either (1, 0), (0, 1), or (1, 1), never going below the diagonal (although they may touch it). These are generalizations of Dyck paths (for which only the first two types of steps are allowed), well-known to be enumerated by the Catalan numbers. The aim of this work is to investigate properties of an analogous notion for the m × n-rectangle, rather than for the n × n-square, the latter corresponding to the classical case. Our (m, n)-Schröder paths (defined in Section 2) have the same kind of steps, but we change the endpoint to (m, n), and use the diagonal of the rectangle to crop the set of allowed paths. Partial results are already known, in the case where m and n are coprime, in particular when m = rn+1 (see [14]). We first obtain (see Corollary 2) a symmetric function enumeration formula for the general case (no coprimality condition). This result, as well as the methods used to obtain it, closely parallels the case of Dyck paths studied in [2]. Next, we consider the notion of Schröder parking functions, i.e., labeled rectangular Schröder paths, and investigate associated q-analogs and (q, t)-analogs of our enumeration formulas; with the parameter q accounting for the area between the path and the diagonal.

This work was supported by NSERC-Canada.

2. Schröder path enumeration

Schröder paths. Our (m, n)-Schröder paths are sequences

(0, 0) = (x_{0}, y_{0}), (x_{1}, y_{1}), …, (x_{N}, y_{N}) = (m, n)

with (x_{k}, y_{k}) in ℕ × ℕ, and such that • (x_{k+1}, y_{k+1}) = (x_{k}, y_{k})+(s, t), with (s, t) ∈ {(0, 1), (1, 1), (1, 0)},

• such that my_{k} − nx_{k} ≥ 0, for all k.

Depending on (s, t) being equal to (0, 1), (1, 1), or (1, 0) in the first condition, we say that we have an up, diagonal, or right step. The inequality of the second condition ensures that the paths does not go below the diagonal.

Schröder polynomials. Recall that the enumerating polynomials for (n, n)-Schröder paths are given by the formula

S_{n}(y) := ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{n}{k}\binom{2n − k}{n} y^{k},  (1)

with S_{0} = 1. These “Schröder polynomials” have a long and interesting history. The coefficient of y^{k}, denoted by S_{n}^{(k)}, enumerates Schröder paths having k diagonal steps. Hence, the case k = 0 corresponds to the usual notion of Dyck paths, well-known to be counted by the Catalan numbers

S_{n}^{(0)} = \frac{1}{n + 1}\binom{2n}{n}.

Small values of these polynomials are

S_{1}(y) = 1 + y,
S_{2}(y) = 2 + 3 y + y^{2},
S_{3}(y) = 5 + 10 y + 6 y^{2} + y^{3},
S_{4}(y) = 14 + 35 y + 30 y^{2} + 10 y^{3} + y^{4},
S_{5}(y) = 42 + 126 y + 140 y^{2} + 70 y^{3} + 15 y^{4} + y^{5}.

366434210 \underline{Row areas} 012345678 \underline{Row labels}
Figure 1. The (12, 9)-Schröder path 000\overline{0}22\overline{2}\overline{3}7.

We consider here an (m, n)-rectangular analog of these polynomials, for any pair (m, n) of positive integers. Just as for Dyck paths, the case when m and n are coprime is somewhat simpler. To make this more apparent notation-wise, we often write our pairs of integers in the form (m, n) = (ac, bc), with (a, b) coprime. Hence c is the greatest common divisor of m and n. In particular, the (a, b)-case corresponds to the coprime situation. We recall that the number of (a, b)-Dyck paths is simply given by the formula

C_{a,b} = \frac{1}{a + b}\binom{a + b}{a}.

The general case of (m, n)-Dyck path enumeration, C_{m,n} giving the number of such paths, is probably best presented in generating series format as

∑_{d≥0} C_{ad,bd}z^{d} = exp(∑_{j>1} \frac{1}{a}\binom{ja + jb}{ja} \frac{z^{j}}{j} ).  (2)

The proof of this formula, going back to 1954, is due to Bizley [7], who attributes it to Grossman [10].

Sequence encoding. It will be practical to encode our paths as sequences α = a_{0}a_{1} ⋯ a_{n−1} of barred or unbarred integers, with one a_{i} for each up or diagonal step of the path, reading them from top to bottom. For up steps we set a_{i} = k, whereas diagonal steps are encoded a_{i} = \overline{k} (barred steps). In both cases, k is equal to to the number of entire “cells” that lie to the left of the unique up (or diagonal) step at height n − i. The a_{i} are the parts of α. In this encoding, α = a_{0}a_{1} ⋯ a_{n−1} corresponds to an (m, n)-Schröder path if and only if

(1) a_{0} ≤ a_{1} ≤ … ≤ a_{n−1}, (with the order 0 < \overline{0} < ⋯ < k < \overline{k}),

(2) if a_{i} = \overline{k}, then necessarily a_{i} < a_{i+1}, and

(3) for each i, we have a_{i} ≤ \overline{⌊i m/n⌋}. Each unbarred k, between 0 and m, occurs with some multiplicity^{1} n_{k} in a path α. Removing 0-multiplicities, we obtain the (multiplicity) composition γ(α) of the sequence α, reading these multiplicities in increasing values of k. For example,

γ(0\overline{0}11\overline{1}244\overline{4}) = (1, 2, 1, 2).

Clearly γ(α) is a composition of n − k, where k stands for the number of diagonal steps in α. The parts of γ(α) may be understood as the lengths of risers (also called vertical runs) in the path. These are maximal sequences of consecutive up-steps. Any (m, n)-Schröder path may be obtained by either barring or not the rightmost part of a given size in the analogous word encoding of an (m, n)-Dyck path. As we will see this makes the enumeration of Schröder paths easy, once we set up the right tools.

Symmetric function weight. As we will come to see later, it is interesting to consider a weighted enumeration of Schröder paths, with the weight lying in the graded ring

Λ = ⨁_{d≥0} Λ_{d}

of symmetric “functions” (polynomials in a countable set of variables x = x_{1}, x_{2}, x_{3}, …). Recall that the degree d homogeneous component Λ_{d} affords as a linear basis the set

{e_{μ}(x) | μ ⊢ d}

of elementary symmetric functions, with

e_{μ}(x) := e_{μ_{1}}(x)e_{μ_{2}}(x) ⋯ e_{μ_{ℓ}}(x),

for μ = μ_{1}μ_{2} … μ_{ℓ} running over the set of partitions of d. In turn, each factor e_{k}(x) is characterized by the generating function identity

∑_{k≥0} e_{k}(x)z^{k} = ∏_{i≥1}(1 + x_{i} z).

1possibly equal to 0.

with e_{0}(x) := 1. It easily follows that

e_{k}(x + y) = e_{k}(x) + e_{k−1}(x) y,  (3)

where x + y means that we add a new variable y to those occurring in x. With these notions at hand, we now simply set

S_{m,n}(x; y) := ∑_{α} α(x) y^{diag(α)}, with α(x) := ∏_{k∈γ(α)} e_{k}(x), (4)

where the sum is over the set of (m, n)-Schröder paths α, with diag(α) denoting the number of diagonal steps in α. Likewise, we denote by

S_{m,n}^{(k)}(x) := ∑_{diag(α)=k} α(x),

the symmetric function enumerator of (m, n)-Schröder paths with exactly k diagonal steps, so that S_{m,n}(x; y) = ∑_{k} S_{m,n}^{(k)}(x) y^{k}. For example, we have

S_{1,1}(x; y) = e_{1}(x) + y,
S_{2,2}(x; y) = (e_{11}(x) + e_{2}(x)) + 3 e_{1}(x) y + y^{2},
S_{3,3}(x; y) = (e_{111}(x) + 3 e_{21}(x) + e_{3}(x))
+(6 e_{11}(x) + 4 e_{2}(x))y + 6 e_{1}(x)y^{2} + y^{3}.

Observe that, for all r and n, we have

S_{rn+1,n}(x; y) = S_{rn,n}(x; y),  (5)

since the last step of (rn+1, n) must necessarily be a right step, and the coprimality of rn + 1 and n implies that staying above the (rn + 1, n)- diagonal insures as well that we stay above the (rn, n)-diagonal. Hence we get the same set of paths. To make some expressions more compact, we shall use “plethystic notation”, recalling that we have

e_{n}[m x] := ∑_{ν⊢n}(−1)^{n−ℓ(ν)} m^{ℓ(ν)} \frac{p_{ν}(x)}{z_{ν}},  (6)

with m considered as a “constant” in the calculation of plethysm. This means that p[mx] = m p[x]. Recall that it is usual, for any partition ν of n, to denote its length by ℓ(ν), and to use the notation

z_{ν} := 1^{d_{1}}d_{1}!2^{d_{2}}d_{2}! … n^{d_{n}}d_{n}!,

where d_{i} is the number of copies of the part i in ν.

Main results. Recall from [2] that we have a Bizley-like formula for the symmetric function enumeration

C_{m,n}(x) := ∑_{diag(α)=0} α(x)

of (m, n)-Dyck paths, namely

∑_{d≥0} C_{ad,bd}(x) z^{d} = exp(∑_{j≥1} e_{jb}[ja x] \frac{z^{j}}{aj} ),  (7)

with a and j considered as constants in the plethysm. We can exploit this formula to get one for our weighted enumeration of Schröder paths. Indeed,

Proposition 1. For all m and n, we have

S_{m,n}(x; y) = C_{m,n}(x + y).  (8)

Proof. Let us fix the dimensions m, n of the rectangular box. Recall that, for any given k ≥ 0, S_{m,n}^{(k)} stands for the set of (m, n)-Schröder paths with exactly k diagonal steps. We denote by C_{m,n} the set S_{m,n}^{(0)} of (m, n)-Dyck paths. For β ∈ C_{m,n}, let us denote by γ(β) = (γ_{1}, …, γ_{j}) the composition giving the lengths of the vertical runs of β. In view of (4) and (3), we may write

C_{m,n}[x + y] = ∑_{β∈C_{m,n}} ∏_{γ_{i}∈γ(β)} e_{γ_{i}}[x + y]

= ∑_{β∈C_{m,n}} ∏_{γ_{i}∈γ(β)}(e_{γ_{i}}[x] + y e_{γ_{i}−1}[x])

= ∑_{β∈C_{m,n}} ∑_{k≥0} y^{k} ∑_{δ} e_{δ}[y],  (9)

where the last sum is over all possible compositions δ obtained by reducing exactly k of the parts of γ(β) by 1. Let us now consider the projection

π : S_{m,n}^{(k)} ⟶ C_{m,n}

which replaces any diagonal step by a North step followed by an East step, i.e., an (outer) corner. For a Dyck path β, let us denote by S_{m,n}^{(k)}(β) := π^{−1}(β) the inverse image of β under π. It is clear that the sets S_{m,n}^{(k)}(β), for β running over C_{m,n}, are the blocks of a partition of S_{m,n}^{(k)}. We may thus rewrite the inner sum in (9) as

∑_{δ} e_{δ}[y] = ∑_{α∈S_{m,n}^{(k)}(β)} e_{γ(α)}[x],

and get

C_{m,n}[x + y] = ∑_{β∈C_{m,n}} ∑_{k≥0} y^{k} ∑_{α∈S_{m,n}^{(k)}(β)} e_{γ(α)}[x]

= ∑_{k≥0} y^{k} ∑_{α∈S_{m,n}^{(k)}} e_{γ(α)}[x] = S_{m,n}(x; y)

as announced. □

From Equation (7), we may derive the following reformulation of Proposition 1.

Corollary 2. The generating function of rectangular Schröder polynomials is

∑_{d≥0} S_{ad,bd}(x) z^{d} = exp(∑_{j≥1} e_{jb}[ja (x + y)] \frac{z^{j}}{aj} ).  (10)

For example, for any a and b coprime, we get

S_{a,b}(x + y) = \frac{1}{a}e_{b}[a (x + y)],
S_{2a,2b}(x + y) = \frac{1}{2a}e_{2b}[2a (x + y)] + \frac{1}{2a^{2}} e_{b}[a (x + y)]^{2},
S_{3a,3b}(x + y) = \frac{1}{3a}e_{3b}[3a (x + y)] + \frac{1}{2a^{2}} e_{b}[a (x + y)] e_{2b}[2a (x + y)]

+ \frac{1}{6a^{3}} e_{b}[a (x + y)]^{3}.

Recall the following well-known expansion^{2} of (6) in terms of elementary symmetric functions:

e_{n}[m x] = ∑_{ν⊢n} \binom{m}{ℓ(ν)}\binom{ℓ(ν)}{d_{ν}}e_{ν}(x),

where \binom{ℓ(ν)}{d_{ν}} stands for the multinomial coefficient

\binom{ℓ(ν)}{d_{ν}} := \binom{ℓ(ν)}{d_{1}, d_{2}, …, d_{n}},

2This is essentially an instance of the dual Cauchy formula.

with each d_{i} equal to the multiplicity of the part i in ν. Using this formula, we get

S_{a,b}(x; y) = \frac{1}{a}e_{b}[a (x + y)]

= \frac{1}{a} ∑_{k=0}^{b} e_{b−k}[a x] e_{k}[a y]

= \frac{1}{a} ∑_{k=0}^{b} \binom{a}{k} e_{b−k}[a x] y^{k}

= \frac{1}{a} ∑_{k} y^{k} ∑_{ν⊢b−k} \binom{a}{k}\binom{a}{ℓ(ν)} \binom{ℓ(ν)}{d_{ν}}e_{ν}(x).  (11)

Moreover, we may write the coefficient of y^{k} in (11) as the following integer coefficient linear combination of the e_{ν}(x):

S_{a,b}^{(k)}(x) = ∑_{ν⊢b−k} \frac{1}{a}\binom{a}{k}\binom{a}{ℓ(ν)} \binom{ℓ(ν)}{d_{ν}}e_{ν}(x).

Since ⟨e_{μ}(x), ∑_{j≥0} e_{j}(x)⟩ = 1 for all partition μ, we immediately get

S_{a,b}^{(k)} = ⟨S_{a,b}^{(k)}(x), ∑_{j≥0} e_{j}(x)⟩,

where ⟨−, −⟩ stands for the usual scalar product on symmetric function^{3}. Otherwise stated, for a and b coprime,

S_{a,b}^{(k)} = ∑_{ν⊢b−k} \frac{1}{a}\binom{a}{k}\binom{a}{ℓ(ν)} \binom{ℓ(ν)}{d_{ν}}.

In particular, in view of (5), this covers the classical case (m = n) as well as the generalized version (m = rn) of [14]. One also deduces from Proposition 1 the following generalization of a result of Haglund [9].

Proposition 3. For all m and n, we have

S_{m,n}^{(k)} = ⟨C_{m,n}(x), e_{n−k}(x)h_{k}(x)⟩.

Proof. We start by recalling the symmetric function identity

f(x + y) = ∑_{k≥0} y^{k} h_{k}^{⊥} f(x),  (12)

where h_{k}^{⊥} stands for the dual of the operator of multiplication by h_{k}(x) with respect to the symmetric function scalar product. Equation (12) may be checked by computation for the basis element f = e_{λ} for λ a partition λ = (λ_{1}, …, λ_{t}), by using the classical fact that

3For which ⟨p_{μ}, p_{ν}⟩ = z_{μ} δ_{μ,ν}

h_{k}^{⊥}(e_{λ}) = ∑_{|ρ|=k} ∏_{i=1}^{t} e_{λ_{i}−ρ_{i}},

where the sum is over sequences ρ such that 0 ≤ ρ_{i} ≤ 1. It follows directly from (8) that

∑_{k} S_{m,n}^{(k)} y^{k} = ⟨C_{m,n}(x + y), ∑_{k≥0} e_{k}(x)⟩,

= ⟨ ∑_{k≥0} y^{k} h_{k}^{⊥} C_{m,n}(x), ∑_{j≥0} e_{j}(x)⟩,

= ⟨C_{m,n}(x), ∑_{k≥0} y^{k}h_{k}(x) ∑_{j≥0} e_{j}(x)⟩,

= ∑_{k≥0} ⟨C_{m,n}(x), h_{k}(x)e_{n−k}(x)⟩ y^{k}.

The last equality comes from the fact that C_{m,n}(x) is homogeneous of degree n, hence all terms of the wrong degree vanish in the scalar product. Evidently we get the announced result by comparing powers of y of the same degree in both sides of the identity obtained. □

Area enumerator. The i^{th} row area of a path α in S_{n}^{(r)} is the integer

area_{i}(α) := ⌊i m/n⌋ − |a_{i}|,

where we set |\overline{k}| := k. Summing over all indices i between 1 and n, we get the area of α:

area(α) := ∑_{i=0}^{n−1} area_{i}(α).

This generalizes a notion of area on Schröder paths introduced for the case m = n in [8] (and further studied in [3]) to (m, n)-Schröder paths. Following the presentation of [9], this may also be understood as the number of “upper” triangles lying below the path and above the diagonal line (as illustrated in Figure 1). These triangles are also called area triangles. We have the area q-enumerator symmetric function

S_{m,n}(x; y, q) := ∑_{α} α(x) q^{area(α)}y^{diag(α)}.

Keeping up with our previous notational conventions, we also set

S_{m,n}^{(k)}(q) := ∑_{diag(α)=k} q^{area(α)},

and

C_{m,n}(x; q) := ∑_{diag(α)=0} α(x) q^{area(α)}.

Proposition 4. For all m and n, we have

S_{m,n}(x; y, q) = C_{m,n}(x + y; q),  (13)

and

S_{m,n}^{(k)}(q) = ⟨C_{m,n}(x; q), e_{n−k}(x)h_{k}(x)⟩.  (14)

Proof. This comes easily from the fact that the projection π in the proof of Proposition 1 preserves the area. □

From a result of [11], it follows that C_{rn+1,n}(x; q) = C_{rn,n}(x; q) = ∇^{r}(e_{n})|_{t=1}, where ∇ is a Macdonald “eigenoperator” introduced in [5]. By this, we mean that its eigenfunctions are the (combinatorial) q, t-Macdonald polynomials. Thus, a special instance of (14) may be formulated as

S_{rn,n}^{(k)}(q) = ⟨∇^{r}(e_{n})|_{t=1}, e_{n−k}(x)h_{k}(x)⟩.  (15)

In this way, we get back the case t = 1 of Proposition 1 in [9].

3. Constant term formula

The following constant term formula adds an extra parameter to our story. We conjecture that it corresponds to a (q, t)-enumeration of (m, n)-Schröder parking functions, with t accounting for a “dinv”- statistic, still to be defined.

Conjecture 5. We have

S_{m,n}(x; y, q, t) =

CT_{z_{m},...,z_{0}} (\frac{1}{z_{m,n}} ∏_{i=1}^{m} \frac{z_{i}(1 + y z_{i})}{z_{i} − q z_{i+1}}Ω′(x; z_{i}) ∏_{j=i+1}^{m} \frac{(z_{i} − z_{j})(z_{i} − qt z_{j})}{(z_{i} − qz_{j})(z_{i} − tz_{j})}),

where Ω′(x; z) := ∑_{k≥0} e_{k}(x) z^{k}, and z_{m,n} := ∏_{i=0}^{n−1} z_{⌊im/n⌋}.

We recall that some care must be used in evaluating multivariate constant term expressions. Indeed, the order in which successive constant terms are taken does have an impact on the overall result. This is why, in the above formula, the indices appearing after “CT” specify that this should be done starting with z_{m}, and then going down to z_{0}. For example, we have

S_{2,2}(x; y, q, t) = (s_{2} + (q + t) s_{11})+(q + t + 1) s_{1} y + y^{2},
S_{2,3}(x; y, q, t) = (s_{21} + (q + t) s_{111})+(s_{2} + (q + t + 1)s_{11}) y + s_{1} y^{2},
S_{2,4}(x; y, q, t) = (s_{22} + (q + t) s_{211} + (q^{2} + qt + t^{2}) s_{1111})
+((q + t + 1) s_{21} + (q^{2} + qt + t^{2} + q + t) s_{111}) y
+(s_{2} + (q + t) s_{11}) y^{2}.

We underline that Conjecture 5 is simply the evaluation at x + y of a similar formula conjectured in [12] in relation with (m, n)-parking functions. More precisely, it is conjectured in the mentioned paper, that

Conjecture 6 (Negut). We have

C_{m,n}(x; q, t)

= CT_{z_{m},...,z_{0}} (\frac{1}{z_{m,n}} ∏_{i=1}^{m} \frac{z_{i}}{z_{i} − q z_{i+1}} Ω′(x; z_{i}) ∏_{j=i+1}^{m} \frac{(z_{i} − z_{j})(z_{i} − qt z_{j})}{(z_{i} − qz_{j})(z_{i} − tz_{j})}).

From this identity it is clear that Conjecture 5 follows, using the equality Ω′(x + y; z_{i}) = (1 + y z_{i}) Ω′(x; z_{i}). One may readily show that the specialization at t = 1 of the right-hand side of Conjecture 5 does indeed give back our previous C_{m,n}(x + y; q) = S_{m,n}(x; y, q), since the relevant constant term formula is shown to hold in [6]. This, together with the results and conjectures that appear in [6], opens up many new avenues of exploration. In particular, we may obtain explicit candidates for the (q, t)-enumeration of special families of (m, n)- Schröder paths (say with return conditions to the diagonal), by the simple device of evaluating analogous symmetric function formulas for (m, n)-Dyck paths at x + y. Several questions regarding this are explored in [4].

4. Schröder parking functions

An (m, n)-Schröder parking function is a bijective labeling of the up steps of an (m, n)-Schröder path α by the elements of {1, 2, …, n − diag(α)}. One further imposes the condition that consecutive up steps of same x-coordinate have decreasing labels reading them from top to bottom. The path involved in this description is said to be the shape of the parking function. For α an (m, n)-Schröder path, we denote by ℙ(α) the set of parking functions having shape α. When diag(α) = 0, 1 2 6 7 3 5 4

Figure 2. A Schröder parking function.

we get the “usual” notion of parking functions of shape α (an (m, n)- Dyck path). The (m, n)-Schröder parking functions may be understood as preference functions, with some of the parking places being closed to parking (these correspond to diagonal steps). For f ∈ ℙ(α), we denote the row area for the i^{th} row of the shape of f by area_{i}(f). Figure 2 gives an example of a parking function of shape 000\overline{0}1\overline{1}223. As we did for paths, we consider the (m, n)-Schröder parking function polynomial

P_{m,n}(y, q) = ∑_{k} P_{m,n}^{(k)} y^{k} := ∑_{α} |ℙ(α)| q^{area(α)}y^{diag(α)}.

It is easy to derive the following fact from Corollary 4.

Corollary 7. For all m and n, we have

P_{m,n}(y, q) = ⟨C_{m,n}(x + y; q), \frac{1}{1 − p_{1}(x)}⟩.

Equivalently, for all k, we have

P_{m,n}^{(k)}(q) = ⟨C_{m,n}(x; q), p_{1}(x)^{n−k}h_{k}(x)⟩,

It follows from this, and the observation preceding (15), that

P_{rn,n}^{(k)}(q) = ⟨∇^{r}(e_{n})|_{t=1}, p_{1}(x)^{n−k}h_{k}(x)⟩.

Also, for a and b coprime, we have P_{a,b}^{(k)} = \binom{a}{k}a^{b−k−1}, which in the case k = 0 reduces to a formula obtained in [1] for the number of parking functions in the special case of Dyck paths, and a and b coprime.

References

[1] D. Armstrong, N. Loehr, and G. Warrington, Rational Parking Functions and Catalan Numbers, Ann. Combin. 20 (2015), 21–58. 12

[2] J.-C. Aval, and F. Bergeron, Interlaced Rectangular Parking Functions, arXiv:1503.03991. 2, 6

[3] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Some Combinatorial Interpretations of q-Analogs of Schröder Numbers, Ann. Combin. 3 (1999), 171–190. 9

[4] F. Bergeron, Open Questions for Operators Related to Rectangular Catalan Combinatorics, J. Combin. 8 (2017), 673–703. 11

[5] F. Bergeron and A. M. Garsia, Science Fiction and Macdonald Polynomials, in: Algebraic Methods and q-Special Functions (L. Vinet, R. Floreanini, eds.), CRM Proceedings and Lecture Notes, American Mathematical Society, 1999. 10

[6] F. Bergeron, E. Leven, A. M. Garsia, and G. Xin, Compositional (km, kn)-Shuffle Conjectures, Intern. Math. Research Notices, Vol. 2016, 4229– 4270. 11

[7] T. L. Bizley, Derivation of a New Formula for the Number of Minimal Lattice Paths from (0, 0) to (km, kn) Having Just t Contacts with the Line and a Proof of Grossman’s Formula for the Number of Paths which May Touch but Do Not Rise above this Line, J. Inst. Actuar. 80 (1954), 55–62. 3

[8] J. Bonin, L. Shapiro, and R. Simion, Some q-Analogues of the Schröder Numbers Arising from Combinatorial Statistics on Lattice Paths, J. Statist. Plann. Inference 34 (1993), 35–55. 9

[9] E. S. Egge, J. Haglund, K. Killpatrick, D. Kremer, A Schröder Generalization of Haglund’s Statistic on Catalan Paths, Electron. J. Combin. 10 (2003), Article #R16, 21 pp. 8, 9, 10

[10] H. D. Grossman, Fun with Lattice Points: Paths in a Lattice Triangle, Scripta Math. 16 (1950), 207–212. 3

[11] M. Haiman, Combinatorics, Symmetric functions and Hilbert Schemes, in: CDM 2002: Current Developments in Mathematics in Honor of Wilfried Schmid & George Lusztig, International Press Books, 2003, pp. 39–112. 10

[12] A. Negut, The Shuffle Algebra Revisited, Int. Math. Res. Notices (2014) (22): 6242–6275. doi: 10.1093/imrn/rnt156 arXiv:1209.3349, (2012). 11

[13] N.J.A Sloane, The On-Line Encyclopedia of Integer Sequences,

http://oeis.org.

[14] C. Song, The Generalized Schröder Theory, Electron. J. Combin. 12 (2005), Article #R53, , 8

LaBRI, CNRS - Université de Bordeaux, 351 cours de la Libération, 33405 Talence, France

Département de Mathématiques, UQAM, C.P. 8888, Succ. Centre-Ville, Montréal, H3C 3P8, Canada.