BIJECTIONS FROM WEIGHTED DYCK PATHS TO SCHRÖDER PATHS

DAN DRAKE

Abstract. Kim and Drake used generating functions to prove that the number of 2-distant noncrossing matchings, which are in bijection with little Schröder paths, is the same as the weight of Dyck paths in which downsteps from even height have weight 2. This work presents bijections from those Dyck paths to little Schröder paths, and from a similar set of Dyck paths to big Schröder paths. We show the effect of these bijections on the corresponding matchings, find generating functions for two new classes of lattice paths, and demonstrate a relationship with 231-avoiding permutations.

1. Introduction and preliminaries

This work begins with the work of Kim and the present author [4] in which they studied, among other things, 2-distant noncrossing matchings. Such matchings—which will be defined shortly—are naturally enumerated by little Schröder paths. In the process of describing connections between k-distant noncrossing matchings and orthogonal polynomials, Drake and Kim used generating functions to show that little Schröder paths are equinumerous with a certain set of labeled Dyck paths. We present here a bijective proof of that fact; the bijection has a number of interesting properties and is a consequence of a bijection between big Schröder paths and a similar set of labeled Dyck paths.

We begin with definitions of the combinatorial objects mentioned above. The notation [n] refers to the set of positive integers from 1 to n. A matching of [n] is a set of vertex-disjoint edges in the complete graph on n vertices so that every vertex is adjacent to exactly one edge. For our purposes, a matching can also be viewed as a permutation whose cycles all have length 2, or a set partition whose blocks all have size 2. We will draw matchings by arranging the vertices horizontally and drawing arcs, as in Figure 1.

1 2 3 4 5 6 7 8 9 10 11 12

Figure 1: A matching of [12].

Drake and Kim [4] define a k-distant crossing as a pair of arcs (i_{1}, j_{1}) and (i_{2}, j_{2}), with i_{1} < i_{2} < j_{1} < j_{2} and j_{1} − i_{2} ≥ k. The arcs (6, 11) and (8, 12) of the matching in Figure 1 form a 3-distant crossing; the arcs (1, 4) and (3, 7) form a 1-distant crossing. A k-distant noncrossing matching is simply a matching with no k-distant crossing. The matching in Figure 1 is 4-distant noncrossing. (This notion of k-distant crossing is different from the k-crossings of matchings studied by, for example, Chen et al. [2]; their work concerns sets of k mutually crossing edges, and ignores the distance between vertices.)

1991 Mathematics Subject Classification. Primary: 05A19; Secondary: 05A15, 05A05.

Key words and phrases. lattice paths, Schröder numbers, matchings, 231-avoiding permutations.

In a 2-distant noncrossing matching, crossing edges are allowed as long as the right vertex of the left edge is adjacent to the left vertex of the right edge. This fact allows us to describe a bijection from 2-distant noncrossing matchings to a certain class of lattice paths. A lattice path of length n is a sequence (p_{0}, p_{1}, …, p_{n}) of points in ℕ × ℕ; the kth step of the path is the pair (p_{k−1}, p_{k}). A step is called an upstep if the component-wise difference of p_{k} −p_{k−1} is (1, 1), and a downstep if the difference is (1, −1). In this work, we will use paths with double horizontal steps, which is a pair of adjacent steps whose component-wise differences are both (1, 0). By a minor abuse of terminology, a double horizontal step will usually be called a horizontal step. A little Schröder path is a lattice path consisting of upsteps, downsteps, and horizontal steps, such that no horizontal step occurs at height zero. See Figure 2 for an example of such a path.

It is not difficult to describe a bijection from 2-distant noncrossing matchings to little Schröder paths: convert every vertex at the left end of an arc to an upstep and every vertex at the right end of an arc to a downstep—except for adjacent vertices involved in a crossing: convert those vertices into a horizontal step. This operation is a bijection because, given a little Schröder path, one can recover the matching by drawing an opening half edge at every upstep, two crossing half edges at every horizontal step, and a closing half edge at every downstep. Then connect every closing half-edge to the nearest opening half-edge to create a matching. See Figure 2 for an example of this correspondence.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Figure 2: An example of the bijection between 2-distant noncrossing matchings and little Schröder paths (left), and the correspondence between the edges incident to vertices of the matching and steps in the little Schröder path (right).

The little Schröder numbers s_{n} (sequence A1003 in the OEIS [5]) count 2-distant noncrossing matchings of [2n] and also little Schröder paths of length 2n. If horizontal steps on the x-axis are allowed, one has a big Schröder path; the number of such paths of length 2n is S_{n}, the big Schröder number (sequence A6318) and it is well known that S_{n} = 2s_{n} for n > 0; see the next section and also Deutsch’s bijective proof [3].

We need several more definitions related to lattice paths. The first is the step that matches a step. For an upstep u, the matching step is the rightmost downstep to the left of u that leaves from the same height at which the upstep ends; the definition for a downstep is similar. For a horizontal step h not on the x-axis, the matching step is the leftmost downstep to the right of h that leaves from the same height as h; in the corresponding 2-distant noncrossing matching, the matching downstep corresponds to the rightmost vertex involved in the two crossing edges. For example, the step matching the first horizontal step in Figure 2 is the last downstep. We will write paths using “U” for upsteps, “HH” for horizontal steps, “D” for regular downsteps, and “d” for special downsteps, which will be defined in section 2. The path in Figure 2 is UUDHHUHHDUUDDD.

1.1. Orthogonal polynomials and weighted Motzkin paths. When one has a sequence of positive numbers, in many cases it is possible to describe that sequence as the moments of a sequence of orthogonal polynomials. In other words, given {μ_{n}}_{n≥0}, define a measure (or a linear functional on polynomials; the two are equivalent here) by ∫ x^{n} dμ = μ_{n} and find polynomials {P_{n}(x)}_{n≥0} so that the integral

∫ P_{n}(x)P_{m}(x) dμ = 0

when n ≠ m and is nonzero when n = m. Many classical combinatorial sequences produce sequences of orthogonal polynomials: the Catalan numbers produce Chebyshev polynomials of the second kind, matching numbers produce Hermite polynomials, factorials produce Laguerre polynomials, and so on.

Viennot described a completely combinatorial theory of orthogonal polynomials [12, 13] in which the moments of a sequence of orthogonal polynomials are expressed as weighted Motzkin paths. A Motzkin path is a lattice path that consists of upsteps, downsteps and single horizontal steps (steps that move (1, 0)); a weighted Motzkin path has a weight λ_{n} associated with every downstep leaving from height n, a weight b_{n} for every horizontal step at height n, and weight 1 for all upsteps. For many orthogonal polynomial moment sequences, the weights b_{n} are zero, which means the corresponding moments may be described by weighted Dyck paths; a Dyck path is just a Motzkin path with no horizontal steps.

Drake and Kim [4] showed that the number of 2-distant noncrossing matchings of [2n]—little Schröder numbers—is the same as the total weight of weighted Dyck paths of length 2n in which downsteps leaving from odd height have weight 1, and downsteps leaving from even height have weight 2. They proved this equality using equation (2) of Kim and Zeng [6] (or equation (1) of Vauchassade de Chaumont and Viennot [11]), which in the present context is

(1)  s_{n} = ∑_{k≥0} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}2^{k};

in both works, the authors demonstrate that the sum above represents the generating function for the weighted Dyck paths described above. However, the sum also counts little Schröder paths, since \binom{n}{k}\binom{n}{k+1}/n is a Narayana number (sequence A1263), which counts Dyck paths of length 2n with k + 1 peaks and k ravines. A peak is an upstep immediately followed by a downstep, and a ravine is a downstep immediately followed by an upstep. Between two consecutive peaks, there must be exactly one ravine, so having k + 1 peaks is equivalent to having k ravines. Any ravine can clearly be “filled in” and replaced with a horizontal step, so a Dyck path with k ravines corresponds to 2^{k} little Schröder paths, which explains equation (1). On the other hand, any peak can be “flattened” into a horizontal step, so we also have

(2)  S_{n} = ∑_{k≥0} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}2^{k+1}

because peaks can occur on the x-axis. This provides one explanation for why there are twice as many big Schröder paths as little ones.

1.2. Plan of the paper. The aim of this work is to demonstrate a bijection from weighted Dyck paths whose downsteps at even height have weight 2 to little Schröder paths. That bijection will be a minor modification of a bijection from big Schröder paths to a similar class of Dyck paths; both bijections will in turn be consequences of more refined bijections between classes of little and big hybrid paths, which are described in section 2. In section 3 we show the effect of those bijections on the corresponding matchings, and then find generating functions for little and big hybrid paths in section 4. We finish by showing that our bijections are closely related to 231-avoiding permutations in section 5.

2. Description of the bijection

Instead of working with Dyck paths in which downsteps from even height have weight 2, we will work with Dyck paths in which such downsteps may or may not be labeled “special”; the two ideas are clearly equivalent. Such paths will be called even-special Dyck paths and abbreviated “ESDPs”; odd-special Dyck paths (ODSPs) are defined similarly.

We will first describe a bijection E_{∞} from odd-special Dyck paths to big Schröder paths—our desired bijection from even-special Dyck paths to little Schröder paths will follow from a minor modification of that bijection. The bijection E_{∞} will be a consequence of a more refined bijection E between two classes of what we will call big hybrid paths. Big hybrid paths include odd-special Dyck paths and any path obtained by applying E to a big hybrid path. To understand this recursive definition, we must define the map E.

Definition. Given a hybrid path, the map E does nothing to the path if the path contains no special steps. Otherwise, given a hybrid path with k horizontal steps, E yields a hybrid path with k +1 horizontal steps by the following procedure. Find the leftmost special step in the hybrid path. If that step is preceded by an upstep, flatten the upstep and special downstep by replacing them with a horizontal step. If the special step is preceded by a downstep d, find the upstep u that matches d and let P be the (possibly empty) subpath between u and d. Replace u with a horizontal step, delete d, slide P so that it follows the horizontal step, and make the original special step an ordinary downstep.

Figure 3 demonstrates the flatten and slide operations. All the paths in Figure 4 are big hybrid paths.

The map E clearly preserves the total number of special and horizontal steps and, for paths with at least one special step, reduces the number of special steps by one. It is also a bijection:

Theorem 1. The map E is a bijection from the set of odd-special Dyck paths of length n with no special steps to the set of big Schröder paths of length n with no horizontal steps. It is also a bijection from the set of big hybrid paths of length n with j special steps and k horizontal steps to the set of big hybrid paths with j − 1 special steps and k + 1 horizontal steps.

We will show that E is a bijection by describing a procedure for finding the horizontal step that was added last; the operation described in section 2 and Figure 3 is obviously reversible if we know which horizontal step was added last. Before giving the proof, let’s see why this identification is not as simple as it may sound. The problem is that sometimes E “moves forward” and sometimes E “moves backward”. Figure 4 shows what we mean by this. A horizontal step may be created by

(a) When the special step is preceded by an upstep, E and e simply “flatten” the two steps.

\begin{matrix}P \\ P \end{matrix}

(b) When the special step is preceded by a downstep, E and e find the matching up step and “slide” P.

Figure 3: The action of bijections E and e on the leftmost special down step in a hybrid path.

E to the left, to the right, or in the middle of the existing horizontal steps, so the left- or rightmost horizontal step need not be the last one added.

1 2 1 3 2 1 (a) The horizontal steps added by E move “backwards” when doing repeated slide operations.

1 1 2 1 2 3 (b) The horizontal steps added by E move “forwards” when doing repeated flatten operations.

1 1 2 1 2 3 (c) Horizontal steps can also be added between existing horizontal steps.

Figure 4: The horizontal steps created by E are not necessarily added left-to-right. The three paths on the far right look similar, but their horizontal steps were added in different orders.

One may think that, since horizontal steps from slides are always created at odd height and horizontal steps from flattenings are created at even height, it might be possible to use that information to identify the last-added step, but since slides change the height of parts of the path by one, a simple examination of odd and even heights will not suffice.

Proof of Theorem 1. The first statement of the theorem is trivial, as it is saying that E acts as the identity on the set of Dyck paths. For the second statement, we must show that it is possible to identify which horizontal step was added last. This can be done with the following procedure.

Partition the path into subpaths that consist of either a sequence of non-horizontal steps, or a horizontal step, its matching step, and all steps in between. The only part of a path altered by E when adding a horizontal step is between the horizontal step and its matching downstep, so if a horizontal step b is to the right of the downstep matching a horizontal step a, then b must have been added after a. (This is a special case of Lemma 9.) This fact tells us that the last-added horizontal step must be in the rightmost such subpath that contains a horizontal step. Call that subpath the first active subpath. Figure 5 illustrates this partitioning process.

Figure 5: The partitioning process to find the first active subpath, which is the rightmost subpath with a horizontal step.

If the first active subpath starts with a horizontal step on the x-axis, then, because horizontal steps on the x-axis can only be created with a flatten operation, the rightmost horizontal step in the subpath must be the last-added step.

Otherwise, we may assume the first active subpath starts with a horizontal step at some positive height. If that step is at odd height, that step is the last-added horizontal step, because the slide operation of E creates horizontal steps at odd height, and, as seen in Figure 4a, as one moves forward along a sequence of downsteps, some of which are special steps, E creates horizontal steps at the beginning of the first active subpath.

If the step at the beginning of the first active subpath is at even height, we must partition the path again. Now partition the first active subpath into sequences of horizontal steps at the same height as the original horizontal step and subpaths that begin with an upstep and end at the downstep matching the upstep. Call these two kinds of sequences valleys and hills, respectively. Using the same reasoning as before, the last-added horizontal step must be in the rightmost hill or valley that contains a horizontal step. Call that hill or valley the second active subpath. In the subpath of Figure 6, the final hill is the second active subpath.

If the second active subpath is a valley, the rightmost step in the valley is the most recently added horizontal step because steps in a valley must come from the flattening operation.

If the second active subpath is a hill, we recursively use the procedure described here to identify the last-added step within that hill. Since the hill begins at even height, the path is of the same form as the hybrid paths we began with.

Since the paths have finite length and the recursion step uses a shorter path than it started with, this procedure always finishes, and since the “exit points” always identify what must be the most recently added step, the procedure as a whole will identify the last-added horizontal step of a hybrid path. □

For example, with the second active subpath in Figure 6, we would recursively use the procedure on the final hill. The procedure in the proof above, given that hill (UUHHDd) as a single path

even height valley hill hill valley hill

Figure 6: Partitioning the first active subpath into hills and valleys. The second active subpath is the rightmost hill or valley with a horizontal step.

would identify HHD as the first active subpath then, since the horizontal step is at even height, partition again and identify the valley HH as the second active subpath, and finally declare that single horizontal step as the most recently added horizontal step. In Figure 7, step 12, starting at (14, 2), is the last-added horizontal step.

2.1. Consequences of the bijection. If we start with an odd-special Dyck path, we can use E to iteratively “evolve” the path into a big Schröder path. (In fact, we use E to suggest the word “evolve”.) Let E_{∞} be the resulting map from odd-special Dyck paths to big Schröder paths. Since E is a bijection and preserves the total number of special steps and horizontal steps, we have the following corollary of Theorem 1.

Corollary 2. The map E_{∞} is a bijection from odd-special Dyck paths of length n with k special steps to big Schröder paths of length n with k horizontal steps.

The operation described in section 2 and Figure 3 does not refer to the parity of the heights of the special steps, so we may use it with even-special Dyck paths. Define the map e the same way as E, but starting with even-special Dyck paths. Little hybrid paths are defined analogously to big hybrid paths. By simply switching “odd” and “even” in the proof of Theorem 1 and ignoring the possibility of sequences of horizontal steps on the x-axis, we see that e is also a bijection:

Corollary 3. The map e is a bijection from the set of even-special Dyck paths of length n with no special steps to the set of little Schröder paths of length n with no horizontal steps. It is also a bijection from the set of little hybrid paths of length n with j special steps and k horizontal steps to the set of hybrid paths with j − 1 special steps and k + 1 horizontal steps.

By defining e_{∞} analogously to E_{∞}, we accomplish our goal of showing bijectively that the little Schröder numbers enumerate even-special Dyck paths of length n:

Corollary 4. The map e_{∞} is a bijection from even-special Dyck paths of length n with k special steps to little Schröder paths of length n with k horizontal steps.

Figure 7 shows an example of e_{∞}.

The connections between colored or labeled Dyck paths and the little Schröder numbers have also been studied by Asinowski and Mansour [1, §4]; in their work, they colored ascents in Dyck paths with various kinds of paths. An ascent is a maximal sequence of up steps, and they colored ascents of length k with Fibonacci paths of length 2k, which they defined to be Dyck paths that consist only of pyramids (a pyramid is a Dyck path of the form U^{n}D^{n}). Asinowski and Mansour gave a bijection from the set of Dyck paths with ascents of length k colored by Fibonacci paths (D^{𝔉}(n), e_{∞}

Figure 7: An example of the bijection e_{∞}.

in their notation) to the set of little Schröder paths. This weighting of Dyck paths is different from the weighting of our even-special Dyck paths; for example, the path UUDUDD corresponds to four even-special Dyck paths but only two paths with ascents labeled by Fibonacci paths—one can label the initial UU ascent with UDUD or UUDD.

We can also enumerate even- and odd-special Dyck paths by number of special steps. Using the reasoning behind equations (1) and (2), which counted Schröder paths by changing peaks or ravines in Dyck paths into horizontal steps, the bijections above imply that the number of even-special Dyck paths of length 2n with j special steps is, for positive n,

(3)  ∑_{k≥0} N(n, k)\binom{k}{j} = N(n, j)_{2}F_{1} \binom{j − n j − n + 1}{j + 2} = \frac{1}{n}\binom{n}{j}\binom{2n − j}{n + 1},

where N(n, k) is again a Narayana number and the _{2}F_{1} notation is a hypergeometric function evaluated at one, which we can sum with the Chu-Vandermonde identity. The above triangle of numbers is sequence A126216. Similarly, the number of odd-special Dyck paths of length 2n with j special steps is, for positive n,

(4)  ∑_{k≥0} N(n, k)\binom{k + 1}{j} = N(n, j − 1)_{2}F_{1} \binom{j − n j − n − 1}{j} = \frac{1}{n − j + 1}\binom{n}{j}\binom{2n − j}{n};

the middle expression is not defined when j = 0, but in that case, the sum on the left is just the sum of the Narayana numbers—a Catalan number—so the rightmost expression is correct for all nonnegative j. The triangle in equation (4) is sequence A60693.

3. Hybrid paths as matchings

This work began with an investigation of certain matchings, and since little hybrid paths were developed to describe our bijection, it is fitting that we examine the connection between little hybrid paths and matchings. We already know that little Schröder paths correspond to 2-distant noncrossing matchings, so first we will describe an interpretation of even-special Dyck paths. Using the bijection from Schröder paths to matchings, a Dyck path with no special steps corresponds to a noncrossing matching, so it is reasonable to interpret special steps in the path as special edges in the matching. For example, the path UUdUUUDDdD corresponds to the noncrossing matching {(1, 10), (2, 3), (4, 9), (5, 8), (6, 7)} in which the edges between 2 and 3 and between 4 and 9 are special.

To interpret paths with both special steps and horizontal steps and understand the action of e in terms of paths, we need to define nesting. An edge (i_{1}, j_{1}) in a matching nests the edge (i_{2}, j_{2}) if i_{1} < i_{2} < j_{2} < j_{1}. An edge a in a matching immediately nests edge b if a nests b, and any other edge that nests b also nests a.

Before describing the action of the flatten and slide operations on “hybrid matchings”, we need one observation.

Lemma 5. Let h be a double horizontal step in a little hybrid path. Let d be the downstep matching h and u the upstep matching d. The step in the path corresponding to the rightmost (respectively, leftmost) vertex involved in the 1-distant crossing at h is either d (resp., u) or the leftmost (resp., rightmost) horizontal step to the right (resp., left) of h which is at the same height as h, whichever is closer to h.

Proof. A key idea in this proof is that a sequence of steps in a hybrid path that begins with an upstep and ending with the matching downstep—what we called a hill in the proof of Theorem 1— corresponds to a set of vertices in the matching that form a “submatching”. Let h be a double horizontal step in a little hybrid path, and partition the path as we did to find the second active subpath in the proof of Theorem 1 (but ignore the height of h). The first step in h corresponds to an opening half edge x. To what vertex will x be connected? Any hill to the right of h corresponds to a group of vertices that form a submatching, and hence x will not be connected to any of them. If there is a double horizontal step between h and d, then x will be connected to the vertex corresponding to the second step of the leftmost such double horizontal step; otherwise, x will be connected to the vertex corresponding to d. The proof for the “respectively” part of the statement is similar. □

For example, in Figure 2, the horizontal step at positions 4 and 5 corresponds to the 1-distant crossing in the matching in the same position; step 14 in the Schröder path is the downstep that matches the horizontal edge, so the right vertex of the edge incident to vertex 4 is vertex 14; and step 1 in the path is the upstep that matches step 14, so vertex 1 is the left vertex of the edge incident to vertex 5. Another example is UHHUDHHD; vertex 2 in the corresponding matching (which is {(1, 3), (2, 7), (4, 5), (6, 8)}) connects to vertex 7 because the second horizontal step is at the same height as the first, and is between the first horizontal step and its matching downstep.

Now we can describe the corresponding action of the bijection e on hybrid matchings.

Theorem 6. The analogue of the flatten operation for hybrid paths works as follows on matchings: given a special edge connecting vertices c and c + 1, find the edge that immediately nests that special edge; say it connects a and b. Then “swap the tails”: replace the edges (c, c + 1) and (a, b) with edges (c, b) and (a, c + 1).

Proof. The special downstep in the path (which is immediately preceded by an upstep, since we are doing a flatten operation) becomes a horizontal edge. So there will be 1-distant crossing at vertices c and c + 1. We only need to find the other two vertices involved; because of the way matchings are constructed from paths and Lemma 5, those other two vertices are a and b. □

To define the analogue of the slide operation, we need to define the transitive left endpoint of an edge. Given an edge e, the transitive left endpoint of that edge is simply the left endpoint of e—unless the edge is the right edge in a 1-distant crossing; then the transitive left endpoint of

\begin{matrix}M_{1} \\ M_{2} \\ M_{1} \\ M_{2} \end{matrix}

(a) The flatten operation when applied to a matching just “swaps tails”.

\begin{matrix}a \\ b \\ c \\ M_{1} \\ b − 1 \\ c + 1 \\ M_{2} \\ a \\ b \\ c \\ M_{1} \\ c + 1 \\ M_{2} \end{matrix}

(b) The slide operation when applied to a matching. Note that the edge from c to b − 1 may actually be several edges, as in UUUHHDdD, where b − 1 is 6 and c is 3.

Figure 8: The effect of e on matchings. This is the matchings version of Figure 3.

e is the transitive left endpoint of the left edge in the crossing. For example, the transitive left endpoint of the edge (6, 8) in the matching {(1, 5), (2, 3), (4, 7), (6, 8)} is 1. In little hybrid paths, the transitive left endpoint corresponds to finding the upstep that matches a downstep; because of Lemma 5, a matching upstep-downstep pair may not correspond to the left and right vertices of a single edge.

Theorem 7. The analogue of the slide operation for paths works as follows on matchings: given a special edge (a, b), let c be the transitive left vertex of the edge incident to vertex b − 1. The slide operation on hybrid paths corresponds to replacing (a, b) and (c, b−1) with edges (a, c+1) and (c, b) and sliding all half edges incident to vertices from c + 1 to b − 2 to the right by one vertex.

Proof. Since we are doing a slide operation, the special step in the path must be preceded by a ordinary downstep, which means b − 1 must be the right vertex of an ordinary edge nested by the special edge. The new 1-distant crossing created by the slide operation will be at the upstep that matches the downstep at b − 1, which as we saw above is the transitive left endpoint of the edge incident to b − 1 in the matching. We create the new crossing at vertices c and c + 1; the slide operation on the path moves all steps from c + 1 to b − 2 to c + 2 to b − 1, so all half edges incident to vertices from c + 1 to b − 2 are moved to the right one vertex. □

Figure 8 demonstrates these two operations for matchings.

4. Enumeration of hybrid paths

Having defined and used hybrid paths it is natural to wonder just many of them there are. Let L_{n} and B_{n} be the number of little and big hybrid paths, respectively. All big Schröder paths and odd-special Dyck paths are big hybrid paths, and Dyck paths, which are counted by the Catalan number C_{n}, are both big Schröder paths and OSDPs, so B_{n} is certainly at least 2S_{n} −C_{n}, but there are paths such as HHUd which are neither Schröder paths nor odd-special Dyck paths. Table 1 shows the number of all hybrid paths, little and big, for some small values of n.

n:  0 2 4 6  8  10  12  14  16  18  20  22
little: 1 1 4 18 87 439 2278 12052 64669 350733 1918152 10560678
big: 1 3 11 47 219 1075 5459 28383 150131 804515 4355163 23768079

Table 1: The number of little and big hybrid paths.

One way to count hybrid paths is to begin with even- and odd-special Dyck paths with j special steps, which are counted in equations (3) and (4); repeatedly applying e or E to such a Dyck path will produce j hybrid paths. Multiplying those equations by j + 1 and summing over j yields, for little hybrid paths,

(5)  L_{n} = C_{n} _{3}F_{2} (\begin{matrix}−n & −n + 1 & 2 \\ & −2n & 1 \end{matrix} ; −1) ,

where C_{n} is a Catalan number and the hypergeometric function is now evaluated at −1. Similarly, the number of big hybrid paths is

(6)  B_{n} = C_{n} _{3}F_{2} (\begin{matrix}−n & −n − 1 & 2 \\ & −2n & 1 \end{matrix} ; −1) .

Another way to enumerate these paths is to find their generating functions. Let L(x) and B(x) be the generating functions for little and big hybrid paths, respectively. We will use the following generating functions: E(x) and O(x) for even- and odd-special Dyck paths, and s(x) and S(x) for little and big Schröder paths. Of course, we already know that E(x) = s(x), O(x) = S(x), S(x) = 2s(x) − 1, and

s(x) = \frac{2}{1 + x + \sqrt{x^{2} − 6x + 1}},

but it will be helpful to use different names to keep different types of paths separate. In all the generating functions considered here, paths of length 2n are weighted by x^{n}.

Theorem 8. Let R = \sqrt{x^{2} − 6x + 1}. The ordinary generating function for little hybrid paths is

(7)  L(x) = \frac{R + 1 − x}{2} · \frac{2(R + x)}{R(R + x + 1)} · \frac{2}{R + x + 1}

and the ordinary generating function for big hybrid paths is

(8)  B(x) = (\frac{R + 1 − x}{2} − 1 + x − \frac{R(R + x)}{2} + \frac{3}{2} − \frac{3x}{2}) \frac{2(R + x)}{R(R + x + 1)} · \frac{2}{R + x + 1}.

More explicitly, we have

(9)  L(x) = \frac{1}{8x} (3x + 1 − \frac{3x^{2} − 8x + 1}{\sqrt{x^{2} − 6x + 1}})

and

(10)  B(x) = \frac{1}{2x} (1 − \frac{2x^{2} − 7x + 1}{\sqrt{x^{2} − 6x + 1}}) − 1.

Proof. We will decompose little and big hybrid paths to express L and B in terms of each other and then solve the system. A key idea is that raising a big hybrid path up one unit and sandwiching it between an upstep and downstep yields a valid little hybrid path, since all the step height parities have effectively been reversed. Doing the same thing to a little hybrid path yields a big hybrid path, although the resulting path will never have a horizontal step at height 1.

Every nonempty little hybrid path may be decomposed into an upstep, a big hybrid path P, a downstep, then a little hybrid path Q, as shown in Figure 9. Any pair P and Q is allowed, unless P has a special step and Q has a horizontal step.

big hybrid P

little hybrid Q

Figure 9: A decomposition of a nonempty little hybrid path.

Assume that P has a special step, so that Q has no horizontal step. Since S(x) counts big hybrid paths with only upsteps, downsteps, and horizontal steps—in other words, with no special steps— the generating function for big hybrid paths with a special step is B(x) − S(x); similar reasoning shows that the generating function for little hybrid paths with no horizontal steps is simply E(x). Thus the generating function for little hybrid paths with a special step in their first components is x(B(x) − S(x))E(x).

On the other hand, if P doesn’t have a special step, then it is a big Schröder path and Q can be any little hybrid path. The generating function for little hybrid paths with no special step in their first components is therefore xS(x)L(x).

Every nonempty little hybrid path can be uniquely decomposed in this way and falls into exactly one of the above categories, so adding in the empty path we have

L(x) = 1 + x(B(x) − S(x))E(x) + xS(x)L(x),

or, solving for L,

(11)  L(x) = \frac{1 + x(B(x) − S(x))E(x)}{1 − xS(x)}.

The decomposition for big hybrid paths is slightly more involved. Given a big hybrid path with an upstep, let s be the first downstep to return to the x-axis and decompose the path as in Figure 10. In any such big hybrid path, either there is or is not a special step before Q.

little hybrid P s

big hybrid Q

Figure 10: A decomposition of a big hybrid path with an upstep. The path begins with a possibly empty sequence of horizontal steps. The step s is the first downstep to return to the x-axis; it may or may not be a special step.

Assume that there is a special step before Q, and that s is special. In that case, P can be any little hybrid path, because if s is special, we know that no horizontal steps can appear in P at height 1—such a step has s as its matching downstep and can only be created with a slide operation that would make s an ordinary step. Since there are no horizontal steps at height 1, P can be any little hybrid path, and since there are special steps preceding Q, it cannot have any horizontal steps, and hence is an odd-special Dyck path. The generating function for the possibly empty sequence of horizontal steps at the beginning is 1/(1 − x), so the generating function for paths of this type is xL(x)O(x)/(1 − x).

If a special step appears before Q and s is ordinary, then P must have a special step and cannot have a horizontal step at height 1. Assume there is such a horizontal step h. The step h is at odd height and its matching step is s, so the only way h could be created is by a slide operation that converts s from a special to an ordinary step, but since we process special steps left to right, s would be converted from special to ordinary only if there were no special steps in P, which is a contradiction. This means that P can be any little hybrid path with a special step; the generating function for such paths is L(x) − s(x). The subpath Q can therefore be any odd-special Dyck path, so the generating function for all such big hybrid paths is x(L(x) − s(x))O(x)/(1 − x).

Finally, if there is no special step preceding Q, then P can be any big Schröder path, and Q can be any big hybrid path. The generating function for such big hybrid paths is xS(x)B(x)/(1 − x).

Every big hybrid path with an upstep falls into exactly one of the categories above, so, including paths that consist only of a sequence of horizontal steps on the axis, we have

B(x) = \frac{1}{1 − x} + \frac{xL(x)O(x)}{1 − x} + \frac{x(L(x) − s(x))O(x)}{1 − x} + \frac{xS(x)B(x)}{1 − x},

or, solving for B,

(12)  B(x) = \frac{1 + xL(x)O(x) + x(L(x) − s(x))}{1 − x − xS(x)}.

Solving the system of equations (11) and (12) and using the fact that

s(x) = E(x) = \frac{2}{1 + x + R} = \frac{1 + x − R}{4x} and

S(x) = O(x) = \frac{4}{1 + x + R} − 1 = \frac{1 + x − R}{2x} − 1,

we obtain the desired expressions for L(x) and B(x). □

It may seem that the generating functions L and B were described in equations (7) and (8) in an unusual way, but the expressions show that L and B are in some sense built out of familiar generating functions for paths:

\frac{2(R + x)}{R(R + x + 1)} = 1 + 2x + 7x^{2} + 30x^{3} + 141x^{4} + ⋯

is the generating function for sequence A116363, which counts dot products of rows of Pascal’s and Catalan’s triangle, and of course 2/(R + x + 1) is the generating function for the little Schröder numbers. Also appearing in both L and B is

\frac{R + 1 − x}{2} = 1 − x − xS(x),

a minor modification of the generating function for the big Schröder numbers. In B, we see that we have exactly −xS(x); the remaining terms in B are

−\frac{R(R + x)}{2} + \frac{3}{2} − \frac{3x}{2}

which is 1 + x + x^{2}S(x).

The expressions in (9) and (10) for L(x) and B(x) allow us to derive new expressions for the numbers of little and big hybrid paths. The expression 1/\sqrt{x^{2} − 6x + 1} is the generating function for the central Delannoy numbers (sequence A1850). The central Delannoy number D_{n} can be interpreted as the number of lattice paths from (0, 0) to (n, 0), not necessarily above the x-axis, consisting of upsteps, downsteps, and double horizontal steps; they can be expressed as

D_{n} = ∑_{k≥0} \binom{n}{k}^{2}2^{k}.

See Sulanke [10] for basic facts about the central Delannoy numbers and a collection of objects enumerated by them. Using the generating function expressions, one may easily derive the number of little hybrid paths of length 2n. Equation (9) implies that

(13)  L_{n} = −\frac{1}{8}[x^{n+1}]\frac{3x^{2} − 8x + 1}{\sqrt{x^{2} − 6x + 1}} = −\frac{1}{8}(D_{n+1} − 8D_{n} + 3D_{n−1}),

and similarly (10) implies that

(14)  B_{n} = −\frac{1}{2}[x^{n+1}]\frac{2x^{2} − 7x + 1}{\sqrt{x^{2} − 6x + 1}} = −\frac{1}{2}(D_{n+1} − 7D_{n} + 2D_{n−1}).

Both expressions above are valid for n ≥ 1 and are, of course, equal to the expressions in (5) and (6), respectively. My thanks to the anonymous referee for pointing out the relationship between the generating functions L(x) and B(x) and the central Delannoy numbers.

5. The bijections E and e and 231-avoiding permutations

While using the bijections E or e, one can keep track of the order in which horizontal steps are added and thereby associate a permutation to an even- or odd-special Dyck path. For example, the paths in Figure 4 correspond to the permutations 321, 123, and 132; the path in Figure 7 corresponds to 12387465. In this section we will see that every permutation so obtained must avoid the pattern 231. This is very interesting, since 231-avoiding permutations are counted by the Catalan numbers and hence are in bijection with Dyck paths; see Mansour et al. [7, §3.1].

A permutation π = π_{1}π_{2} ⋯ π_{n} written in one-line notation contains a pattern σ (another permutation) if there is some subset of the π_{i}’s that are order-isomorphic to σ. A permutation avoids a pattern if it does not contain it. The permutation 12584367 contains the pattern 231 because the subset 583 is order-isomorphic to 231, and avoids the pattern 3124. The notation S_{n}(231) refers to the set of 231-avoiding permutations of [n].

We start with a lemma that tells us exactly when the horizontal steps created by two special steps are added out of order—that is, when two special steps create the pattern 21. Given a special step s, let h(s) refer to the horizontal step created when s is turned into an ordinary step.

Lemma 9. Given two special steps a and b in a hybrid path with a to the left of b, h(b) is created to the left of h(a) if and only if b is preceded by a downstep d and the upstep matching d is to the left of a.

Proof. We only need to examine three possibilities: b is preceded by an upstep, b is preceded by a downstep whose matching upstep is to the right of a, and b is preceded by a downstep whose matching upstep is to the left of a. To work through those three cases, we need to use the fact that for any special step s, h(s) is created to the left of s and to the right of the downstep matching s. (When doing a flatten, “to the left” and “to the right” are weak inequalities, since the horizontal step will be created in the same position as those steps.)

In the first case, if b is preceded by an upstep, then h(b) will clearly be to the left of h(a), since h(b) will be created at the position of b, which is to the right of a.

If b is preceded by a downstep whose matching upstep is to the right of a, let u be that matching upstep. Since h(b) will be created at u and the following step, h(b) is to the right of a and hence to the right of h(a).

Finally, if b is preceded by a downstep whose matching upstep is to the left of a, let u be that matching upstep. See Figure 3b; b would be the special step pictured in that figure, u would be the upstep, and a would be somewhere in the subpath P, and since the upstep matching a is also in that subpath, h(b) will be created to the left of h(a). □

With that result, we can easily prove the following theorem.

Theorem 10. The permutation corresponding to the order in which horizontal steps are added while transforming an even- or odd-special Dyck path into a small or large Schröder path avoids the pattern 231.

Proof. Consider any three special steps a, b, and c in a hybrid path, appearing in that order left to right. If these three steps cause the corresponding permutation to contain 231, then we must have h(b), h(c), and h(a) in that order. The bijections E and e process special steps left to right, so we first create h(a), and then create h(b) to the left of that. Now we must have h(c) created to the right of h(b), which means by Lemma 9 either c is preceded by an upstep, or is preceded by a downstep whose matching upstep is to the right of b, but both of those possibilities cause h(c) to be to the right of h(a), which is a contradiction. □

The permutations produced are therefore a subset of 231-avoiding permutations; next we will see that every such permutation can be obtained from some even- or odd-special Dyck path.

Theorem 11. Every 231-avoiding permutation can be obtained from some odd-special Dyck path.

Proof. Given a 231-avoiding permutation π = π_{1} ⋯ π_{n}, we use the following recursive procedure to construct an odd-special Dyck path that, when using E_{∞}, will create horizontal steps in the order specified by π.

To begin with, the empty permutation corresponds to the empty path. Given a nonempty permutation π of length n, if π_{n} = n, find the path corresponding to π_{1} ⋯ π_{n−1} and append the steps Ud to that path. (Recall that U refers to an upstep, and D and d refer to ordinary and special downsteps, respectively.) We will call this an append operation; it corresponds to the flatten operation. If a path P corresponds to the permutation π_{1}π_{2} … π_{n−1}, then the path obtained by appending Ud to P will correspond to π_{1}π_{2} … π_{n−1}n.

If the permutation does not end with n, we will need the lift operation, which is defined as follows: given an odd-special Dyck path of the kind produced by this procedure, find an upstep leaving from the x-axis and let Q be the subpath consisting of that upstep and everything following it. The lift operation, illustrated in Figure 11, replaces Q with a path consisting of two upsteps, then Q, then an ordinary downstep and a special downstep. The lift operation corresponds to the slide operation of E and e.

\begin{matrix}P \\ Q \\ P \\ Q \end{matrix}

Figure 11: The lift operation. If the resulting path has n special steps, in the corresponding permutation all numbers from P will precede n, and all numbers from Q will follow n.

For ease of description, define good insertion to be the operation of inserting n into a 231avoiding permutation of [n − 1] anywhere except at the end so that the resulting permutation is also 231-avoiding. We write P ↔ π if a path P, constructed using the append and lift operations, corresponds to the permutation π.

Assume P ↔ π, where π ∈ S_{n}(231). Say that we obtain π′ by good insertion of n + 1 after the kth entry of π. We need to show:

(1) that we can do a lift operation following the kth special step of P (that is, the kth special step ends on the x-axis), and

(2) the corresponding path P′ corresponds to π′.

The path Ud corresponds to the permutation 1, and both claims are true for that path-permutation pair. To prove the two claims in general, we need two propositions:

Proposition 12. If π ∈ S_{n}(231), good insertion can be done after the kth entry of π if and only if the first k entries of π form a permutation of [k].

Proposition 13. Assume that P ↔ π. The kth special step of P ends on the x-axis if and only if the first k entries of π form a permutation of [k].

The proof of the first is elementary and left to the reader. As for the second, let s be the kth special step of P. Assume s ends on the x-axis. Then by Lemma 9, the horizontal step for every special step to the right of s will be created to the right of s, which means the first k entries of π form a permutation of [k]. On the other hand, if s does not end on the x-axis, then because of the definition of the lift operation, there must be a special step to the right of s that is immediately preceded by a downstep d, with the upstep matching d to the left of s. Therefore, by Lemma 9, there will be a number bigger than k among the first k entries of π, so π_{1} ⋯ π_{k} will not form a permutation of [k].

The first claim above is now clear, since if π′ was obtained by good insertion into the (k + 1)st position of π, then the first k entries of π form a permutation of [k], which in turn means that the kth special step ends on the x-axis, and one can do a lift operation starting with following step.

The second claim is also easy to see: say π = π_{1} ⋯ π_{n} and π′ is obtained by good insertion after π_{k}. If one lifts P after the kth special step, the resulting path P′ will correspond to the permutation π′ because, following the lift operation, the special steps corresponding to π_{1} ⋯ π_{k} and to π_{k+1} ⋯ π_{n} will be turned into horizontal steps in the same order (they are either unchanged or simply raised by 2 units), and the final step of P′ is a special downstep that will be turned into a horizontal step that follows every horizontal step created by the first k special steps of P′ and precedes every horizontal step created by the (k + 1)st to nth special steps. □

Figure 12 shows an example of this procedure. The permutation 21354 is built from the permutation 1 with the sequence “good insert into position 1, append, append, good insert into position 4”; the path is built using the corresponding append and lift operations in the same order.

21354 2134 213 21 1

Figure 12: An example of the recursive procedure to build an OSDP corresponding to a 231-avoiding permutation. Here we see how the path for 21354 is built up from the path Ud. Below each path is the corresponding permutation.

One can also obtain every 231-avoiding permutation with even-special Dyck paths simply by taking a path produced by this procedure and sandwiching it between an upstep and an ordinary downstep. That produces an even-special Dyck path that clearly corresponds to the same permutation.

We close with an interesting conjecture. The paths produced for 231-avoiding permutations of [n] are not all the same length; the lengths range from 2n for the path corresponding to 123 ⋯ n to 4n − 2 for the path corresponding to n(n − 1) ⋯ 21. An obvious question to ask is: how are the lengths distributed? In other words, find the coefficients of the polynomial

∑_{π∈S_{n}(231)} q^{pathlen(π)},

where pathlen(π) is the length of the path corresponding to π using the construction above. We can also sum that expression over all n, since for a given length there can be only finitely many permutations that correspond to a path of that length, and ask what generating function we get.

The lengths appear to have the Narayana distribution; see sequence A1263 and Sulanke [9]. The table below shows the polynomials for some small values of n.

n distribution of lengths n distribution of lengths
1 q^{2}  4 q^{14} + 6q^{12} + 6q^{10} + q^{8}
2 q^{6} + q^{4}  5 q^{18} + 10q^{16} + 20q^{14} + 10q^{12} + q^{10}
3 q^{10} + 3q^{8} + q^{6}  6 q^{22} + 15q^{20} + 50q^{18} + 50q^{16} + 15q^{14} + q^{12}

Table 2: The lengths of the OSDPs corresponding to 231-avoiding permutations of [n] appear to be Narayana-distributed.

Conjecture 14. The lengths of the paths corresponding to 231-avoiding permutations of [n] using the above construction have the Narayana distribution; that is,

(15)  ∑_{π∈S_{n}(231)} q^{pathlen(π)} = q^{2n} ∑_{k≥0} N(n, k)q^{2k},

where N(n, k) is a Narayana number. We also have

(16)  ∑_{n≥0} ∑_{π∈S_{n}(231)} q^{pathlen(π)} = \frac{1 − q^{2} + q^{4} − \sqrt{1 − 2q^{2} − q^{4} − 2q^{6} + q^{8}}}{2q^{4}} .

The right-hand side of equation (16) is the generating function for generalized Catalan numbers described by Stein and Waterman [8] (see the m = 1 column of Table 1), and by Vauchassade de Chaumont and Viennot [11]. Those numbers are sequence A4148, and count secondary structures of RNA molecules according to the number of bases.

6. Sage code

Readers interested in programming code for working with the various paths, bijections, matchings, and permutations described here may find code for the Sage mathematics software system (see sagemath.org) at arxiv.org/abs/1006.1959. On that page, click “Other formats”, then “Download source”, and look for the file code for dyck schroeder.sage in the resulting archive.

Concerned with sequences: A000108, A001003, A001263, A001850, A004148, A006318, A060693, A116363, A126216.

References

[1] Andrei Asinowski and Toufik Mansour, Dyck paths with coloured ascents, European Journal of Combinatorics 29 (2008), no. 5, 1262–1279, doi:10.1016/j.ejc.2007.06.005, MR 2419229.

[2] William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley, and Catherine H. Yan, Crossings and nestings of matchings and partitions, Transactions of the American Mathematical Society 359 (2007), no. 4, 1555–1575 (electronic), http://dx.doi.org/10.1090/S0002-9947-06-04210-3 doi:10.1090/

S0002-9947-06-04210-3, MR 2272140.

[3] Emeric Deutsch, A bijective proof of the equation linking the Schröder numbers, large and small, Discrete Mathematics 241 (2001), no. 1-3, 235–240, http://dx.doi.org/10.1016/S0012-365X(01)00122-4 doi:10.1016/

S0012-365X(01)00122-4, MR 1861420.

[4] Dan Drake and Jang Soo Kim, k-distant crossings and nestings of match-

ings and partitions,  DMTCS Proceedings AK (2009),  349–360,  available from

www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAK0129.

[5] N. J. A. Sloane (ed.), The on-line encyclopedia of integer sequences, 2010, available from

www.research.att.com/^{∼}njas/sequences/.

[6] Dongsu Kim and Jiang Zeng, Combinatorics of generalized Tchebycheff polynomials, European Journal of Combinatorics 24 (2003), no. 5, 499–509, doi:10.1016/S0195-6698(03)00046-5, MR 1983674.

[7] Toufik Mansour, Eva Y. P. Deng, and Rosena R. X. Du, Dyck paths and restricted permutations, Discrete Applied Mathematics 154 (2006), no. 11, 1593–1605, doi:10.1016/j.dam.2006.02.004, MR 2229432.

[8] P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Mathematics 26 (1979), no. 3, 261–272, doi:10.1016/0012-365X(79)90033-5, MR 0535254.

[9] Robert A. Sulanke, The Narayana distribution, Journal of Statistical Planning and Inference 101 (2002), no. 1-2, 311–326, http://dx.doi.org/10.1016/S0378-3758(01)00192-6 doi:10.1016/S0378-3758(01)00192-6, MR 1878867.

[10] , Objects counted by the central Delannoy numbers, Journal of Integer Sequences 6 (2003), no. 1, Article 03.1.5, 19 pp. (electronic), MR 1971435.

[11] M. Vauchassade de Chaumont and Gérard Viennot, Polynômes orthogonaux et problèmes d’énumération en biologie moléculaire, Séminaire Lotharingien de Combinatoire 8 (1984), article B08l, 8 pp., available from

www.emis.de/journals/SLC/opapers/s08viennot.html.

[12] Gérard Viennot, Une théorie combinatoire des pôlynomes othogonaux generaux, Notes from a conference at the Université du Québec à Montréal, Sep 1983, available from

http://web.mac.com/xgviennot/Xavier Viennot/polyn%C3%B4mes orthogonaux.html.

[13] , A combinatorial theory for general orthogonal polynomials with extensions and applications, Orthogonal polynomials and applications (Bar-le-Duc, 1984) (Berlin), Lecture Notes in Mathematics, vol. 1171, Springer, 1985, pp. 139–157, doi:10.1007/BFb0076539, MR 838979.

Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, Daejeon, Korea

E-mail address: ddrake@member.ams.org
URL: http://mathsci.kaist.ac.kr/~drake