Semiorders and Riordan Numbers

Barry Balof and Jacob Menashe Department of Mathematics Whitman College Walla Walla, WA 99362 USA

                      balofba@whitman.edu
                     menashjv@whitman.edu

Abstract In this paper, we define a class of semiorders (or unit interval orders) that arose in the context of polyhedral combinatorics. In the first section of the paper, we will present a pure counting argument equating the number of these interesting (connected and irredundant) semiorders on n + 1 elements with the nth Riordan number. In the second section, we will make explicit the relationship between the interesting semiorders and a special class of Motzkin paths, namely, those Motzkin paths without horizontal steps of height 0, which are known to be counted by the Riordan numbers.

1 Counting Interesting Semiorders

We begin with some basic definitions.

Definition 1. 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 a weak order known as the trace.

A semiorder is interesting if it satisfies the following two properties.

• (Connectedness) Each element is incomparable with its immediate predecessors in the trace.

• (Irredundancy) No two elements have both the same predecessor sets and the same successor sets.

We use I_{n} to denote the set of all interesting semiorders on n elements.

The criterion of connectedness guarantees that the semiorder is represented by a topologically connected set of distinct intervals on the real line. The criterion of irredundancy guarantees that the semiorder has a linear order as its trace (i.e., no two elements are incomparable in the trace). These criteria came about from the study of the polyhedral set of all representations of a semiorder. This polyhedron has one dimension for each element of the semiorder, save for the smallest element in the trace, and one dimension for the length of the intervals (which we denote the r-value). The connectedness criterion guarantees that the polyhedron is bounded along each hyperplane corresponding to a fixed r value (that is, if the interval length is bounded, then so is any numeric representation of the semiorder). The irredundancy criterion guarantees that each dimension will take on a different set of values for the polyhedron (that is, no two elements may be represented by the same interval in any representation of the semiorder). Though the motivation comes from the study of this polyhedron, the remainder of the paper will focus on the properties of the semiorders and an exploration of the following theorem.

Theorem 1. The number of interesting semiorders on n + 1 elements is the nth Riordan number, r_{n}. That is, |I_{n}| = r_{n}.

The Riordan numbers (1,0,1,1,3,6,15,36,91,...) are found at [5] (A005043) and explored in depth by Bernhart in [2]. This theorem is an order-theoretic analog of a graph-theoretic result of Hanlon [3].

We prove the result by showing that the number of interesting semiorders on n + 1 elements, which we will denote ρ_{n}, satisfies the same recurrence relation as do the Riordan numbers, namely that

c_{n} = ∑_{k=0}^{n} \binom{n}{k}ρ_{k} with ρ_{0} = 1

where c_{n} = \frac{1}{n+1} \binom{2n}{n} is the nth Catalan number (sequence [A000108]). The above recurrence for the Riordan numbers was proven in detail by Chen et. al. in [4].

Proof. We first check that the base case holds, namely that there is 1 interesting semiorder on 1 element (ρ_{0} = 1), which is the only semiorder on one element.

A semiorder on n + 1 elements can be represented by an n + 1 by n + 1 0-1 matrix, A, with the rows and columns labeled by the semiorder elements. The entry A_{i,j} is 1 if element i is above element j in the semiorder, and 0 otherwise. If the labels on the rows and columns are in accordance with the trace, then the matrix will be in echelon form with each row beginning with a string of zeroes and ending with a (possibly empty) string of ones. The set of leading ones in each row will form a ‘staircase’ pattern, as in Figure 2. We can move along the steps to obtain a path from the upper right to the lower left corner of the matrix. Since this path never goes below the diagonal, we have as many semiorders on n elements as we do lattice paths from (0, 0) to (n + 1, n + 1) that don’t go below the line y = x, the number of which is well known to be the n + 1st Catalan number, c_{n+1}.

If we restrict our attention to connected semiorders, the matrix has no non-zero entries in the sup-diagonal (a_{i,i+1}) or below. Hence, the lattice paths in question can be viewed as going from (1, 0) to (n, n + 1) without crossing the line y = x + 1, which are just counted by the nth Catalan number, c_{n}.

Suppose that there are ρ_{k} interesting semiorders on k +1 elements, and take an arbitrary connected semiorder on n+1 elements. Either it is irredundant, or for some pairs of elements x_{i} and x_{i+1} which are adjacent in the trace, x_{i} and x_{i+1} have the same predecessor sets and successor sets. There are n such adjacent pairs which might be ‘the same’ in this way. For each pair that is the same, iteratively replace them with a single element. If there are n − k such pairs the same, then what results is an interesting semiorder on n + 1 − (n − k) = k + 1 elements. There are ρ_{k} interesting semiorders on k + 1 elements, and hence there are \binom{n}{n−k}ρ_{k} = \binom{n}{k}ρ_{k} orders on n + 1 elements which reduce to an interesting semiorder on k + 1 elements. Summing over all possible values of k gives the desired recursion. Therefore ρ_{n} = r_{n}, the nth Riordan number.

2 Semiorder/Motzkin Path Bijection

It is known that the Riordan numbers count the number of Motzkin paths without horizontal steps of height zero. In the remainder of the paper, we make explicit a bijection between semiorders and these Motzkin paths. We begin with some more terminology about semiorders, and we follow definitions similar to those of Pirlot [6] for two other relations on the elements of a semiorder, nose relations and hollow relations.

2.1 Definitions and Terminology

In terms of the matrix A, we have that aNb if A_{ab} = 1, and changing that 1 to a 0 leaves a staircase matrix pattern. We have that cHd if A_{cd} = 0, and changing that 0 to a 1 leaves a staircase matrix pattern. We make another definition in terms of predecessor and successor sets.

Definition 2. The relations N and H are defined as follows, with x_{j} ≺_{T} x_{i}

• x_{i}Nx_{j} if x_{j} ∈ pred(x_{i}), x_{j+1} ∉ pred(x_{i}), and x_{j} ∉ pred(x_{i−1})

• x_{i}Hx_{j} if x_{j} ∉ pred(x_{i}), x_{j−1} ∈ pred(x_{i}), and x_{j} ∈ pred(x_{i+1}) ^{1}

As shown in [6], and in explicit detail in [7], the semiorder can be reconstructed in its entirety by its nose and hollow relations. We also say that x_{i} noses x_{j} if x_{i}Nx_{j}, and similarly, x_{i} hollows x_{j} if x_{i}Hx_{j}.

Definition 3. 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).

We denote by P_{i} the point on the path with x-coordinate i (0 ≤ i ≤ n) .

Motzkin paths are a generalization of the classic Catalan paths. The Catalan paths are often viewed as going from (0,0) to (k, k), and consisting of k horizontal and k vertical steps (that stay above the ‘baseline’ y = x). By rotating 45^{∘} and using the described up-steps and down-steps, a Catalan path can be viewed as going from (0, 0) to (2k, 0) (and staying above the ‘baseline’ y = 0). The primary difference between Catalan and Motzkin paths is that Motzkin paths allow for horizontal steps. As such, we can construct such paths from (0, 0) to (n, 0) for n even or odd. We further narrow our focus to the set of paths that will correspond to our set of semiorders.

Definition 4. A Riordan path of order n is a Motzkin path of order n in which no horizontal steps occur on the horizontal axis of the plane. We will denote the set of Riordan paths of order n by R_{n}.

We will make an explicit bijection between these Riordan paths and the set of interesting semiorders. We begin by closely examining the Riordan paths.

Definition 5. Let P_{i} represent the ith point in a Riordan path of order n, where 1 < i < n. There are nine possibilities for any given point P_{i}.

(i) P_{i} is a hard peak if P_{i} lies vertically above both of the points P_{i−1}, P_{i+1}.

(ii-iii) P_{i} is a positive (negative) soft peak if P_{i} lies vertically above the point P_{i−1} (P_{i+1}), and level with the point P_{i+1} (P_{i−1}).

(iv) P_{i} is a hard dip if P_{i} lies vertically below both of the points P_{i−1}, P_{i+1}.

(v-vi) P_{i} is a positive (negative) soft dip if P_{i} lies vertically below the point P_{i+1} (P_{i−1}), and level with the point P_{i−1} (P_{i+1}).

1The definition given here is the inverse of the relation defined in [6], but we use this for the ease in discussing the bijection in the remainder

(vii-viii) P_{i} is a positive (negative) slope if it lies vertically above (below) P_{i−1} and vertically below (above) P_{i+1}.

(ix) P_{i} is a level point if it lies vertically level with P_{i−1}, P_{i+1}

The nine types of points are shown graphically in Figure 1. Thus, each Riordan path is uniquely defined by its list of point types. We now define several operations on the Riordan paths and some useful terminology associated with those operations.

Definition 6. The sum of two Riordan paths M_{m}, M_{n} of order m, n, respectively, is the Riordan path M in which points P_{i} for (1 ≤ i < m) are identical to those of M_{m}, and points P_{(m−1)+i} in M are identical to points P_{i} in M_{n} for 1 ≤ i ≤ n. This sum is denoted M_{m} +M_{n}.

Definition 7. A Riordan path M is splittable if it can be expressed as the sum of two Riordan paths of lesser order.

Definition 8. Let P_{1}, P_{2}, …, P_{n} be the ordered set of points of M, where M ∈ I_{n}, and P_{i} lies adjacently to the right of P_{i−1} for i > 1. The reverse of M, denoted M^{r}, is the ordered set of points Q_{n}, Q_{n−1}, …, Q_{1} with the following property: the steps of M^{r} are defined by (Q_{k−1}, Q_{k}) = (P_{n−k+2}, P_{n−k+1}) and (Q_{k}, Q_{k+1}) = (P_{n−k}, P_{n−k+1}). Equivalently, if P_{n−k+1} is a positive (negative) soft peak or dip, then Q_{k} is a negative (positive) soft peak or dip. Similarly, if P_{n−k+1} is positive (negative) slope, then Q_{k} is a negative (positive) slope. Finally, if P_{n−k+1} is either a hard peak, a hard dip, or a level point, Q_{k} is the same type of point. Note that this results in M^{r} appearing graphically as the mirror image of M.

We will furthermore let I^{r} denote the reverse of a semiorder I, which we will define as being equivalent to its dual; that is, I^{r} = I^{∂} for any I ∈ I_{n}, as defined in [1].

2.2 Construction of the Bijection

We will now define a mapping F_{n} : I_{n} → R_{n}. Our bijection uses the nose and hollow relations on the elements of the semiorder to explicitly construct a Riordan path. We prove the bijectiveness of the mapping inductively, using our operations to construct larger semiorders from smaller ones.

Let I ∈ I_{n}, and let x_{i} denote the ith element of I where 1 < i < n. We will now define the nine possible cases for x_{i}, and, for each, the type of point that x_{i} will correspond to in the Riordan path.

• 2 Hollows - There exist elements a, b such that aHx_{i}, x_{i}Hb, and there exists no element c such that cNx_{i} or x_{i}Nc. In this case, we set the ith point in the path to a hard peak.

• 2 Noses - There exist elements a, b such that aNx_{i}, x_{i}Nb, and there exists no element c such that cHx_{i} or x_{i}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 aHx_{i}, x_{i}Hb, and there exists an element c such that x_{i}Nc (cNx_{i}). In this case, we set the ith point in the path to a positive (negative) soft peak.

Figure 1: The nine possible types of points in a Riordan path. 6 • 2 Noses, 1 Hollow - There exist elements a, b such that aNx_{i}, x_{i}Nb, and there exists

an element c such that x_{i}Hc (cHx_{i}). 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 x_{i}Na and x_{i}Hb (aNx_{i} and bHx_{i}), and there exists no elements c such that cNx_{i} or cHx_{i} (x_{i}Nc or x_{i}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 aNx_{i},bHx_{i},x_{i}Nc,x_{i}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 [6]), as are any two paths with a different list of point types, this gives a welldefined map from I_{n} to R_{n}. Since we showed in part (i) that I_{n} and R_{n} have the same size, we need only show that the map is onto for each value of n to prove each map F_{n} is a bijection. We formalize this here.

Theorem 2. Let n > 2. If F_{n} : I_{n} → R_{n} is onto, then F_{n} is a bijection.

Definition 9. Let x_{i} be the ith element in the trace of an interesting semiorder I ∈ I_{n}.

• We say that x_{i} initiates a nose (hollow) if there exists an element b ∈ I such that x_{i}Nb (x_{i}Hb) and no element a ∈ I such that aNx_{i} (aHx_{i}).

• We say that x_{i} terminates a nose (hollow) if there exists an element a ∈ I such that aNx_{i} (aHx_{i}) and no element b ∈ I such that x_{i}Nb (x_{i}Hb).

• We say that x_{i} continues a nose (hollow) if there exist elements a, b ∈ I such that aNx_{i} (aHx_{i}) and x_{i}Nb (x_{i}Hb).

Given that I is an interesting semiorder, we see that there are a priori 16 types of elements in our semiorder (Each point may be the starting and/or ending point of a nose and/or a hollow, or not), yet we’ve claimed there are only nine types of elements. We now show that there are no other possible cases for the element x_{i} given that I is an interesting semiorder. The following theorem provides a set of restrictions on x_{i} that follow from the properties of I.

Theorem 3. Let I be a semiorder of order n and let x_{i} be the ith element of I. If I is interesting, then x_{i} has the following properties:

(i) If x_{i} initiates a hollow, then x_{i} does not terminate a nose.

(ii) If x_{i} terminates a hollow, then x_{i} does not initiate a nose.

(iii) x_{i} shares a nose/hollow relationship with at least two distinct elements a, b ∈ I.

Proof. Let I ∈ I_{n} and let x_{i} be the ith element of I.

Figure 2: An example of an interesting semiorder I, given in matrix and interval representations, and its corresponding path.

Case i: Suppose x_{i} initiates a hollow. Thus we have that no element hollows x_{i}, which implies that succ(x_{i}) = succ(x_{i+1}). Now suppose x_{i} terminates a nose, implying that x_{i} does not nose any element of I. Thus we have that pred(x_{i}) = pred(x_{i+1}). We have therefore shown that x_{i} and x_{i+1} are redundant elements, a contradiction. We conclude that x_{i} does not terminate a nose.

Case ii: Suppose x_{i} terminates a hollow. Thus we have that x_{i} hollows no element of I, which implies that pred(x_{i}) = pred(x_{i−1}). Now suppose x_{i} initiates a nose, implying that no element of I noses x_{i}. Thus we have that succ(x_{i}) = succ(x_{i−1}). Again, this shows redundancy between elements x_{i} and x_{i−1}, contradicting the fact that I is interesting. We conclude that x_{i} does not initiate a nose.

Case iii: This case follows directly from the arguments in the previous cases.

The following theorems will provide the necessary procedures for building interesting semiorders from those of smaller order based on the differences between their corresponding Riordan paths. Given two Riordan paths of orders m and n, respectively, we may use the machinery provided in Theorem 4 to “glue” these two Riordan paths together at the ends, as well as construct the semiorder associated with our result. Theorem 5 will allow us to take the mirror image of a Riordan path and find its associated semiorder, based on the semiorder of the original. Using Theorem 5 in conjunction with the different cases of Theorem 6 we will be able to take any Riordan path and add a horizontal step anywhere above the axis, and find the semiorder associated with our result. Finally, Theorem 7 will allow us to add an up-step and a down-step to the beginning and end of a Riordan path (respectively) and, again, generate the corresponding semiorder

By generating semiorders from paths of smaller order, we will be able to prove inductively that F_{n} is onto for all n > 2.

Theorem 4. If two Riordan paths M_{m} ∈ R_{m}, M_{n} ∈ R_{n} have preimages under F_{m} and F_{n}, respectively, the Riordan path M_{m} + M_{n} has a preimage under F_{m+n−1}.

Proof. Let M_{m} and M_{n} be the images of two interesting semiorders I_{m}, I_{n} under F_{m}, F_{n}, respectively. We will now construct a semiorder I ∈ I_{m+n−1} and show that its image under F_{m+n−1} is M_{m} + M_{n} by constructing its incidence matrix, which we will denote A. We will denote the incidence matrices of I_{m} and I_{n} as B, C, respectively.

Let x_{m} denote the last element in the trace of I_{m} and let y_{1} denote the first element in the trace of I_{n}. In adding our two Riordan paths together we are essentially combining the points x_{m} and y_{1} into one, with their corresponding element in I being denoted x. Since I_{m} and I_{n} are interesting semiorders, let αHx_{m} and x_{m}Nβ, where α is the pth element in the trace of I_{m} and β is the qth element in the trace of I_{n}. We have the entries of A as follows:

\begin{matrix}I_{m} & 1 \\ 0 & I_{n} \end{matrix}  →  1 2 ⋯ α ⋯ x ⋯ β q ⋯; 1 ; 2 ; ⋮ ; p 0 0 ⋯ 0 1 1 ⋯ 1 1 ⋯; α 0 0 ⋯ 0 0 0 ⋯ 0 1 ⋯; ⋮ 0 0 ⋯ 0 0 0 ⋯ 0 1 ⋯; x 0 0 ⋯ 0 0 0 ⋯ 0 1 ⋯; ⋮  0 ⋯ 0 0 ⋯; β

Figure 3: Constructing the Preimage of M_{m} + M_{n}

A_{i,j} = \{ \begin{matrix}B_{(i,j)}, & if i < p, j ≤ m; \\ C_{(i−m+1,j−m+1)} & if i > m, j ≥ m; \\ 0, & if i > m, j < m; \\ 0, & if p < i ≤ m, j < m + q − 1; \\ 1, & if i < p, j > m; \\ 1, & if p < i ≤ m, j ≥ m + q − 1 \end{matrix}

This procedure simply adds all elements of I_{n} to the predecessor sets of the first p − 1 elements in I_{m}, and adds the last n − q + 1 elements of I_{n} to the predecessor sets of the last m − p + 1 elements of I_{m}. This is demonstrated in Figure 3. Since we are simply adding elements to the predecessor sets of elements from I_{m}, we have that the irredundancy and connectedness of I follow necessarily from those of I_{m} and I_{n}. Thus our resultant semiorder I is interesting.

Since I ∈ I_{m+n−1}, we will now show that F_{m+n−1} maps I to M_{m} + M_{n}. Note that when we restrict A to rows and columns 1, …, m, we obtain the matrix A, and thus the only relationship difference between the elements of I_{m} and their corresponding elements of I is that αHx_{m} in I_{m} and αHβ in I. Similarly, when restricting A to rows and columns m, …, m + n − 1, we obtain the matrix B, and our only difference is that x_{n}Hβ in I_{n} and αHβ in I. Note that α and β are therefore mapped to the same type of point (with reference to Definition 5) as they were in F_{m} and F_{n}, respectively, since α still hollows another element and an element still hollows β. Applying our function F_{m+n−1} to I, we therefore find that the shape of the first m points of our path is equivalent to that of M_{m}. Since noses are preserved by our procedure, x is a hard dip. This implies that x is followed by an up-step, just as is x_{n} in M_{n}. Finally, we find that the shape of the last n points of the path is equivalent to that of M_{n}. We have therefore shown that F_{m+n−1}(I) = M_{m} + M_{n}.

Theorem 5. If M is a Riordan path of order n and has a preimage I under F_{n}, then M^{r} has a preimage under F_{n}, namely I^{r}.

Proof. Let M ∈ R_{n}, let {P_{k}}_{k=1}^{n} be the ordered set of points of M, and suppose F_{n}(I) = M, where I ∈ I_{n}. Let x ∈ I. If aHx for some element a ∈ I, then xHa in I^{r}, since pred(x) in I

Reassigning Noses and Hollows: Specific Cases

Hard Peak  if {p_{i}}_{i=1}^{k}, {q_{i}}_{i=1}^{k} ≠ ∅ → Shift Summary Table
if {p_{i}}_{i=1}^{k} = {q_{i}}_{i=1}^{k} = ∅ → Set x_{0}Hx_{1}.
Positive Soft Peak if {p_{i}}_{i=1}^{k}, {q_{i}}_{i=1}^{k} ≠ ∅ → Shift Summary Table
if {p_{i}}_{i=1}^{k} = {q_{i}}_{i=1}^{k} = ∅ → Set x_{0}Hx_{1}.
Positive Soft Dip {p_{i}}_{i=1}^{k}, {q_{i}}_{i=1}^{k} ≠ ∅  → Shift Summary Table
Positive Slope  {p_{i}}_{i=1}^{k}, {q_{i}}_{i=1}^{k} ≠ ∅  → Shift Summary Table
Hard Dip  Either Case  → Shift Summary Table

is equal to succ(x) in I^{r}. This applies analogously to the cases of aNx, xNa, and xHa in I. Thus if x ∈ I is mapped to a positive (negative) soft peak or dip, then x ∈ I^{r} is mapped to a negative (positive) soft peak or dip. Similarly, if x ∈ I is mapped to a positive (negative) slope, then x ∈ I^{r} is mapped to a negative (positive) slope. If x ∈ I is mapped to either a hard peak, a hard dip, or a level point, x ∈ I^{r} is mapped to the same type of point. Let F_{n}(I^{r}) = M′ and let {Q_{k}}_{k=1}^{n} represent the ordered set of points of M′.

Since the ordering of elements in the trace of I^{r} is reversed with respect to their ordering in the trace of I, we now have that each point Q_{k} of M′ corresponds to that of P_{n−k+1} with respect to the element they represent in I^{r} and I, respectively. Thus we have shown that M′ = M^{r}, and that the preimage of M^{r} under F_{n} is I^{r}.

Theorem 6. Let P_{j} denote the jth point in a Riordan path M ∈ R_{n} where 1 < j < n. Furthermore, let M_{j}^{h} denote the path P_{1}, …, P_{j−1}, P_{a}, P_{b}, P_{j+1}, …, P_{n} where (P_{j−1}, P_{a}) and (P_{b}, P_{j+1}) are the same types of steps as (P_{j−1}, P_{j}) and (P_{j}, P_{j+1}) in M, respectively, and (P_{a}, P_{b}) is a horizontal step. We describe this process as adding a horizontal step to point P_{j}, which is shown graphically in Figures 5 and 6. If M has a preimage under F_{n}, and M_{j}^{h} is a Riordan path, then M_{j}^{h} has a preimage under F_{n+1}.

Shift Summary Table

I  I_{j}^{h}
aHb (a < b < x or x < a < b) aHb
aNb (a < b < x or x < a < b) aNb
p_{1}Hx_{0}
p_{i}Hq_{i} (p_{i} < x < q_{i})  p_{i}Hq_{i−1}
x_{1}Hq_{k}
r_{1}Nx_{0}
r_{i}Ns_{i} (r_{i} < x < s_{i})  r_{i}Ns_{i−1}
x_{1}Ns_{l}

Proof. Let M ∈ R_{n}, P_{j}, and M_{j}^{h} be as defined above, and suppose M has a preimage I under F_{n}. The following notation will be used when applicable in each case: Let x denote the element of I corresponding to P_{j}. Let {p_{i}}_{i=1}^{k} be the possibly empty set of elements preceding x in the trace of I such that p_{i}Hq_{i}, where {q_{i}}_{i=1}^{k} is a set of elements succeeding x in the trace of I. Let {r_{i}}_{i=1}^{l} be the set of elements preceding x in the trace of I such that r_{i}Ns_{i}, where {s_{i}}_{i=1}^{l} is a set of elements succeeding x in the trace of I. Note that in our first four cases, this set is trivially nonempty. Let αHx, xHβ, γNx, xNδ, if such elements exist.

Now, let I_{j}^{h} denote the semiorder in which the first j − 1 elements and the last n − j elements are obtained from their corresponding elements in I. These elements will inherit all nose/hollow relationships from I with the exception of those involving α, β, γ, δ, and x, those of the form p_{i}Hq_{i}, and those of the form r_{i}Ns_{i}. Between these elements we will place two elements x_{0}, x_{1}, in that order.

In each following case we set p_{i}Hq_{i−1}, r_{i}Ns_{i−1} for i > 1, essentially “shifting” our noses and hollows to make room for those of the newly-added point. We will then construct the remaining nose/hollow relationships of I_{j}^{h}, and show that I_{j}^{h} ∈ I_{n} and F_{n}(I_{j}^{h}) = M_{j}^{h}.

Case 1: P_{j} is a hard peak. Let I_{j}^{h} have the following properties: p_{1}Hx_{1}, x_{1}Hβ, αHx_{0}, x_{0}Hq_{k}, r_{1}Nx_{1}, and x_{0}Ns_{l}. If our sets {p_{i}}_{i=1}^{k} is empty, we set x_{0}Hx_{1}. By this construction every element in I_{j}^{h}, x_{0} and x_{1}, has the same number and type of nose/hollow relationships as their corresponding elements of I. Furthermore, with the definition of the nose/hollow relationships of x_{0} and x_{1}, (x_{0}, x_{1}) is now a horizontal step, with x_{0} mapping to a positive soft peak and x_{1} mapping to a negative soft peak. Thus we have shown that if I ∈ I_{n}, then F_{n+1}(I_{j}^{h}) = M_{j}^{h}.

Let A denote the incidence matrix of I. We will investigate the incidence matrix of I, which we will denote A_{j}^{h}, with the purpose of showing that I ∈ I_{n}. A_{j}^{h} is constructed as follows: We start with the matrix A, and duplicate the row and column corresponding to x, placing the copy next to the original. These two duplicate rows and columns are x_{0} and x_{1}. The resulting matrix implies that αHx_{1}, so we add a “1” in the row corresponding to α so that we have αHx_{0}. Now let r_{i} correspond to the z_{i}th row in the matrix for all i. We add enough 1’s in rows z_{i} through z_{i+1} − 1 so that the nose r_{i}Ns_{i} has now become r_{i}Ns_{i−1} and r_{1}Nx_{1}. Note that this furthermore shifts each hollow such that we now have p_{i}Hq_{i−1}. Finally, we add enough 1’s in the row corresponding to x_{0} so that we have x_{0}Ns_{k}. This procedure is exemplified in Figures 4, 5, and 6.

Let a, b ∈ I_{j}^{h} where a immediately precedes b in the trace of I_{j}^{h}. Since p_{1}Hx_{1}, x_{0}Hq_{k}, and the pair x_{0}, x_{1} have different predecessor sets, neither a nor b are the elements x_{0} or x_{1}. Suppose pred(a) = pred(b) and succ(a) = succ(b). Then a does not nose any element, and no element hollows a in I^{a}. These statements are also true in I by our construction of I_{j}^{h}. This implies that pred(a) = pred(b) and succ(a) = succ(b) in I, a contradiction. Thus, I_{j}^{h} is irredundant. We must now verify the connectedness of I_{j}^{h}. By our construction of I_{j}^{h}, no element noses an element adjacent to it in the trace; the noses r_{1}Nx_{1}, x_{0}Ns_{l}, and r_{i}Ns_{i−1} are all between non-adjacent elements. Since all other nose relationships were inherited from I, this shows that I_{j}^{h} is connected. We conclude that I_{j}^{h} ∈ I_{n+1}.

Case 2: P_{j} is a positive soft peak. Let I_{j}^{h} have the following properties: p_{1}Hx_{1}, x_{1}Hβ, αHx_{0}, x_{0}Hq_{k}, r_{1}Nx_{1}, x_{1}Nδ, and x_{0}Ns_{k}. If {p_{i}}_{i=1}^{k} is empty, then set x_{0}Hx_{1}. Analogously

1 α/r_{1} p_{1} r_{2} p_{2}/r_{3} x q_{1}/s_{1} q_{2}/s_{2} β/s_{3} 10
1 0 0 0 1  1 1 1  1  1 1
α/r_{1} 0 0 0 0  0 0 1  1  1 1
p_{1} 0 0 0 0  0 0 0  1  1 1
r_{2} 0 0 0 0  0 0 0  1  1 1
p_{2}/r_{3} 0 0 0 0  0 0 0  0  1 1
x 0 0 0 0  0 0 0  0  0 1
q_{1}/s_{1} 0 0 0 0  0 0 0  0  0 1
q_{2}/s_{2} 0 0 0 0  0 0 0  0  0 1
β/s_{3} 0 0 0 0  0 0 0  0  0 0
10 0 0 0 0  0 0 0  0  0 0

The incidence matrix of a semiorder in I_{10}. The associated Riordan path is shown in

Figure 5.

1 α/r_{1} p_{1} r_{2} p_{2}/r_{3} x_{0} x_{1} q_{1}/s_{1} q_{2}/s_{2} β/s_{3} 10
1 0 0 0 1  1  1 1  1  1  1 1
α/r_{1} 0 0 0 0  0  0 0  1  1  1 1
p_{1} 0 0 0 0  0  0 0  0  1  1 1
r_{2} 0 0 0 0  0  0 0  0  1  1 1
p_{2}/r_{3} 0 0 0 0  0  0 0  0  0  1 1
x_{0} 0 0 0 0  0  0 0  0  0  0 1
x_{1} 0 0 0 0  0  0 0  0  0  0 1
q_{1}/s_{1} 0 0 0 0  0  0 0  0  0  0 1
q_{2}/s_{2} 0 0 0 0  0  0 0  0  0  0 1
β/s_{3} 0 0 0 0  0  0 0  0  0  0 0
10 0 0 0 0  0  0 0  0  0  0 0

The incidence matrix after duplication.

1 α/r_{1} p_{1} r_{2} p_{2}/r_{3} x_{0} x_{1} q_{1}/s_{1} q_{2}/s_{2} β/s_{3} 10
1 0 0 0 1  1  1 1  1  1  1 1
α/r_{1} 0 0 0 0  0  0 1  1  1  1 1
p_{1} 0 0 0 0  0  0 0  1  1  1 1
r_{2} 0 0 0 0  0  0 0  1  1  1 1
p_{2}/r_{3} 0 0 0 0  0  0 0  0  1  1 1
x_{0} 0 0 0 0  0  0 0  0  0  1 1
x_{1} 0 0 0 0  0  0 0  0  0  0 1
q_{1}/s_{1} 0 0 0 0  0  0 0  0  0  0 1
q_{2}/s_{2} 0 0 0 0  0  0 0  0  0  0 1
β/s_{3} 0 0 0 0  0  0 0  0  0  0 0
10 0 0 0 0  0  0 0  0  0  0 0

The incidence matrix after shifting rows α through x_{0}. The associated Riordan path is shown in in Figure 6.

Figure 4: Constructing the Incidence Matrix A_{j}^{h} from A with j = 6 to our previous case, this construction implies that if I_{j}^{h} ∈ I_{n}, then F_{n+1}(I_{j}^{h}) = M_{j}^{h}.

Furthermore, the construction of the incidence matrix of I_{j}^{h} is identical to that of the case of a hard peak. In duplicating the row corresponding to P_{j}, the element x_{1} is given the property x_{1}Nδ, as required by our construction of I_{j}^{h}. Since the procedure for constructing the incidence matrix of I_{j}^{h} is the same for both the case of the hard peak and the soft peak, we conclude that I_{j}^{h} is an interesting semiorder in the case of a soft peak as well.

Case 3: P_{j} is a positive soft dip. Let I_{j}^{h} have the following properties: p_{1}Hx_{0}, x_{0}Hq_{k}, x_{1}Hβ, r_{1}Nx_{1}, x_{1}N_{δ}, γNx_{0}, and x_{0}Ns_{k}. Similar to the previous cases, we have that f I_{j}^{h} ∈ I_{n}, then F_{n+1}(I_{j}^{h}) = M_{j}^{h}.

In constructing our matrix, we proceed identically to the case of the hard peak with one exception: rather than begin adding 1’s with the row corresponding to α (this element does not exist in this case), we add a ”1” to the row corresponding to γ after duplication so that γNx_{0}. We then proceed exactly as in the case of a hard peak. Analogously, our resulting matrix represents an interesting semiorder, and thus we have F_{n+1}(I_{j}^{h}) = M_{j}^{h}.

Case 4: P_{j} is a positive slope. Let I_{j}^{h} have the following properties: p_{1}Hx_{0}, x_{0}Hq_{k}, x_{0}Ns_{k}, r_{1}Nx_{1}, x_{1}Nδ, and x_{1}Hβ. Similar to the previous cases, we have that f I_{j}^{h} ∈ I_{n}, then F_{n+1}(I_{j}^{h}) = M_{j}^{h}.

Again, we construct our matrix in a manner identical to that of the case of the hard peak, with the following exception: Since α does not exist in this case, we simply ignore this element and begin adding 1’s wherever necessary. This results in a matrix representing an interesting semiorder, proving that F_{n+1}(I_{j}^{h}) = M_{j}^{h} for this case as well.

Case 5: P_{j} is a hard dip.

Lemma. Let P be a hard dip of a Riordan path M with preimage I under F_{n}, let n_{i} be the number of noses initiated prior to P, and let n_{t} be the number of noses terminated prior to P. The height of P is equal to n_{i} − n_{t} − 1.

Proof. Let P_{i} denote the ith point in M ∈ R_{n}, let 1 < k < n, let u denote the number of up-steps prior to P_{k}, let d denote the number of down-steps prior to P_{k}, let h denote the number of hard peaks prior to P_{k}, and finally let n_{i} and n_{t} denote the number of noses initiated and terminated prior to P_{k}, respecitvely.

For i > 1, each point P_{i} that initiates a nose is preceded by an up-step, and each point that terminates a nose precedes a downstep, which follows directly from our definition of F_{n}. Thus we can associate exactly one up-step to each nose initiated after P_{1}, and exactly one down-step to each nose terminated.

Each up-step that is not part of a hard peak immediately precedes a point that initiates a nose, and each down-step that is not part of a hard peak is immediately preceded by a point that terminates a nose. A hard peak neither initiates nor terminates a nose, and contains both an up-step and a down-step. We now note that P_{1} initiates a nose but is not preceded by an up-step.

Thus we arrive at the following two equations: n_{i} = u − h + 1 (our “+1” comes from the fact that we do not associate P_{1} with an up-step) and n_{t} = d − h. Combining these, we get that n_{i} − n_{t} = 1 + u − d, or equivalently, n_{i} − n_{t} − 1 = u − d. We conclude that the height of P_{k} is equal to n_{i} − n_{t} − 1.

In all previous cases, the fact that M_{j}^{h} ∈ R_{n+1} has been trivial. This case, however, provides the possibility of a horizontal step being added on the horizontal axis, which would result in M_{j}^{h} not being a Riordan path. We will thus require that P_{j} is of height greater than 0. Equivalently, this means that there are at least two unterminated noses initiated prior to the point P_{j}, by the previous lemma. One of these noses is initiated by the point corresponding to γ, and the rest ensure that our set {r_{i}}_{i=1}^{l} is non-empty.

For this case, we let I_{j}^{h} have the following properties: γNx_{0}, x_{0}Ns_{k}, r_{1}Nx_{1}, and x_{1}Nδ. We add 1’s to our incidence matrix just as in previous cases, starting with the row corresponding to γ and ending with that corresponding to x_{0}. Since there are no noses between adjacent points, connectedness is guaranteed, and irredundancy is guaranteed by an argument analogous to that of each previous case.

Finally, we consider the cases of a level point, a negative soft peak, and negative soft dip, and a negative slope. If P_{j} is a negative soft peak, negative soft dip, or negative slope, we have that M_{j}^{h} has a preimage under F_{n+1} by Theorem 5. If P_{j} is a level point, then adding a horizontal step to the point P_{j} is equivalent to adding a horizontal step to the point P_{j−1}. Continuing as necessary, we find that adding a horizontal step to P_{j} is equivalent to adding a horizontal step to P_{j−i} for some 1 < i < j − 2, where P_{j−i} is not a level point. Since we have proven that F_{n+1}(I_{j}^{h}) = M_{j}^{h} for every other case, we have therefore proven it for this case as well.

Theorem 7. Let M ∈ R_{n}, and let P_{1}, P_{2}, …, P_{n} denote the ordered set of points in M, where P_{1} is the left-most point. Now let M^{a} denote the path consisting of the ordered points x, P_{1}, P_{2}, …, P_{n}, y, where P_{i} in M and (x, P_{1}), (P_{n}, y) represent an up-step and a down-step, respectively. If M has a preimage in F_{n}, then M^{a} has a preimage under F_{n+2}.

Proof. Let I be a semiorder such that F_{n}(I) = M, and let i_{j} denote the jth element in the trace of I for 1 ≤ j ≤ n. Furthermore, let {p_{i}}_{i=1}^{k}, {q_{i}}_{i=1}^{k} denote the set of elements of I such that p_{i}Hq_{i}, and let {r_{i}}_{i=1}^{l},{s_{i}}_{i=1}^{l} denote the set of elements of I such that r_{i}Ns_{i}. We will now define a semiorder I^{a} as the set i_{x}, i_{1}, …, i_{n}, i_{y} with noses r_{i}Ns_{i+1}, i_{x}Ns_{1}, r_{l}Ni_{y}, and hollows p_{i}Hq_{i+1}, i_{x}Hq_{1}, and p_{k}Hi_{y}. Note that each element i_{1}, …, i_{n} has the same number and type of nose/hollow relationships in I^{a} as in I.

We will first show that I^{a} is an interesting semiorder. The connectedness of I^{a} follows trivially from the connectedness of I, so we will focus on proving irredundancy.

Let a, b ∈ I^{a} where a immediately precedes b in the trace of I^{a}. Suppose pred(a) = pred(b) and succ(a) = succ(b). Then a does not nose any element, and no element hollows a in I^{a}. These statements are also true in I by our construction of I^{a}. This implies that pred(a) = pred(b) and succ(a) = succ(b) in I, a contradiction. We conclude that I^{a} ∈ I_{n+2}.

We will now show that F_{n+2}(I^{a}) = M^{a}. By our construction of I^{a}, the elements i_{2}, …, i_{n−1} map to points P_{2}, …, P_{n−2} under F_{n+2}, respectively. The points i_{1} and i_{n} now map to positive and negative slopes, respectively, since i_{1} necessarily hollows and noses two elements in I^{a}, and i_{n} is necessarily nosed and hollowed by two elements in I^{a}. This furthermore shows that (x, P_{1}) is an up-step and (P_{n}, y) is a downstep. Finally, due to the noses Figure 5: An example of a Motzkin path M.

Figure 6: The Motzkin path M_{5}^{h} and hollows constructed for elements i_{x}, i_{y}, we have that they properly correspond to the first and last elements of a Riordan path, namely M^{a}.

Theorem 8. The function F_{n} is a bijection for all n > 2.

Proof. We will prove by induction on n that F_{n} is onto, with the case n = 3 shown in Figure 7, and case n = 4 given by Theorem 6 and the case n = 3. By Theorem 2, this will show that F_{n} is a bijection for all n > 2.

Let n ≥ 5 and assume that F_{k} is a bijection for all 2 < k < n. Suppose M has a horizontal step and let M′ denote the Riordan path of length n − 1 with this horizontal step deleted. By our inductive hypothesis, this shows that M′ has a preimage under F_{n−1}. By Theorem 6, M has a preimage under F_{n}.

Now suppose that M has no horizontal steps, and suppose that there exists a point P_{i} in M such that P_{i} is on the horizontal axis and 1 < i < n. Let M_{1}, M_{2} denote the Riordan paths consisting of points P_{1}, …, P_{i} and P_{i}, …, P_{n}, respectively. We have that M_{1} + M_{2} = M. By our inductive hypothesis and Theorem 4, we have that M has a preimage under F_{n}.

Finally, suppose that M has no horizontal steps and that there are no points other than P_{1} and P_{n} on the horizontal axis. Now let M′′ denote the path with the first and last steps deleted. Since there are no horizontal steps and no points on the horizontal axis in M, this implies that M′′ has no points below the axis and no horizontal steps on the axis, i.e., it is a Riordan path. By our inductive hypothesis and Theorem 7, M has a preimage under F_{n}.

Since these cover every possible case for M, we have shown that F_{n} is onto. By Theorem 2, F_{n} is a bijection for all n > 2.

Figure 7: The Riordan path of base case n = 3, as well as its interval representation.

3 Acknowledgement

We are thankful to Jean-Paul Doignon for many helpful comments in the preparation of this manuscript. We would also like to thank the referee for their comments regarding presentation and clarity.

References

[1] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge, 1990.

[2] F. Bernhart, Catalan, Motzkin, and Riordan numbers, Discrete Math. 204 (1999), 73– 112.

[3] P. Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), 383–426.

[4] W. Chen, E. Deng, and L. Yang, Riordan paths and derangements,

   http://arxiv.org/abs/math/0602298.

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

   http://research.att.com/∼njas/sequences.

[6] M. Pirlot, Minimal representation of a semiorder, Theory and Decision 28 (1990), 109– 141.

[7] M. Pirlot, Synthetic description of a semiorder, Discrete Math. 31 (1991), 299–308.

[8] R. Donaghey, and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Ser. A 23 (1977), 291–301.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 06A07. Keywords: Riordan numbers, interval orders, semiorders, lattice paths.

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

Received February 14 2007; revised version received July 18 2007. Published in Journal of Integer Sequences, July 23 2007.

Return to Journal of Integer Sequences home page.