Bijections on Riordan Objects

BIJECTIONS ON RIORDAN OBJECTS ↔ ↔ (7,1,2,3,4,5,6) ↔ ↔ 0 BIJECTIONS ON RIORDAN OBJECTS 1 Abstract The Riordan Numbers are an integer sequence closely related to the well-known Catalan Numbers [2]. They count many mathematical objects and concepts. Among these objects are the Riordan Paths, Catalan Partitions, Interesting Semiorders, Specialized Dyck Paths, and Riordan Trees. That these objects have been shown combinatorially to be counted by the same sequence implies that a bijection exists between each pair. In this paper we introduce algorithmic bijections between each object and the Riordan Paths. Through function composition, we thus construct 10 explicit bijections: one for each pair of objects. Keywords: Riordan Numbers, Ordered Trees, Permutations, Lattice Paths, Catalan Partitions, Bijections 2 1. The Riordan Numbers The Riordan Numbers are the  sequence {1, 0, 1, 1, 3, 6, 15, 36, . . .} defined by the n−1 recursive formula rn = n+1 (2rn−1 + 3rn−2 ). They are found at Sloane [2] (A005043) and have a close connection to the Catalan Numbers. The Riordan Numbers solve a number of similar counting problems; They count the number of Riordan Paths, Riordan Trees, Catalan Partitions, and Riordan Permutations on n elements [2], as well as the Interesting Semiorders on n + 1 elements [6]. Given this connection between these various objects, it follows that a bijection exists between each pair. The aim of this paper is therefore to explicitly lay out and prove the validity of these bijections. The following sections will address each object individually, using the Riordan Paths as the central conduit. Bijections not explicitly laid out will intuitively follow via function composition. We will therefore begin with the basic concept of a Riordan Path, and move on to its relationships with each other object. 2. Riordan Paths Definition 1. A Motzkin Path of order n> 0 is a walk from the point (0, 0) to the point (n, 0) along integer lattice points, none of which lie below the x-axis, consisting of three types of steps: • up-steps from a point (i, j) to (i + 1, j + 1) • horizontal steps from a point (i, j) to a point (i + 1, j) • down-steps from a point (i, j) to a point (i + 1, j − 1). Due to their association with different types of elements further in the paper, these steps may also be referred to as initial, neutral, or terminal steps, respectively. (0,0) (8,0) Figure 1. A Motzkin Path of order 8. Definition 2. A Riordan Path of order n is a Motzkin Path of order n in which no neutral steps occur on the horizontal axis of the plane. We will denote the set of Riordan Paths of order n by Rn . BIJECTIONS ON RIORDAN OBJECTS (0,0) 3 (8,0) Figure 2. A Riordan Path of order 8. 3. Dyck Paths Dyck Paths are very similar to Riordan Paths, and as this section will show, Specialized Dyck Paths (SDP’s) are in essence of the same structure. The following theorems and proofs will show that Riordan Paths and SDP’s can be considered, for all intents and purposes, the same type of object. 3.1. Definitions. Dyck Paths have a number of essentially equivalent definitions, and we will use the following for the purposes of this paper: Definition 3. A Dyck Path is a lattice path in the integer lattice plane Z × Z consisting of steps in the directions (1, 1) (denoted U ) and (1, −1) (denoted D) which never pass below the x-axis [7]. A Dyck Path of order n is such a path from (0, 0) to (2n, 0). A Specialized Dyck Path of order n is a Dyck Path of order n with no peaks after odd steps. That is, given any point (2k + 1, h) that is a vertex of a Dyck Path, that point cannot be both preceded by an up-step and followed by a down-step. We denote the set of Specialized Dyck Paths SD n . Figure 3. The r5 = 6 SPD’s of order 5. Odd-numbered steps are dotted for verification that none are peaks. It is first necessary to specify three types of elements in SDP’s, so that we may associate them with either up-steps, horizontal steps, or down-steps in Riordan 4 Paths. We first notice that an SDP of order n has 2n steps, and thus we will pair these steps sequentially: The first two steps are paired together, the second two are paired, and so on. Given a pair of steps (s1 , s2 ) in a Dyck Path, there are four possibilities: (s1 , s2 ) = (U, U ), (U, D), (D, D), (D, U ). Since s1 is necessarily an odd step by our pairing, if (s1 , s2 ) = (U, D) then we have a peak after an odd-numbered step. Thus we only have three possibilities: (s1 , s2 ) = (U, U ), (D, U ), or (D, D). We denote these possibilities ι, ν, and τ , respectively. 3.2. Proofs. Theorem 1. Any Dyck Path is an SDP if and only if it is built with step pairs of type ι, ν and/or τ . Proof. It is clear from previous arguments that any SDP only has step pairs of type ι, ν and τ . Now suppose a Dyck Path D has only these types of step pairs. None of the middle vertices in these step pairs is a peak. Since these vertices comprise every vertex immediately following an odd-numbered step in D, D is an SDP.  Let R ∈ Rn , and let s denote the kth step of R. We now define the function Fn as follows. We construct its image D ∈ SD n by moving from left to right along the steps of R. • If s is an initial step, then the kth step pair of D is of type ι. • If s is an neutral step, then the kth step pair of D is of type ν. • If s is a terminal step, then the kth step pair of D is of type τ . We will now show how to construct the preimage of an SDP inductively. Theorem 2. Let R ∈ Rn−2 and let D ∈ SD n−2 . Now define Dip to be the SDP with the steps ι, τ added after the ith step pair, and let Rip be the Riordan Path with initial and terminal steps added after the ith step. If Fn−2 (R) = D, then Fn (Rip ) = Dip . Proof. Let all variables be as defined above. Since adding ι, τ after any step pair does not result in a step below the x-axis in Dip , this is indeed an SDP. Furthermore, adding an initial and terminal step in that order at any point in R will still result in a Riordan Path. We must now show that the two constructed paths actually correspond under Fn . The first k steps remain unchanged in both Dip and Rip , as do the last (n−2)−k steps in both cases. Since ι corresponds with an initial step, and τ corresponds with a terminal step, this shows that Fn (Rip ) = Dip .  Theorem 3. Let R ∈ Rn−1 and let D ∈ SDn−1 . Now define Dih to be the SDP with the step ν added after the ith step-pair si , where si = ν or si = ι. Also define Rih as the Riordan Path with a neutral step added after the ith step, where s i is either an initial step or a neutral step. If Fn−1 (R) = D, then Fn (Rih ) = Dih . Proof. Let all variables be defined as above. It is clear that Rih is a Riordan Path, since adding a horizontal step after another horizontal step or an up-step guarantees it is not added at height zero. Therefore we must now show that Dih is indeed a Dyck Path. Since the ith step of Dih is either of type ι or τ , the vertex after this step is of vertical height at least 1. A step pair of type ν after it would therefore BIJECTIONS ON RIORDAN OBJECTS 5 have minimum vertex height of 0, occurring only at the middle. Thus Dih is a Dyck Path, and furthermore, it is an SDP by Theorem 1. By arguments similar to the previous proof, we have that Fn (Rih ) = Dih  Theorem 4. Any SDP can be constructed with the methods used above. Proof. Let D ∈ SD n . It is necessary that D’s first step pair be of type ι, and its last be of type τ . This further implies that a peak exists somewhere in D. Suppose D has no steps of type ν. Then its peak is formed by step pairs of type ι and τ , which implies that we can construct D from some D 0 ∈ SD n−2 using the methods in Theorem 2. Now suppose D has a step of type ν, which we will denote s. Assume without loss of generality that the distance of s from the x-axis, measured from its two outer vertices, is the maximum for any step of type ν in D. If ν is preceded by a step of type τ , then there is a peak of the form ι, τ preceding s, again showing that this SDP was constructed with the methods in Theorem 2. If the step pair preceding s is not of type τ , then D was constructed from some D 0 ∈ SD n−1 as described in Theorem 3.  Theorem 5. Fn is a bijection for all n. Proof. From [2] we have that |Rn | = |SD n−1 | for all n. Thus in showing that Fn is onto we show that it is bijective. Let D ∈ SD n and assume Fk is a bijection for all k < n. By Theorem 4, D was constructed from some SDP D 0 where D0 ∈ SD n−1 or D0 ∈ SD n−2 . By Theorems 2 and 3, this shows that D has a preimage under Fn in either case.  4. Riordan Trees Riordan Trees, differing significantly in background and utility, are our first object to appear visually distinct from Riordan Paths. A simple bijection between these two objects does, however, exist, as the following theorems will prove. 4.1. Definitions. We begin with some fundamental definitions on trees in graph theory. Definition 4. The following definitions are adapted from [5]. • A tree is a combinatorial graph with no cycles. • A leaf edge of a tree is an edge sharing a vertex with exactly one other edge. • A parent edge f of an edge e is the edge adjacent to e in the path from e to the root. We say that e is a child of f . • A rooted tree is a tree in which one vertex is specified as the root. • The outdegree of a vertex in a rooted tree is the number of vertices to which it is adjacent in the direction away from the root. • Given two vertices u, v, we say that u is a parent of v, and the v is a child of u, if u and v share an edge and u lies on a path from v to the root. • Two vertices are called siblings if they share the same parent. • A cluster is a complete set of leaves that comprise all the children of a given parent. In Figure 6, edges 4,5 and 6 constitute a cluster. 6 • The height of an edge is the distance, counted in edges, from the root of the tree to that edge. In terms of a tree, height refers to the greatest height of any edge therein. • An ordered tree is a tree in which the left-to-right order of each vertex’s children is significant. • A Riordan Tree is an ordered tree in which no vertex is of outdegree 1. We denote the set of Riordan Trees on n edges Tn . Figure 4. The r4 = 3 Riordan Trees on 4 edges. Note that the middle and right-most trees are identical graphs, but are considered distinct because the trees are ordered. In constructing a bijection between Riordan Paths and Trees, we use an approach similar to Section 3; We distinguish three types of edges in Riordan Trees, and associate with them the three types of steps in a Riordan Path. Definition 5. Let u be a parent of v, where u and v are both vertices of a Riordan Tree. Let e be the edge that connects them. • We say that e is initial if v is the left-most child of u. • We say that e is terminal if v is the right-most child of u. • In any other case, we say that e is neutral. We see an example of this distinction in Figure 5. Figure 5. An example of a Riordan Tree. Initial edges are shown with shorter dashes, and terminal edges are shown with longer ones. Neutral edges are represented with solid lines. BIJECTIONS ON RIORDAN OBJECTS 7 4.2. The Bijection. We now have three types of edges and three types of steps to correlate with one another, but we must first introduce a method of ordering our edges. In terms of Riordan Paths, the left-to-right ordering intuitively presents itself, but an ordering isn’t so clear in terms of trees. We therefore use the following algorithm: The root’s initial edge is counted first. From each edge, we proceed up (that is, away from the root) to the next initial edge whenever possible. When this is not possible, we move to the nearest uncounted edge, giving precedence to edges on the left. This is exemplified in Figure 6. In either case, we only have one possible choice at any stage of the algorithm, and thus one tree cannot have its edges ordered in two ways using this method. We will use this edge ordering algorithm as the basis for some of the major inductive steps in the following proofs; Furthermore, when we discuss the kth edge of a Riordan Tree, it will be the kth edge that the algorithm counts. 6 5 8 9 4 3 7 10 2 1 Figure 6. An example of the edge counting algorithm. We are now ready to define our bijection Fn : Rn → Tn . Due to the nature of these structures, Fn is defined algorithmically. Given a Riordan Path R ∈ Rn , we construct its image T ∈ Tn as follows. Let sk and ek be the kth steps and edges in R and T , respectively, according to their respective counting algorithms. We thus have three cases: Case 1: sk is an initial step. In this case, we set ek to be on an initial edge. Case 2: sk is a neutral step. In this case, we set ek to be a neutral edge. Case 3: sk is a terminal step. In this case, we set ek to be a terminal edge. 4.3. Proofs. We begin with a few proofs concerning the edge ordering algorithm. Theorem 6. Let e be an edge in a Riordan Tree T counted after a cluster C ⊆ T . Furthermore, let ne denote the number of initial edges counted prior to e minus the number of terminal edges counted prior to e. Removing C from T does not change ne . Proof. It is simple to see that the edge ordering algorithm counts every edge in a cluster before leaving the cluster. Once the left-most sibling is counted, the closest edges to that initial edge are its siblings in the cluster. If e is outside of a cluster C 8 and counted afterward, then removing C removes exactly one initial edge and one terminal edge prior to e, leaving ne the same.  Theorem 7. Any edge e of a tree is preceded by at least as many initial edges as terminal ones. Furthermore, if e is not an initial edge, it is preceded by a strictly greater number of initial edges. Proof. For the case of a tree on two edges, this is trivially satisfied. We will thus proceed by induction on the number of edges of a tree. Assuming our hypothesis for k < n, we let T ∈ Tn and let e be an edge of T . If e is at the maximum height for any edge in T , then we simply remove e and all its siblings to obtain T 0 , which is covered under our inductive hypothesis. Let p denote the parent of e. If p does not exist, then T is a tree of height one and e is preceded by one initial edge and zero terminal edges, so we assume that p exists and note that p is still in T 0 . By our inductive hypothesis p is preceded by at least as many initial as terminal edges. Since there are no terminal edges counted between p and e in T , this shows that the same was true for e. If e is not initial, then it is counted after its left-most (initial) sibling, and thus is preceded by more initial edges than terminal edges. Now suppose e is not of maximum height and let ne denote the number of initial edges occuring before e minus that of the terminal edges. Since T must contain some other edge of maximum height, T contains a cluster that e does not belong to. By Theorem 6, removing this cluster from T does not affect ne , and because this smaller tree is covered under our inductive hypothesis, this shows that the hypothesis holds for e in T .  We now lay out the two primary methods of building Riordan Trees from those of smaller order. The first will add a neutral leaf after an initial leaf, which corresponds to adding a horizontal step after an up-step in a Riordan Path. Our second method will add a pair of leaves to any leaf, corresponding to adding a pair of up-down steps (in that order) to a Riordan Path. Theorem 8. Let T ∈ Tn−1 , and let ek denote the kth edge in T . If T has a preimage under Fn−1 and ek is an initial leaf, then Tkh , the tree with a neutral edge added to T immediately after ek , has a preimage under Fn . Proof. Let all variables be defined as above and suppose T has a preimage under Fn−1 . Now let e denote the neutral edge added in Tkh . Since ek is preceded by at least as many initial as terminal edges, and ek is an initial leaf, this means that e is counted next by the ordering algorithm, and furthermore, is preceded by at least one more initial edge than the number of terminal edges. In terms of our bijection, this translates to adding a horizontal step at height greater than zero after the kth up-step in the corresponding Riordan Path. Since this is operation results in valid Riordan Paths (it does not add horizontal steps of height less than 1) and Riordan Trees, this shows that Tkh has a preimage under Fn .  Theorem 9. Let T ∈ Tn−2 , and let R ∈ Rn−2 . Now let T 0 be the tree with a pair of initial and terminal edges added to a leaf of T , as shown in Figure 7. If T has a preimage under Fn−2 , then T 0 has a preimage under Fn . Proof. Let all variables be defined as above, let e1 , e2 be the two edges added to the leaf e to create T 0 from T , and suppose T has a preimage R under Fn−2 . Given that e is the kth element of T , we now have that R0 , the Riordan Path R with an BIJECTIONS ON RIORDAN OBJECTS 9 → Figure 7. Adding an initial-terminal pair to a leaf of a Riordan Tree. up-down pair of steps added after the kth step, is the preimage of T 0 under Fn . Adding an up-down pair of steps can occur at any point in a Riordan Path since the resulting path has neither edges below the axis nor horizontal edges on the axis. Since this operation is therefore valid, this completes the proof.  Theorem 10. Fn is a bijection for all n. Proof. We need only show that Fn is onto for all n to show that it is a bijection, since |Rn | = |Tn | [2]. We will prove this by induction, using n = 2 as a trivial base case. Let T ∈ Tn . Suppose T has a pair of leaves with no children that constitute a full branch; that is, an initial/terminal pair. Removing these two leaves, we’re left with a valid Riordan Tree of smaller order. By our inductive hypothesis and Theorem 9, this shows that T has a preimage under Fn . Now suppose T does not have such a pair. We therefore find the set of edges of maximum height in T , of which there are necessarily three by our assumption. One of these leaves is the edge counted immediately after an initial edge. Removing it, we obtain a tree of smaller order as described in Theorem 8. By this theorem and our inductive hypothesis, T has a preimage under Fn . This shows that Fn is onto, and thus bijective.  5. Catalan Partitions Catalan Partitions are subsets of the first n integers with a few interesting properties. They can be represented as sets, but can be more intuitively understood when represented graphically as a set of points on the perimeter of a circle. 5.1. Definitions. Definition 6. A partition A of a set X is a subset of the powerset of X such that its elements are pairwise disjoint and the union of all its elements is X. That is, if A = {A1 , A2 , . . . , Ak } where Ai ⊆ X, then ∪ki=1 Ai = X and Ai ∩ Aj = ∅ for all i 6= j. Definition 7. A Catalan Partition C of order n is a partition of {1, 2, . . . , n} with the following properties: • Each subset of C contains at least two elements. • The convex hulls of any two elements of C do not intersect when the elements are arranged on a circle. When we say “arranged on a circle”, we mean that we simply set n vertices on a circle and, starting at any vertex arbitrarily, label them clockwise from 1 to n. There are multiple ways to arrange any given partition in this manner, and so we note that two partitions are said to be equal if and only if their set representations are equal. 10 The concept of a convex hull is somewhat more complex, but since we are dealing exclusively in 2-space, we will define it as follows: Definition 8. The Convex Hull of a set of k vertices is the set of points bounded by the k-sided polygon with these vertices. In the case k = 2, this set consists of all the points in a straight line between the two vertices. 2 1 3 10 9 4 8 5 7 6 Figure 8. A Catalan Partition on 10 vertices, with set representation {{1, 2, 5}, {3, 4}, {6, 10}, {7, 8, 9}}. Initial vertices are shown with squares, neutral vertices with stars, and terminal vertices with circles. As we come to a new vertex vi for 1 ≤ i ≤ n, there are three possible cases for vi , due to the fact that a Catalan Partition cannot have any singletons: Case 1: vi is the first vertex we have come across for a given part. In this case, we say that vi is an initial vertex. Case 2: vi is the last vertex we have come across for a given part. In this case, we say that vi is a terminal vertex. Case 3: vi is neither the first nor last vertex we have come across for a given part. In this case, we say that vi is a neutral vertex. Definition 9. We say that a subset {vi , . . . , vi+k } is complete if the parts corresponding to its vertices are all some subset of {vi , . . . , vi+k }. We say that a subset is sequential if its indices are a sequence of integers i, i + 1, . . . , i + k. BIJECTIONS ON RIORDAN OBJECTS 11 5.2. The Bijection. Let {s1 , . . . , sn } denote the steps of a Riordan Path R and let {v1 , . . . , vn } denote the vertices of a Catalan Partition C to be constructed. We now consider the three cases for each step si of R and define Fn : Rn → Cn as follows: Case 1: si is an up-step. In this case, we set vi to an initial vertex. Case 2: si is a down-step. In this case, we set vi to a terminal vertex. Case 3: si is a horizontal step. In this case, we set vi to a neutral vertex. At first glance, this mapping appears ambiguous; we do not specify which part a given vertex will belong to when it is classified. Due to the specific properties of Catalan Partitions, however, we will find that given a Riordan Path there is only one possible partition we can create. v2 v1 v3 v10 v9 v4 v8 v5 v7 v6 Figure 9. An example of a Catalan Partition and its associated Riordan Path. Initial vertices are shown with squares, neutral vertices with stars, and terminal vertices with circles. 12 5.3. Proofs. Theorem 11. Let R ∈ Rn−1 with steps {s1 , . . . , sn−1 }, and let C ∈ Cn−1 with vertices {v1 , . . . , vn−1 }. Define Rih as the Riordan Path with steps {s1 , . . . , si , s, si+1 , . . . , sn−1 } where s is a horizontal step and si is not a down-step. Furthermore, define Cin as the Catalan Partition {v1 , . . . , vi , v, vi+1 , . . . , vn−1 } where v is a neutral vertex and vi is not terminal. If C has preimage R under Fn−1 , then Cin has preimage Rih under Fn . v2 v2 v v1 v1 v3 v10 v3 v10 v9 v9 v4 v8 v4 v8 v5 v7 v5 v6 v7 v6 s Figure 10. The partition and its associated path are unmodified on the left. On the right, we have added a neutral vertex to the partition, and a horizontal step to the path, as described in Theorem 11. Proof. Let all variables be as defined above, and suppose vi is not a terminal vertex. We now let v be the (i + 1)th vertex of C and set it to be neutral. This implies that some vj is in the same part as v, where j ≤ i. If vi is not in the same part as v, then some subset {vk , vk+1 , . . . , vi } with k > j must be complete in order to avoid intersecting convex hulls. Since vi is the last vertex in this subset, it is necessarily terminal. vi must be initial or neutral, however, so we now assume j = i, which means that vi and v are in the same part. Since v is counted immediately after vi , and vi is not terminal, we have indeed set v to be a neutral vertex, and {v1 , . . . , vi , v, vi+1 , . . . , vn } = Cin . Furthermore, the fact that vi and v are in the same part guarantees no possibility of introducing hull intersection. Reconstructing a Riordan Path R0 from Cin as described by Fn , we find that its first i steps are equivalent to those of R, and its last (n − 1) − i steps are equivalent to si+1 , . . . , sn . The step s, corresponding to the neutral vertex v, is a horizontal step. Since Fn−1 (M ) = C, and vi is not terminal, we have that si is either an up-step or a horizontal step, and thus adding a horizontal step after si is a valid operation. Thus, R0 = Mih , and Fn (Mih ) = Cin .  Theorem 12. Let R ∈ Rn−2 with steps {s1 , . . . , sn−2 }, and let C ∈ Cn−2 with vertices {v1 , . . . , vn−2 }. We now define Rip to be the SMP defined by the steps BIJECTIONS ON RIORDAN OBJECTS 13 {s1 , . . . , si , sa , sb , si+1 , . . . , sn−2 } where sa and sb are up- and down-steps, respectively, and define Cip as the Catalan Partition {v1 , . . . , vi , va , vb , vi+1 , . . . , vn−2 } where va and vb are initial and terminal vertices, respectively. If C has preimage R under Fn−2 , then Cip has preimage Rip under Fn . vb v2 v2 va v1 v1 v3 v10 v3 v10 v9 v9 v4 v8 v4 v8 v5 v7 v5 v6 v7 sa v6 sb Figure 11. The partition and its associated path are unmodified on the left. On the right, we have added initial and terminal vertices to the partition, and up- and down-steps to the path, as described in Theorem 12. Proof. Let all variables be as defined above. Since va is an initial vertex, it is the first vertex of some part in the subset {vb , vi+1 , . . . , vn−2 }. Similarly, vb is in the last vertex of some part in the subset {v1 , . . . , vb }. If va and vb are not in the same part, their parts’ convex hulls will intersect, and thus va and vb must constitute a single part. Any chord connecting points vj and vk where j ≤ i and k ≥ i will not intersect with the chord connecting va and vb , and thus Cip is a valid Catalan Partition. Reconstructing a Riordan Path R0 from Cip as described by Fn , we find that its first i steps are equivalent to those of R, and its last (n − 2) − i steps are equivalent to si+1 , . . . , sn−2 . Since va and vb are initial and terminal (respectively), sa is an up-step and sb is a down-step. Adding these two steps in succession does not change the height of any of the vertices of R, and does not involve a horizontal step, so this is a valid operation. Thus, R0 = Mip and Fn (Mip ) = C p .  Theorem 13. Any Catalan Partition can be constructed from a single pair of vertices via the operations detailed in Theorems 11 and 12. Proof. Let C ∈ Cn have vertices {v1 , . . . , vn }. We want to find a sequentiallyordered subset of vertices that constitute exactly one entire part, since we can remove one of its neutral vertices, or both of its vertices in the case that it has no neutral vertices, and still have a Catalan Partition. Let A1 be a complete subset of C whose vertices are sequential, the first being x1 and the last being y. Note that A1 = C trivially satisfies these restrictions, and thus A1 necessarily exists. If A1 does not constitute a single part, then there 14 exists some complete subset of sequential vertices occurring after x1 and before (yet possibly including) y, which we will denote A2 . We continue in this manner until we have found an An that constitutes a single part. If it has more than two vertices, then we can construct it from some C 0 ∈ Cn−1 using the operation described in Theorem 11. If Ai has exactly two vertices, than we can construct it from some C 00 ∈ Cn−2 using the operation described in Theorem 12. Since these two cases cover all possible partitions, this shows that any partition can be constructed with the given theorems.  Theorem 14. Fn is a bijection for all n ≥ 2. Proof. This will be a proof by induction, with the base case n = 2 being trivial. From [2] we have that |Rn+1 | = |Cn | for all n. If Fn is onto for all n, this implies that Fn is a bijection. Suppose C ∈ Cn and assume Fk is onto for all 2 ≥ k < n. By Theorem 13, C was generated by some partition C 0 ∈ Cn−1 or C 00 ∈ Cn−2 . By our inductive hypothesis, we have that C 0 or C 00 has a preimage under Fn−1 or Fn−2 , respectively. By Theorems 11 and 12, this shows that C has a preimage under Fn , and thus that Fn is onto.  6. Riordan Permutations Riordan Permutations, or RP’s, are another object counted by the Riordan Numbers. 6.1. Definitions. I will begin by assuming basic knowledge of permutations and present the three definitions that distinguish Riordan Permutations from their peers. These are essentially a formalization of the definitions given in [2]. Let P = (a1 , . . . , an ) represent a permutation on the first n positive integers: Definition 10. A 321-avoiding permutation is a permutation in which there exist no elements ai , aj , ak such that ai > aj > ak where i < j < k. Definition 11. An element ai of a permutation is a descent if ai > ai+1 where i < n. Definition 12. A left-to-right maximum of a permutation is an element ak such that ai < ak for all i < k. Definition 13. A Riordan Permutation of order n is a 321-avoiding permutation on the first n integers in which each left-to-right maximum is a descent. For example, there are six permutations for n = 3: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). The only permutation on 3 elements that is a Riordan Permutation is (3, 1, 2). In (1, 2, 3), (1, 3, 2) and (2, 3, 1) the first element is a leftto-right maximum and not a descent, as is the case with the last element in (2, 1, 3). (3, 2, 1) is clearly not a 321-avoiding permutation. Definition 14. There are three types of elements found in Riordan Permutations: • The element ai is a left-to-right maximum. In this case, ai is a terminal element. • The element ai−1 is a left-to-right maximum. In this case, ai is an initial. • Neither ai nor ai−1 are left-to-right maximums. In this case, ai t is a neutral element. BIJECTIONS ON RIORDAN OBJECTS 15 6.2. The Bijection. Let P = (a1 , . . . , an ) represent an SP on n elements. Rather than assigning the ith element of the permutation to the ith step in a Riordan Path, as has been done with previously studied objects, each ai corresponds to the ai th step in the Riordan Path. We thus define the function Fn (Rn ) → Pn algorithmically as follows: • ai is a terminal element. In this case, the ai th step in the path is a downstep. • ai is an initial element. In this case, the ai th step in the path is an up-step. • ai is a neutral element. In this case, the ai th step is a horizontal step. Though this gives us an idea of the meaning of each element in our permutations, we need a more precise manner of constructing a permutation from a given Riordan Path. We therefore define our bijection Fn : Rn → Pn in the following manner. Let R ∈ Rn and let P ∈ Pn . • Arrange the locations of the down-steps in order: d1 , d2 , . . . , dk . • Order the up-steps similarly: u1 , . . . , uk . • Let Hi denote the left-to-right sequence of horizontal steps occurring after ui but before ui+1 (in the case i = k, this is simply the set of horizontal steps occuring after uk ). We now define Fn (R) = (d1 , u1 , H1 , . . . , dk , uk , Hk ) = P (6,1,2,3,4,5) (5,1,2,6,3,4) A (2,1,4,3,6,5) B (5,1,2,3,6,4) (4,1,6,2,3,5) (3,1,4,2,6,5) (4,1,2,6,3,5) (3,1,2,6,4,5) (2,1,5,3,6,4) (3,1,6,2,4,5) (2,1,6,3,4,5) (4,1,5,2,6,3) C (5,1,6,2,3,4) (4,1,2,3,6,5) (3,1,5,2,6,4) Figure 12. The r6 = 15 Riordan Paths on 6 edges, along with their corresponding Riordan Permutations. 16 This bijection has a handful desirable results: • RP’s of the form (n, 1, 2, . . . , n − 1) clearly exist for all n ≥ 2. Under Fn , these permutations correspond with the Riordan Path having the maximum number of horizontal steps (Riordan Path “A” in Figure 12). • Since every left-to-right maximum is necessarily followed by a smaller number, each down-step is guaranteed to be preceded by an up-step. • a2 = 1 for all P ∈ Pn , and all n ≥ 2. Since a1 is always a left-to-right maximum, this means that the function always has the first step set to an up-step. Similarly, since ak = n is always a left-to-right maximum, the nth step is always a down-step. • RP’s of the form (2, 1, 4, 3, . . . , n, n − 1), where n is even, correspond with analogues of Riordan Path “B” in Figure 12. Just as we can continue to add pairs of the form k, k − 1 to the end of the permutation and retain its property of being an Riordan Permutation, we can add up-down pairs to the right side of the Riordan Path. • RP’s of the form (n/2 + 1, 1, n/2 + 2, 2, . . . , n, n/2), where n is even, have analogues for all such n and correspond with analogues of Riordan Path “C” in the figure. 6.3. Proofs. Theorem 15. Fn is well-defined for all n. That is, each element of Rn maps to an element of Pn . Proof. Let all variables be as defined in the previous section. We will first show that h < di for all h ∈ Hi . Suppose this is not the case. Then there is some horizontal step occuring after di and before ui+1 . We now have ui+1 > h > di . This implies that exactly i up-steps occur before di , or that di is touching the xaxis, as is ui+1 . But this would also require that h is on the x-axis, which is not possible in a Riordan Path. Thus we have that h < di for all h ∈ Hi . Since ui < di , di < di+1 , and h < di for all applicable i and all h ∈ Hi , this shows that the left-to-right maximums of P are the di ’s, correctly associating them to down-steps as laid out in the definition of Fn . Since di > ui for all i, this sets these left-to-right maximums as descents. We must now show that P is 321-avoiding. Suppose we have three elements ai , aj , ak with i < j < k and ai > aj > ak , and without loss of generality assume ai is a left-to-right maximum. By our construction of P , it is clear that aj and ak cannot both be associated with up-steps or horizontal steps; that is, we must have one of each. If aj corresponds to an up-step, then ak is a down-step with ak < aj , implying that it should have been listed before aj in P . If aj is a horizontal step, then the fact that ak is an up-step listed after it would imply that aj < ak . Thus there cannot exist a “321” in P . Since this algorithm has exactly one output in Pn , we conclude that Fn is welldefined for all n.  BIJECTIONS ON RIORDAN OBJECTS 17 P = (5 , 1, 2, 8, 3, 4, 11, 6, 15, 7, 9, 10, 16, 12, 13, 18, 14, 17) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 i 1 2 3 4 5 6 d i ui Hi 5 1 {2} 8 3 {4} 11 6 ∅ 15 7 {9, 10} 16 12 {13} 18 14 {17} Figure 13. a Riordan Path and its associated permutation, as constructed by the methods of Theorem 15. Dashed lines are shown for clarity. Theorem 16. Fn is a bijection for all n. Proof. From [2] we have that Rn and Pn are equally-sized sets for all n, and thus we need only show that Fn is onto. Let P ∈ Pn . We may assume that P corresponds to some type of path R under the algorithms of Fn , though it has yet to be shown whether R ∈ Rn . Since each left-to-right maximum in P is a descent, it corresponds to a path under Fn in which the number of up- and down-steps is equal, and furthermore, that each down-step corresponds with exactly one up-step preceding it. We now have that R is a Motzkin Path, and must therefore show that it is a Riordan Path; that is, we must show that any horizontal step in R lies above the x-axis. Suppose an element k of P corresponds to a horizontal step in R. Let d be the left-to-right maximum nearest to k on the left, and let u be the element lying immediately after d. We now have that the uth step in R is an up-step, the dth step in R is a down-step, and u < d. In order for k to be on the x-axis, it is at least necessary that k < u or k > d, so that the kth step occurs after the down-step or before the up-step. Since k corresponds to a horizontal step and d is the nearest left-to-right maximum on the left, we cannot have k > d, or else k would be a left-to-right maximum. If k < u, 18 however, then we have formed a “321” with d, u, k. Thus u < k < d, which implies that k cannot lie on the x-axis. This shows that R is a Riordan Path, and thus that Fn is onto. Since Fn is a well-defined onto function acting on two equally-sized sets, we conclude that Fn is a bijection for all n.  7. Interesting Semiorders The final and perhaps most distinct object to be presented is the Interesting Semiorder. From [6] we have that the number of Interesting Semiorders on n + 1 elements is rn , the nth Riordan Number. This paper also shows the validity of the bijection we will be presenting, and thus we will simply present the necessary definitions along with an explanation of the bijective algorithm. 7.1. Definitions. Definition 15. A partially ordered set (X, ≺) is a semiorder if it satisfies the following two properties for any a, b, c, d ∈ X. • If a ≺ b and c ≺ d, a ≺ d or c ≺ b. • If a ≺ b ≺ c, then d ≺ c or a ≺ d. Semiorders are also known as unit interval orders in the literature. This name comes from the fact that each element x ∈ X can be identified with an interval on the real line. All intervals are the same length, and two intervals intersect if and only if their corresponding elements are incomparable. If the intervals for a and b do not intersect, and the interval for a lies to the left of the interval for b, then a ≺ b. We may assume without loss of generality that the intervals in our representation have different endpoints. We define the predecessor (pred) and successor (succ) sets intuitively: pred(x) = {a ∈ X |a ≺ x} and succ(x) = {a ∈ X |x ≺ a}. For a semiorder, the predecessor and successor sets are weakly ordered (for different elements x and y, either pred(x) ⊆ pred(y), pred(y) ⊆ pred(x), or both, with the same criterion for successor sets). These impose two weak orderings on the set X, and their intersection is known as the trace. We denote the binary relation of this ordering by ≺T . A more intuitive explanation of the trace is that it simply refers to the left-to-right order of the elements in the semiorder. This is exemplified in Figure 15, where 10 ≺T 9 ≺T 8 ≺T . . . ≺T 1. A semiorder is interesting if it satisfies the following two criterion. • (Connectedness) Each element is incomparable with its predecessors in the trace. • (Irredundancy) No two elements have both the same predecessor sets and the same successor sets. Having laid out the idea of an Interesting Semiorder, we proceed to define a number of concepts related to the topic. Definition 16. The relations N and H are defined as follows, with xj ≺T xi • xi N xj if xj ∈ pred(xi ), xj+1 6∈ pred(xi ), and xj 6∈ pred(xi−1 ) • xi Hxj if xj 6∈ pred(xi ), xj−1 ∈ pred(xi ), and xj ∈ pred(xi+1 ) 1 1The definition give here is the inverse of the relation defined in [8], but we use this for the ease in discussing the bijection in the remainder. BIJECTIONS ON RIORDAN OBJECTS 19 As shown in [8], the semiorder can be reconstructed in its entirety by its nose and hollow relations. We also say that xi noses xj if xi N xj , and similarly, xi hollows xj if xi Hxj . A nose relationship can be more clearly understood as an instance where two comparable elements are just barely comparable, exemplified in Figure 15 by elements 1 and 3. A Hollow relationship is an instance where two elements are just barely incomparable, as is the case with elements 2 and 4. Alternatively, we may look at nose and hollow relations through an Incidence Matrix. An incidence matrix is a 0,1 step matrix such that a “1” in row x, column y implies y ≺ x. A “0” means simply that this is not the case. A nose occurs in a position where a “1” could be removed and still obtain a step matrix. A hollow occurs where a “1” could be added to retain this type of matrix. This is also shown in Figure 15 Rather than associating elements of the semiorders with edges in the Riordan Paths, as has been done up to this point, we account for the shift in indexes by associating elements to points. Definition 17. Let Pi represent the ith point in a Riordan Path of order n, where 1 < i < n. There are nine possibilities for any given point Pi . (i) Pi is a hard peak if Pi lies vertically above both of the points Pi−1 , Pi+1 . (ii-iii) Pi is a positive (negative) soft peak if Pi lies vertically above the point Pi−1 (Pi+1 ), and level with the point Pi+1 (Pi−1 ). (iv) Pi is a hard dip if Pi lies vertically below both of the points Pi−1 , Pi+1 . (v-vi) Pi is a positive (negative) soft dip if Pi lies vertically below the point Pi+1 (Pi−1 ), and level with the point Pi−1 (Pi+1 ). (vii-viii) Pi is a positive (negative) slope if it lies vertically above (below) P i−1 and vertically below (above) Pi+1 . (ix) Pi is a level point if it lies vertically level with Pi−1 , Pi+1 The nine types of points are shown graphically in Figure 14. 7.2. The Bijection. We will now define a mapping Fn : In+1 → Rn , where In is the number of interesting semiorders on n + 1 elements. Our bijection uses the nose and hollow relations on the elements of the semiorder to explicitly construct a Riordan Path. Let I ∈ In , and let xi denote the ith element of I where 1 < i < n. We will now define the nine possible cases for xi , and, for each, the type of point that xi will correspond to in the Riordan Path. A priori we have 16 types of elements in a semiorder, since for any element x we can have elements a, b such that aHx, bN x, xHa and xN b, or neither. However, it can be shown that seven of these cases do not occur in an Interesting Semiorder, leaving us with 9 types of elements to deal with: • 2 Hollows - There exist elements a, b such that aHxi , xi Hb, and there exists no element c such that cN xi or xi N c. In this case, we set the ith point in the path to a hard peak. • 2 Noses - There exist elements a, b such that aN xi , xi N b, and there exists no element c such that cHxi or xi Hc. In this case, we set the ith point in the path to a hard dip. • 2 Hollows, 1 Nose - There exist elements a, b such that aHxi , xi Hb, and there exists an element c such that xi N c (cN xi ). In this case, we set the ith point in the path to a positive (negative) soft peak. 20 Pi Pi Pi Hard Peak Positive Soft Peak Negative Soft Peak Pi Pi Pi Hard Dip Pi Positive Slope Positive Soft Dip Pi Negative Slope Negative Soft Dip Pi Level Point Figure 14. The nine possible types of points in a Riordan Path. Dashed curves represent hollow relations, and solid curves represent nose relations. • 2 Noses, 1 Hollow - There exist elements a, b such that aN xi , xi N b, and there exists an element c such that xi Hc (cHxi ). In this case, we set the ith point in the path to a positive (negative) soft dip. • 1 Nose, 1 Hollow - There exist elements a, b such that xi N a and xi Hb (aN xi and bHxi ), and there exists no element c such that cN xi or cHxi (xi N c or xi Hc). In this case, we set the ith point in the path to a positive (negative) slope. • 2 Noses, 2 Hollows - There exist elements a, b, c, d such that aN xi , bHxi , xi N c, xi Hd. In this case, we set the ith point in the path to be a level point. Since any two semiorders with different nose and hollow relations are different (as shown by Pirlot in [8]), as are any two paths with a different list of point types, this gives a well-defined map from In+1 to Rn . 8. Conclusions Thus far we have examined bijections between these Riordan Objects and the Riordan Paths. Naturally, we would like to have a bijection for any given pair BIJECTIONS ON RIORDAN OBJECTS 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 21 1 1 1 1 1 1 0 0 0 0 Incidence Matrix 10 6 9 2 5 3 8 1 4 7 Interval Representation 6 8 4 5 7 9 2 1 10 3 Riordan Path Figure 15. An example of an interesting semiorder I, given in matrix and interval representations, and its corresponding path. Circles and boxes in the matrix denote noses and hollows, respectively. Nose relations are shown in the path with solid curved lines, and hollow relations are shown with dashed red lines. of objects. For Specialized Dyck Paths, Riordan Trees, Catalan Partitions, and Riordan Permutations, these bijections follow naturally through composition. As we described earlier, Specialized Dyck Paths and Riordan Paths behave so similarly that we will only be considering Riordan Paths in Figure 16. Semiorders pose somewhat of a problem due to their extra element. In terms of associating these with trees or paths, function composition is still useful, except we must make slight alterations to the bijections to use vertices rather than edges. In 22 Riordan Paths Riordan Trees Catalan Partitions Riordan Permutations Up-Steps Horizontal Steps Down-Steps Initial Edges Neutral Edges Terminal Edges Initial Vertices Neutral Vertices Terminal Vertices Initial Elements Neutral Elements Terminal Elements Figure 16. The correspondence of the major Riordan Objects. To construct the bijection between any two objects listed, simply associate elements sharing the same column,using an appropriate ordering (for example, elements are ordered clockwise in Catalan Partitions, and left-to-right in Riordan Paths). terms of Catalan Partitions and Riordan Permuations, however, there have arisen no “natural” bijections using the handful constructed thus far as intermediaries. References [1] B.A. Davey, H.A. Priestley, “Introduction to Lattices and Order” [2] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://research.att.com/ njas/sequences [3] Weisstein, Eric W. ”Dyck Path.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/DyckPath.html [4] Weisstein, Eric W. ”Projective Space.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/ProjectiveSpace.html [5] Weisstein, Eric W. ”Tree.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/Tree.html [6] Balof and Menashe, “Semiorders and Riordan Numbers”, submitted to Journal of Integer Sequences (2007) [7] Toufik Mansour, “Counting Peaks at Height k in a Dyck Path”, Journal of Integer Sequences, Vol. 5, 2002 [8] Marc Pirlot “Minimal Representation of a Semiorder” Theory and Decision 28:109-141, 1990