On the Number of Fixed-Length Semiorders

Yangzhou Hu^{1} Department of Mathematics Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139 United States

                   yangzhou@mit.edu
                 yangzhou13@gmail.com

Abstract

A semiorder is a partially ordered set P with two certain forbidden induced subposets. This paper establishes a bijection between n-element semiorders of length H and (n + 1)-node ordered trees of height H + 1. This bijection preserves not only the number of elements, but also much additional structure. Based on this correspondence, we calculate the generating functions and explicit formulas for the numbers of labeled and unlabeled n-element semiorders of length H. We also prove several concise recurrence relations and provide combinatorial proofs for special cases of the explicit formulas.

1 Introduction and Main Theorem

We will use partially ordered set (poset) notation and terminology from [5, Ch. 3]. A semiorder is a poset without the following induced subposets:

• (2 + 2): four distinct elements x, y, z, w, such that x > y, z > w, and other pairs are incomparable; • (3 + 1): four distinct elements x, y, z, w, such that x > y > z, and other pairs are

1The author’s research was part of an undergraduate research project at M.I.T. under the supervision of Richard Stanley.

incomparable.

[figure: •; •; •; •; y; x; w; z; (2 + 2)-structure; •; •; •; •; z; y; x; w; (3 + 1)-structure; •; •; ← first level; •; •; •; ← second level; (a) A semiorder with; 5 elements and length 1]

In other words, semiorders are (2 + 2)-free and (3 + 1)-free posets. Every semiorder can also be regarded as a partial ordering P of a subset of ℝ defined by x < y in P if x < y − 1 in ℝ. The length H of a semiorder is the length of a longest chain. Every semiorder R with n elements, up to isomorphism, can be uniquely represented as an integer vector ρ(R) = (r_{1}, r_{2}, …, r_{n}), where r_{i} represents the number of elements smaller than the i^{th} element, and r_{1} ≥ r_{2} ≥ ⋯ ≥ r_{n} ≥ 0, r_{i} ≤ n − i, for all 1 ≤ i ≤ n. For instance, the above graph (a) presents a semiorder R with 5 elements, length 1, and vector ρ(R) = (3, 2, 0, 0, 0). For further basic information on semiorders, see [4].

There is much interest in enumerating the number of posets with certain properties. For example, Bousquet-Mélou et al. enumerated the number of (2 + 2)-free posets [1]. It is a classical result of Wine and Freund [6] that the number of nonisomorphic n-element semiorders is the Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}, while Chandon, Lemaire, and Pouget [3] showed (in an equivalent form) that if f(n) is the number of n-element labeled semiorders (or semiorders on an n-element set), then ∑_{n≥0} f(n)\frac{x^{n}}{n!} = ∑_{n≥0} C_{n}(1 − e^{−x})^{n}. For a general principle implying this result, see Lemma 13. In this paper, we deal with semiorders of length at most H. That is, we enumerate the number of posets which are (2 + 2)-free, (3 + 1)-free, and of length at most H. We carry out the enumeration by establishing a bijection between semiorders and ordered trees of a fixed height.

An ordered tree is a rooted tree that has been embedded in the plane so that the relative order of subtrees at each node is part of its structure. The height H of an ordered tree is the number of edges in a chain of maximum length. The following graph (b) shows an ordered tree with 6 nodes and height 2.

[figure: •; •; •; •; •; •; •; •; •; •; •; (c) A Dyck path with; semilength 5 and height 2; •; ← depth 0; •; A; •; ← depth 1; •; B; •; •; ← depth 2; (b) An ordered tree with; 6 nodes and height 2]

A Dyck path of semilength n is a lattice path in the Euclidean plane from (0, 0) to (2n, 0) whose steps are either (1, 1) or (1, −1) and the path never goes below the x-axis. The height H of a Dyck path is the maximal y-coordinate among all points on the path. The above graph (c) shows a Dyck path with semilength 5 and height 2.

It is well-known that there is a one-to-one correspondence between (i) ordered trees with n + 1 nodes and height H and (ii) Dyck paths with semilength n and height H. This paper establishes a bijection between n-element semiorders of length H and (n + 1)-node ordered trees of height H + 1. Thus these semiorders simultaneously correspond to Dyck paths of semilength n and height H + 1.

Theorem 1 (Main Theorem). For n ≥ 1 and H ≥ 0, the number of nonisomorphic nelement unlabeled semiorders of length H is equal to the number of (n+1)-node ordered trees of height H +1, which is also equal to the number of Dyck paths with semilength n and height H + 1.

Section 2 gives a recurrence proof and a bijective proof for Theorem 1. Section 3 calculates the generating functions and explicit formulas for the number of unlabeled as well as labeled semiorders with fixed lengths. Section 4 proves some concise recurrence relations, and Section 5 shows explicit formulas for the number of semiorders of certain lengths H, and provides simple bijective proofs for these formulas.

2 Proof of Main Theorem 1

Before proving Theorem 1, we first define some terminology that is used later in the proof.

Definition 2. A node A in an ordered tree has depth i if the distance from node A to the root is i. In particular, the depth of the root is 0.

In this paper we regard the root as the uppermost node, and all other nodes are below the root. We say node B is attached to node A if node B has depth i + 1 and node A has depth i, and these two nodes are adjacent. Refer to graph (b) as an example.

Definition 3. An element a of a semiorder is on the i^{th} level (i ≥ 1) if i is the largest integer for which there exist i−1 elements a_{1}, a_{2}, …, a_{i−1} satisfying a_{1} > a_{2} > ⋯ > a_{i−1} > a. Refer to graph (a) as an example.

Proposition 4. For a length H semiorder, and for 1 ≤ i ≤ H, there is at least one element on the i^{th} level that is larger than all elements on the (i + 1)^{th} level.

Proof. Suppose that there does not exist an element on the i^{th} level that is larger than all elements on the (i+1)^{th} level. Since every element on the (i+1)^{th} level must be smaller than at least one element on the i^{th} level, there must exist two elements a and c on the (i + 1)^{th} level which are smaller than two distinct elements b and d on the i^{th} level, respectively, and b is not larger than c, while d is not larger than a. Then {b > a, d > c} forms a (2 + 2)- structure, a contradiction. Therefore, at least one element on the i^{th} level is larger than all elements on the (i + 1)^{th} level.

Proposition 5. For a length H semiorder, and for 1 ≤ i < j ≤ H + 1, j − i ≥ 2, every element on the i^{th} level is larger than all elements on the j^{th} level.

Proof. Assume to the contrary that there exist an element b on the i^{th} level and an element a on the j^{th} level such that b is not larger than a. By Definition 3, there exist j − 1 elements a_{1}, a_{2}, …, a_{j−1}, such that a_{1} > a_{2} > ⋯ > a_{j−1} > a, and then a_{j−2} and a_{j−1} should be on the (j − 2)^{th} and (j − 1)^{th} level, respectively. Since element b is on the i^{th} level, and j − i ≥ 2, element b cannot be smaller than any of a_{j−2}, a_{j−1}, or a. In addition, since b is not larger than a and a_{j−2} > a_{j−1} > a, b is not comparable with any of a_{j−2}, a_{j−1} or a. Hence, {a_{j−2} > a_{j−1} > a, b} forms a (3 + 1)-structure, a contradiction. Therefore every element on the i^{th} level should be larger than all elements on the j^{th} level, for j − i ≥ 2.

We are now ready to prove the Main Theorem 1. We give two proofs here: one considers the recurrence formulas of the two numbers in the theorem, and the other directly establishes a bijection between semiorders and ordered trees.

2.1 Recurrence proof

Let t(n, h, k) denote the number of (n + 1)-node ordered trees of height h + 1, for which exactly k nodes have depth h + 1, 1 ≤ k ≤ n. Let f(n, h, k) be the number of n-element semiorders of length h, and exactly k elements are on the last level. We show that t(n, h, k) and f(n, h, k) have the same initial value and recurrence formula in the following lemmas, and thus they are equal.

Lemma 6. For h ≥ 1, we have

t(n, h, k) = ∑_{m=1}^{n−k} \binom{m + k − 1}{m − 1} · t(n − k, h − 1, m).  (1)

Proof. Say we have an (n − k + 1)-node ordered tree of height h, and assume that exactly m nodes have depth h, 1 ≤ m ≤ n − k. Consider adding k nodes to the tree to get a new tree with n + 1 nodes and height h + 1, and the newly added nodes are exactly the set of nodes of depth h + 1. Thus we need to attach the k new nodes to the m nodes of depth h, and every new node is uniquely attached to one node. Let the m nodes be A_{1}, A_{2}, …, A_{m}, and the number of new nodes attached to A_{i} be r_{i}, 1 ≤ i ≤ m. Then we have r_{1} + r_{2} + ⋯ + r_{m} = k, r_{i} ≥ 0, 1 ≤ i ≤ m.

The number of integer solutions to the above equation is \binom{m+k−1}{m−1}. Therefore, we have \binom{m+k−1}{m−1} ways to add the k nodes. Summing up all possible m’s, we obtain

t(n, h, k) = ∑_{m=1}^{n−k} \binom{m + k − 1}{m − 1} · t(n − k, h − 1, m).

Lemma 7. For h ≥ 1, we have

f(n, h, k) = ∑_{m=1}^{n−k} \binom{m + k − 1}{m − 1} · f(n − k, h − 1, m).  (2)

Proof. We say that an element of a semiorder is good if the element is on the last level of the semiorder. Say we have an (n − k)-element semiorder S of length h − 1 and m good elements, 1 ≤ m ≤ n − k. Consider adding k elements to S to get a new semiorder S′ with n elements and length h, and the newly added elements are exactly the set of good elements of S′. Call the original m good elements a_{1}, a_{2}, …, a_{m}, and the k new elements b_{1}, b_{2}, …, b_{k}. Then in the semiorder S′, we have that a_{1}, a_{2}, …, a_{m} are the only elements on the h^{th} level, and b_{1}, b_{2}, …, b_{k} are the only elements on the (h + 1)^{th} level.

If we remove all elements on the first h−1 levels of S′, then we get a length one semiorder P with m + k elements, and there are exactly m elements on the upper level and k elements on the lower level. On the other hand, given a semiorder S and a semiorder P as above, we can uniquely determine the semiorder S′, because based on Proposition 5, the k elements on the (h + 1)^{th} level of S′ must be smaller than all elements on the i^{th} level of S′, for 1 ≤ i ≤ h − 1. Therefore, the semiorder P uniquely determines the way to add the k new elements.

Let P with ρ(P) = (p_{1}, p_{2}, …, p_{m+k}) represent one such semiorder. Then we have

\begin{cases}k = p_{1} ≥ p_{2} ≥ ⋯ ≥ p_{m} ≥ 0; \\ p_{m+1} = p_{m+2} = ⋯ = p_{m+k} = 0. \end{cases}  (3)

Notice that {p_{2}, p_{3}, …, p_{m}} is an (m−1)-element multiset with elements from {0, 1, …, k}, and thus we have \binom{k+1+m−1−1}{m−1} = \binom{m+k−1}{m−1} such multisets. Therefore, there are \binom{m+k−1}{m−1} possible semiorder P ’s. Summing up all possible m’s, we have

f(n, h, k) = ∑_{m=1}^{n−k} \binom{m + k − 1}{m − 1} · f(n − k, h − 1, m).

Proof of the Main Theorem 1. For h = 0, the (n+1)-element ordered tree of height h+1 = 1 can only be the tree with n nodes adjacent to the root; meanwhile, the n-element semiorder of length 0 can only be the one with n elements and any two of the elements are incomparable. As a result, we have

t(n, 0, k) = f(n, 0, k) = \begin{cases}1, & if n = k; \\ 0, & if n ≠ k. \end{cases}

For h ≥ 1, by Lemma 6 and 7, t(n, h, k) and f(n, h, k) have the same recurrence formula. Therefore t(n, h, k) = f(n, h, k) for every n ≥ 1, h ≥ 0, and 1 ≤ k ≤ n. Summing on k completes the proof of Theorem 1.

2.2 Bijective proof

Recall that an element of a semiorder is good if it is on the last level of the semiorder. Based on the idea in the recurrence proof, we can construct a one-to-one map from (n + 1)-element ordered trees of height H + 1 with k nodes of depth H + 1 to n-element semiorders of length H with k good elements.

For an ordered tree with n + 1 nodes and height H + 1, let us assume that there are x_{i} nodes of depth i, 0 ≤ i ≤ H + 1. Since the root is the only node of depth 0, we have

∑_{i=1}^{H+1} x_{i} = n.  (4)

Let s_{j}^{i} denote the number of nodes of depth i that are adjacent to the j^{th} node of depth i − 1, 1 ≤ j ≤ x_{i−1}, 1 ≤ i ≤ H + 1. Since every node of depth i should be adjacent to exactly one node of depth i − 1, we must have

∑_{j=1}^{x_{i−1}} s_{j}^{i} = x_{i}.  (5)

Let u_{j}^{i} = ∑_{k=j}^{x_{i−1}} s_{k}^{i}, 1 ≤ j ≤ x_{i−1}, 1 ≤ i ≤ H + 1. Then u_{1}^{i} ≥ u_{2}^{i} ≥ ⋯ ≥ u_{x_{i−1}}^{i}. Let y_{i} = ∑_{k=1}^{i} x_{k}, 1 ≤ i ≤ H + 1, and y_{0} = 0. We now define R^{i} by induction, and let the number of entries in R^{i} be y_{i}.

Set R^{1} = (0, 0, …, 0), in which there are x_{1} = y_{1} zeros. Assume R^{i} = (r_{1}^{i}, r_{2}^{i}, …, r_{y_{i}}^{i}), 1 ≤ i ≤ H, and let

R^{i+1} = (r_{1}^{i}+x_{i+1}, r_{2}^{i}+x_{i+1}, …, r_{y_{i−1}}^{i}+x_{i+1}, r_{y_{i−1}+1}^{i}+u_{1}^{i+1}, r_{y_{i−1}+2}^{i}+u_{2}^{i+1}, …, r_{y_{i−1}+x_{i}}^{i}+u_{x_{i}}^{i+1}, 0, 0, …, 0)

in which there are x_{i+1} zeros, and thus R^{i+1} has y_{i−1} + x_{i} + x_{i+1} = y_{i+1} entries.

Theorem 8. The vector R^{H+1} represents an n-element semiorder of length H with x_{H+1} good elements. This gives a bijective map from (n + 1)-node ordered trees of height H + 1 to n-element semiorders of length H.

Since this map is naturally derived from the recurrence proof, we do not give a rigorous proof on why the map is valid and why it is a bijection. The main idea here is to map an ordered tree of height H + 1 to a semiorder with H + 1 levels, where the number of elements on the i^{th} level of the semiorder is equal to the number of nodes of depth i in the tree, 1 ≤ i ≤ H + 1. We get a bijection between (a) the connections between nodes of depths i and i+1 in the tree, and (b) the set of ordered pairs between elements on levels i and i+1 in the semiorder, 1 ≤ i ≤ H. This bijection preserves not only the number of elements but also much additional structure. It presents an effective way to connect semiorders and ordered trees, as well as Dyck paths. In order to illustrate the bijection more clearly, we show by an example how the map works.

Example 9. Assume we have the following ordered tree:

[figure: •; •; •; •; •; •; •; •; •; •]

Here the number of nodes is 10 and height is 4. We have (x_{1}, x_{2}, x_{3}, x_{4}) = (2, 3, 3, 1). So the tree should correspond to a semiorder with 9 elements, length 3, and the number of elements of each depth is given by (2, 3, 3, 1). Write s^{i} = (s_{1}^{i}, s_{2}^{i}, …, s_{x_{i−1}}^{i}) and u^{i} = (u_{1}^{i}, u_{2}^{i}, …, u_{x_{i−1}}^{i}). Then the vectors representing the connections between two adjacent depth-levels in the ordered tree are

s^{1} = (2), s^{2} = (1, 2), s^{3} = (2, 0, 1), s^{4} = (0, 0, 1).

We transform these vectors into vectors that can represent the set of ordered pairs between two adjacent levels of the semiorder. These vectors are

u^{1} = (2), u^{2} = (3, 2), u^{3} = (3, 1, 1), u^{4} = (1, 1, 1).

Now let us construct R^{i}, 1 ≤ i ≤ 4:

R^{1} = (0, 0), R^{2} = (3, 2, 0, 0, 0), R^{3} = (6, 5, 3, 1, 1, 0, 0, 0), R^{4} = (7, 6, 4, 2, 2, 1, 1, 1, 0).

In fact, R^{i} depicts the semiorder with only the first i levels, 1 ≤ i ≤ 4, and R^{4} is the final semiorder we desired. Its Hasse diagram is as follows:

[figure: •; •; •; •; •; •; •; •; •]

The inverse map can be done by reversing the steps.

3 Generating Functions and Explicit Formulas

3.1 On unlabeled semiorders

Let f_{h}^{n} denote the number of nonisomorphic unlabeled semiorders with n elements and length h, and f_{≤h}^{n} denote the number of nonisomorphic unlabeled semiorders with n elements and length at most h, so f_{h}^{n} = f_{≤h}^{n}−f_{≤(h−1)}^{n}. Let F_{h}(x) = ∑_{n=0}^{∞} f_{h}^{n}x^{n}, and F_{≤h}(x) = ∑_{n=0}^{∞} f_{≤h}^{n}x^{n}.

De Bruijn, Knuth, and Rice [2] calculated the generating function for the number of fixed-height ordered trees in 1972. Based on this generating function and Theorem 1, we have the following corollary.

Corollary 10. For h ≥ 0,

• F_{h}(x) = ∑_{n=0}^{∞} f_{h}^{n}x^{n} = \frac{x^{h+1}}{p_{h+1}(x)p_{h}(x)}  (6)

• F_{≤h}(x) = ∑_{n=0}^{∞} f_{≤h}^{n}x^{n} = \frac{p_{h}(x)}{p_{h+1}(x)}  (7)

where

p_{0}(x) = 1, p_{1}(x) = 1 − x, p_{h+1}(x) = p_{h}(x) − x · p_{h−1}(x).

De Bruijn, Knuth, and Rice [2] also found the explicit formulas for the number of fixedheight ordered trees. Based on their results and Theorem 1, we have the following corollary:

Corollary 11. f_{≤h}^{1} = f_{≤h}^{0} = 1. For n ≥ 2, h ≥ 0, we have

f_{≤h}^{n} = (h + 3)^{−1} ∑_{1≤j≤ \frac{h+2}{2}} 4^{n+1} sin^{2} (\frac{jπ}{h + 3}) cos^{2n} (\frac{jπ}{h + 3}) .  (8)

3.2 On labeled semiorders

Let g_{h}^{n} denote the number of nonisomorphic labeled semiorders with n elements and length h, and g_{≤h}^{n} denote the number of nonisomorphic labeled semiorders with n elements and length at most h. Thus g_{h}^{n} = g_{≤h}^{n} − g_{≤(h−1)}^{n}. Let G_{h} = ∑_{n=0}^{∞} g_{h}^{n} \frac{x^{n}}{n!} and G_{≤h} = ∑_{n=0}^{∞} g_{≤h}^{n} \frac{x^{n}}{n!} .

We obtain the exponential generating function G_{h} from the ordinary generating function F_{h} by the following lemma, which is due to Zhang [7]. We first define equivalence of elements and then state the lemma.

Definition 12. Two elements p and p′ of a poset P are equivalent if

p′ < q ⇔ p < q, for all q ∈ P

and

p′ > q ⇔ p > q, for all q ∈ P.

Lemma 13. Define the following two operations on an unlabeled poset P.

• The expansion of P at p ∈ P is obtained from P by adjoining a new element p′ such that p and p′ are equivalent.

• The contraction c(P) of P is a poset c(P) obtained from P by replacing every equivalence class of elements with a single element. Call a poset P a seed if P = c(P). Call a seed P rigid if P has no nontrivial automorphisms.

Let C be a family of unlabeled posets such that C is closed under expansion and contraction, and all seeds in C are rigid. Let F (x) = ∑_{P ∈C} x^{#P} and G(x) = ∑_{P ∈C} D_{p} \frac{x^{#P}}{(#P)!}, where #P is the number of elements in poset P and D_{p} is the number of ways to label the elements of P up to isomorphism, i.e. D_{p} = \frac{#P}{#(aut P)}, where aut P is the automorphism group of P. Then G(x) = F (1 − e^{−x}).

The class of semiorders of length h is closed under expansion and contraction. Zhang has observed that all (2 + 2)-free seeds are rigid. Since semiorders are (2 + 2)-free, all seeds of semiorders are rigid. As a result, Lemma 13 implies the following corollary.

Corollary 14. For h ≥ 0,

G_{h}(x) = F_{h}(1 − e^{−x}) = \frac{(1 − e^{−x})^{h+1}}{p_{h+1}(1 − e^{−x})p_{h}(1 − e^{−x})}  (9)

and

G_{≤h}(x) = F_{≤h}(1 − e^{−x}) = F_{≤h}(1 − e^{−x}) = \frac{p_{h}(1 − e^{−x})}{p_{h+1}(1 − e^{−x})}.  (10)

4 Recurrence Relations

The generating functions and explicit formulas for the number of semiorders of fixed length are complicated, but there are some concise recurrence relations underneath. We will discuss two useful recurrence formulas in this section. The first recurrence formula (11) is a standard result that is known for ordered trees [2, p.17], but only a proof using generating functions was given, while the second recurrence formula (12) is not obvious for ordered trees. We will provide concise combinatorial proofs for both formulas. In this way, we can better understand the relations between fixed-length semiorders with different numbers of elements.

4.1 Recurrence formula 1

Theorem 15. For n ≥ 2 and h ≥ 1,

f_{≤h}^{n} = ∑_{t=0}^{n−1} f_{≤h}^{t}f_{≤h−1}^{n−1−t},  (11)

where f_{≤h}^{0} = 1.

Proof. Let us prove this theorem by first defining the relative positions of elements on the same level of a semiorder.

Definition 16. For elements a and b on the same level of a semiorder S, we say that element b is to the right of element a if b is smaller than more elements than a is, or b and a are smaller than the same number of elements while b is larger than fewer elements than a is.

Remark 17. The above definition is unique up to isomorphism. In fact, if semiorder S has n elements and say the integer vector corresponding to semiorder S, as discussed in Section 1, is (r_{1}, r_{2}, …, r_{n}), then element b is to the right of element a if b corresponds to r_{j}, while a corresponds to r_{i}, i < j. For detailed basic properties of semiorders, see [4].

Let us now prove Theorem 15. Let a_{1} be the rightmost element on the first level of S, and let T_{1} = {a_{1}}. Once T_{i} is defined, let T_{i+1} be the set of elements on the (i + 1)^{th} level, each of whose elements is smaller than at least one element in T_{i}, 1 ≤ i ≤ h. For a given semiorder S, the set T_{i} is uniquely determined, 1 ≤ i ≤ h. Notice that it is possible that T_{i} = ∅, for some i, 1 ≤ i ≤ h, and if T_{i} = ∅, then we must have T_{j} = ∅ for all i ≤ j ≤ h + 1. Let A_{2} = T_{1} ∪ T_{2} ∪ ⋯ ∪ T_{h+1}, and A_{1} = A − A_{2}, where A is the set of all elements of S. Since a_{1} ∈ A_{2}, we must have 1 ≤ |A_{2}| ≤ n, 0 ≤ |A_{1}| ≤ n − 1, and |A_{1}| + |A_{2}| = n.

Let us separate S into two semiorders S_{1} and S_{2}. Let S_{1} be the induced semiorder with element set A_{1}. Similarly, let S_{2} be the induced semiorder with element set A_{2}. Let S_{3} be the semiorder obtained from S_{2} by removing element a_{1}. Then for a given semiorder S, we have that S_{1}, S_{2}, S_{3} are uniquely defined. Since S is a semiorder of length at most h, semiorders S_{1} and S_{2} have length at most h, and thus S_{3} has length at most h − 1.

Assume |A_{1}| = t, so S_{3} is a semiorder with n − 1 − t elements. As a result, for a given n-element semiorder S of length at most h, we can uniquely obtain a pair of semiorders S_{1} and S_{3}, of length at most h and at most h−1, and with t and n−1−t elements, respectively, 0 ≤ t ≤ n − 1.

For example, if S is as follows,

[figure: •; •; •; •; •; •; •; •; •]

the corresponding S_{1}, S_{2}, S_{3} are:

[figure: •; •; •; •; S_{1}; •; •; •; •; •; S_{2}; •; •; •; •; S_{3}]

On the other hand, given a pair of semiorders S_{1} and S_{3}, of length at most h and at most h − 1, and with t and n − 1 − t elements, respectively, 0 ≤ t ≤ n − 1, we can first add an element a_{1} to S_{3}, and let a_{1} be larger than all other elements in S_{3}. Let us call the new semiorder S_{2}. Then S_{2} has n − t elements and length at most h.

Let us construct a new semiorder S by combining S_{1} and S_{2} as follows. The elements on the i^{th} level of S are the elements on the i^{th} level of S_{1} and S_{2}, 1 ≤ i ≤ h + 1, and the order relations in S_{1} and S_{2} are preserved. In addition, let every element on the (i − 1)^{th} level of S_{1} be larger than all elements on the i^{th} level of S_{2}.

This construction uniquely gives an n-element semiorder S of length at most h, and if we separate S into two semiorders by the method discussed above, we get back S_{1} and S_{3}.

As a result, there is a one-to-one map between n-element semiorders S of length at most h, and pairs of semiorders S_{1} and S_{3}, of length ≤ h and ≤ h − 1, and with t and n − 1 − t elements, respectively, 0 ≤ t ≤ n − 1.

Therefore, summing up possible t’s, we have

f_{≤h}^{n} = ∑_{t=0}^{n−1} f_{≤h}^{t}f_{≤h−1}^{n−1−t}.

4.2 Recurrence formula 2

Theorem 18. For n ≥ 2 and h ≥ 1, we have

f_{≤h}^{n} = ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}\binom{h + 2 − k}{k}f_{≤h}^{n−k}.  (12)

Proof. Let us prove this theorem by first defining bad elements of a semiorder and then considering removing one or more bad elements from a given semiorder.

Definition 19. We say an element of a semiorder is bad if the following two conditions hold.

• It is on the first level, or it is smaller than all elements on the level immediately above it, and

• it is on the last level, or it is not larger than any element on the level immediately below it.

Remark 20. By the above definition, there are no two adjacent levels which both have bad elements. In addition, by Proposition 5, if two bad elements are on the same level, they must be equivalent. Therefore there is at most one non-equivalent bad element on each level. We thus only consider one bad element on each level.

Proposition 21. For every semiorder, there exist bad elements.

Proof. Assume to the contrary that there is no bad element for some semiorder. Say a is the rightmost element on the last level based on Definition 16. Since a is not bad, there must be some element b on the last but one level which is not larger than a. Let {a_{1}, a_{2}, …, a_{s}} be the set of all elements on the last but one level which are larger than a. By the definition of element levels, we must have s ≥ 1.

If there exists some element b_{1} on the last level such that b > b_{1}, since a is the rightmost, i.e., a is to the right of b_{1}, there must exist some i, 1 ≤ i ≤ s, such that a_{i} is not larger than b_{1}. Then {a_{i} > a, b > b_{1}} forms a (2 + 2)-structure. This is a contradiction. Hence b is not larger than any element on the last level, and thus b is the rightmost element on the last but one level.

Since b is not bad, it must not be on the first level, and there must be some element c on the level immediately above b that is not larger than b. Again due to the fact that b is the rightmost element on its level and that we cannot have a (2 + 2)-structure, c must be not larger than any element on the level immediately below the level c is on. Continuing, we can find an element on each level that is not larger than any element on the level immediately below it. Since the length of the semiorder is finite, we can finally obtain an element d on the first level such that d is not larger than any element on the second level. Then d is bad, and we get a contradiction. Hence, for every semiorder, bad element exists.

We are now ready to deduce the recurrence formula (18). For fixed k, consider adjoining k bad elements to an (n − k)-element semiorder to get a new semiorder. Specifically, for an (n − k)-element semiorder of length at most h, and for k nonadjacent levels among levels 1, 2, …, h + 1, we consider adjoining k elements onto the given levels of the semiorder in the following manner. Say we are adjoining an element onto the l^{th} level.

• If l = 1, let the new element be larger than all elements on the i^{th} level, i ≥ 3, and be not comparable with any other element.

• If l ≥ 2, and the (l − 1)^{th} level originally has at least one element, we let the new element be smaller than all elements on the (l − 1)^{th} level, be larger than all elements on the i^{th} level, i ≥ l + 2, and be not comparable with any other element.

• If l ≥ 2, and the (l − 1)^{th} level originally has no element, we hang the new element on the l^{th} level, that is, we place it as an isolated vertex on the l^{th} level. We then call the new semiorder an invalid semiorder, and if some semiorder r_{0} can be obtained from the invalid semiorder by taking out the hanging elements, we call the invalid semiorder the disguise of r_{0}.

By Definition 19, in the above adjoining, all new elements which are not hung are bad elements in the new semiorder. There are \binom{h+2−k}{k} ways to choose k nonadjacent levels among levels 1, 2, …, h + 1. Therefore, including multiplicity and the invalid ones, we can obtain \binom{h+2−k}{k} · f_{≤h}^{n−k} n-element semiorders from (n − k)-element semiorders by adjoining k elements. Let S^{k} be the set of all such n-element semiorders, including multiplicity. Then |S^{k}| = \binom{h+2−k}{k} · f_{≤h}^{n−k}.

Let R be the set of all n-element semiorders of length at most h, and R′ be the set of all semiorders with at most n − 1 elements and length at most h. By Proposition 21, every semiorder has bad elements, so every semiorder r ∈ R can be obtained by the above process from some (n − k)-element semiorder of length at most h and k given nonadjacent levels, i.e., r ∈ S^{k}, for some 1 ≤ k ≤ ⌊\frac{h+2}{2}⌋. However, r might be in S^{k} for multiple k’s, and r may have multiple copies in S^{k}. Meanwhile, S^{k} may contain some semiorders not in R, but are the disguises of some semiorders r′ ∈ R′. Notice that |R| = f_{≤h}^{n}. In the following argument, we calculate the number of copies of a semiorder in each S^{k} and obtain a formula connecting |R| and |S^{k}|, 1 ≤ k ≤ ⌊\frac{h+2}{2}⌋.

For a semiorder r_{0} ∈ R ∪ R′, let S_{r_{0}}^{k} be the set of all semiorders in S^{k} which are equal to r_{0} or a disguise of r_{0}. Then S^{k} = ⋃_{r∈R∪R′} S_{r}^{k}, and

∑_{r∈R∪R′} |S_{r}^{k}| = |S^{k}| = \binom{h + 2 − k}{k} · f_{≤h}^{n−k}.  (13)

Next, we show that ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r}^{k}| = 1, for every r ∈ R, and ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r′}^{k}| = 0, for every r′ ∈ R′.

1. For a semiorder r ∈ R, assume r has m bad elements. Since we adjoined k elements to an (n − k)-element semiorder to obtain the semiorder r, which has n elements, the k new elements should all be added to the levels among the m levels where the bad elements are, and no new element is hung. So k ≤ m. Further notice that for a given k, 1 ≤ k ≤ m, and given k levels among the m levels where the bad elements are, there is a unique (n − k)-element semiorder can be used to adjoin k bad elements to the chosen levels to obtain semiorder r. There are \binom{m}{k} ways to choose the k levels, so |S_{r}^{k}| = \binom{m}{k} · 1, and

∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r}^{k}| = ∑_{k=1}^{m}(−1)^{k−1}|S_{r}^{k}| = ∑_{k=1}^{m}(−1)^{k−1}\binom{m}{k} · 1 = 1.  (14)

2. For a semiorder r′ ∈ R′, assume r′ has n′ elements, m′ of which are bad. Further assume that semiorder r′ has length h′. For a given k, 1 ≤ k ≤ ⌊\frac{h+2}{2}⌋, if we adjoined k elements to an (n − k)-element semiorder to obtain r′, we need to adjoin t′ = n′ − (n − k) elements to levels where the bad elements of r′ are, and hang the remaining n − n′ elements. Moreover, since we hung n − n′ elements, there should be at least n − n′ nonadjacent levels among levels h′ + 2, h′ + 3, …, h + 1. As a result, ⌈\frac{h−h′}{2} ⌉ ≥ n − n′.

To obtain the semiorder r′, if we are given t′ levels among the m′ levels where the bad elements of r′ are and n − n′ nonadjacent levels among levels h′ + 2, h′ + 3, …, h + 1, there is a unique (n − k)-element semiorder to which we can adjoin k elements to the chosen levels to obtain the disguise of r′. Notice that there are \binom{m′}{t′} ways to choose t′ levels among the m′ levels, and \binom{h−h′+1−(n−n′)}{n−n′} ways to choose n − n′ nonadjacent levels from levels h′ + 2, h′ + 3, …, h + 1. Thus,

|S_{r′}^{k}| = |S_{r′}^{t′−n′+n}| = \binom{m′}{t′} · \binom{h − h′ + 1 − (n − n′)}{n − n′} · 1.

Then

∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r′}^{k}| = ∑_{t′=0}^{m′}(−1)^{t′−n′+n−1}|S_{r′}^{t′−n′+n}|

= ∑_{t′=0}^{m′}(−1)^{t′−n′+n−1}\binom{m′}{t′} · \binom{h − h′ + 1 − (n − n′)}{n − n′} · 1

= (−1)^{n−n′−1} · \binom{h − h′ + 1 − (n − n′)}{n − n′} ∑_{t′=0}^{m′}(−1)^{t′} \binom{m′}{t′} = 0.  (15)

However, we should be careful with the special case when t′ ≥ 1 and the (h′ + 1)^{th} level of r′ has bad elements. In this case, the (h′ + 1)^{th} level and the (h′ + 2)^{th} level might be both chosen when we choose n − n′ nonadjacent levels among levels h′ + 2, h′ + 3, …, h + 1 and choose t′ levels among the m′ levels where bad elements are (note that here the (h′ + 1)^{th} level is among the m′ levels). Further notice that S_{r′}^{k} ∈ S^{k} and S^{k} is defined as the set of all n-element semiorders generated by adjoining k elements to k nonadjacent levels to (n − k)-element semiorders. Therefore, when we calculate |S_{r′}^{k}|, we need to take out the overcounts of cases when the two adjacent levels (h′ + 1) and (h′ + 2) are both chosen. Thus in the special case where t′ ≥ 1 and the (h′ + 1)^{th} level of r′ has bad elements,

|S_{r′}^{k}| = |S_{r′}^{t′−n′+n}|

= \binom{m′}{t′} · \binom{h − h′ + 1 − (n − n′)}{n − n′} · 1 − \binom{m′ − 1}{t′ − 1} · \binom{h − h′ − 1 − (n − n′ − 1)}{n − n′ − 1} · 1

By similar calculations, we have ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r′}^{k}| = 0.

To conclude the proof, by equations (13), (14), and (15), we have

f_{≤h}^{n} = |R| = ∑_{r∈R} 1 + ∑_{r′∈R′} 0 = ∑_{r∈R} ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r}^{k}| + ∑_{r′∈R′} ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}|S_{r′}^{k}|

= ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1} ∑_{r∈R∪R′} |S_{r}^{k}|

= ∑_{k=1}^{⌊ \frac{h+2}{2} ⌋}(−1)^{k−1}\binom{h + 2 − k}{k} · f_{≤h}^{n−k}.

5 The Number of Semiorders of Small Length

We can substitute certain lengths H in the explicit formulas for the number of semiorders. Though the original formulas are very complicated, we can get some simple results for small values of H. In this section, we list these simple results and give bijective proofs, which present a clearer view of the number of fixed-length semiorders.

5.1 f_{≤1}^{n}, the number of nonisomorphic unlabeled n-element semiorders of length at most one

Theorem 22. For n ≥ 1, f_{≤1}^{n} = 2^{n−1}.

We give a simple bijective proof here.

Proposition 23. For n elements a_{1}, a_{2}, …, a_{n}, put a_{1} on the upper level, and each of a_{2}, …, a_{n} either on the lower or upper level. Define the order relations in the following way: a_{i} > a_{j} if and only if i < j, and a_{i} is on the upper level while a_{j} is on the lower level.

We claim that the above defines a bijective map from (a) an arrangement of n−1 elements onto two levels in (b) an n-element semiorder of length at most one.

Here is an example of the map. Say n = 10, and for a_{2}, …, a_{10}, let {a_{2}, a_{5}, a_{9}} be on the upper level, and {a_{3}, a_{4}, a_{6}, a_{7}, a_{8}, a_{10}} on the lower level. Then the corresponding semiorder looks like:

[figure: •; •; •; •; •; •; •; •; •; •; a_{1}; a_{2}; a_{5}; a_{9}; a_{3}; a_{4}; a_{6}; a_{7}; a_{8}; a_{10}]

Proof. We first show that the map gives a semiorder of length at most one. It suffices to show that the poset the map gives is indeed a semiorder. Then the only possible violation is a (2 + 2)-structure. If there exist four distinct elements a_{i}, a_{j}, a_{k}, a_{m}, such that a_{i} > a_{j}, a_{k} > a_{m}, a_{i} ∼ a_{k}, a_{i} ∼ a_{m}, a_{k} ∼ a_{j}, a_{m} ∼ a_{j}, then a_{i}, a_{k} must be on the upper level, while a_{j}, a_{m} must be on the lower level, and i < j, k < m. Since a_{i} ∼ a_{m}, we must have i > m; since a_{k} ∼ a_{j}, we must have k > j. Then k > j > i > m > k, which is a contradiction. Hence the map gives a semiorder of length at most one.

We then claim that the inverse map is also well-defined, and thus the map is bijective. For a given n-element semiorder r with m elements on the upper level, let ρ(r) = (r_{1}, r_{2}, …, r_{n}). Then r_{m+1} = r_{m+2} = ⋯ = r_{n} = 0. Say element a_{t_{i}} corresponds to r_{i}, 1 ≤ i ≤ m, and then there should be exactly r_{i} elements on the lower level such that their subscripts are larger than t_{i}. As a result, note that a_{1} is on the upper level, we should also have a_{r_{1}−r_{2}+2}, a_{r_{1}−r_{3}+3}, …, a_{r_{1}−r_{m}+m} on the upper level. In other words, for a given semiorder of length at most one, the elements arranged on the upper level are uniquely determined. Therefore, the inverse map is well-defined.

As an example, if we have (r_{1}, r_{2}, …, r_{n}) = (6, 6, 4, 1, 0, 0, 0, 0, 0, 0), then the elements on the upper level must be a_{1}, a_{2}, a_{5}, a_{9}.

There are 2^{n−1} ways to arrange elements a_{2}, …, a_{n} on either upper or lower level, and thus there are 2^{n−1} nonisomorphic unlabeled n-element semiorders of length at most one.

5.2 The number of nonisomorphic trees derived from semiorders of length at most one

In this subsection, we take a closer look at the unlabeled semiorders of length at most one. For an n-element semiorder S of length at most one, and exactly m elements on the first level, let ρ(S) = (r_{1}, r_{2}, …, r_{m}, 0, 0, …, 0), where there are n − m 0’s and n − m ≥ r_{1} ≥ r_{2} ≥ ⋯ ≥ r_{m} ≥ 0. Let the elements of the semiorder be s_{1}, s_{2}, …, s_{n}, with s_{i} corresponding to r_{i}, 1 ≤ i ≤ m, and then s_{1}, s_{2}, …, s_{m} are on the upper level.

For a permutation σ = (a_{1}, a_{2}, …, a_{m}) of {1, 2, …, m}, if we add the relations s_{a_{1}} > s_{a_{2}} > ⋯ > s_{a_{m}} to the original semiorder, we get a tree with the main trunk s_{a_{1}} > s_{a_{2}} > ⋯ > s_{a_{m}}, and the elements s_{m+1}, s_{m+2}, …, s_{n} attached to one of the elements on the main trunk in the following manner. For m + 1 ≤ i ≤ n, element s_{i} is attached to element s_{j} on the main trunk if and only if s_{i} < s_{j}, and s_{i} is incomparable with all elements on the main trunk that are below s_{j}, 1 ≤ j ≤ m. We denote the tree derived from semiorder S and permutation σ by T (S, σ).

For example, the Hasse diagram of the semiorder S with ρ(S) = (7, 5, 4, 2, 1, 0, 0, 0, 0, 0, 0) is as follows:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; s_{1}; s_{2}; s_{3}; s_{4}; s_{5}; s_{6}; s_{7}; s_{8}; s_{9}; s_{10}; s_{11}; s_{12}]

Suppose that σ = (1, 5, 3, 2, 4), and then we add the relations s_{1} > s_{5} > s_{3} > s_{2} > s_{4} to the original semiorder. Then T (S, σ) is

[figure: •; •; •; •; •; •; •; •; •; •; •; •; s_{1}; s_{2}; s_{3}; s_{4}; s_{5}; s_{6}; s_{7}; s_{8}; s_{9}; s_{10}; s_{11}; s_{12}]

Here we call s_{1} > s_{5} > s_{3} > s_{2} > s_{4} the main trunk, and say elements s_{6}, s_{7} are attached to s_{1}, elements s_{8}, s_{9}, s_{10} are attached to s_{2}, and elements s_{11}, s_{12} are attached to s_{4}.

The idea of transforming a semiorder of length at most one to a tree is suggested by R. Stanley, in the context of finding the number of linear extensions of n-element semiorders of length at most one. Though this idea may not be useful in its original context, we can give a different application.

Theorem 24. Given an n-element semiorder R_{m} of length at most one and exactly m elements on the first level, let ρ(R_{m}) = (r_{1}, r_{2}, …, r_{n}). If r_{i} ≠ r_{j} for any 1 ≤ i < j ≤ m, then the number of nonisomorphic unlabeled trees in {T (R_{m}, σ)|σ ∈ S_{m}} is the Catalan number C_{m}.

Proof. A permutation σ = (a_{1}, a_{2}, …, a_{m}) of {1, 2, …, m} uniquely determines the main trunk. For m + 1 ≤ i ≤ n, assume element s_{i} is smaller than t_{i} elements. Then s_{i} must be smaller than s_{1}, s_{2}, …, s_{t_{i}} and is not comparable with the other elements. Let s_{u_{i}} be the lowest element on the main trunk among s_{1}, s_{2}, …, s_{t_{i}}. Then s_{i} is attached to s_{u_{i}} as a leaf, meaning s_{i} is smaller than s_{u_{i}} but not comparable with any element on the main trunk below s_{u_{i}}.

As a result, for an element s_{u} on the main trunk, s_{u} has leaves only if it is the lowest element on the main trunk among s_{1}, s_{2}, …, s_{t}, for some 1 ≤ t ≤ m. In other words, assume b_{1} < b_{2} < ⋯ < b_{k} are the set of right-to-left minima of the permutation σ = (a_{1}, a_{2}, …, a_{m}), and then only the elements s_{b_{1}}, s_{b_{2}}, …, s_{b_{k}} may have leaves. Further notice that the numbers of leaves attached to s_{b_{1}}, s_{b_{2}}, …, s_{b_{k}} are r_{b_{1}} − r_{b_{2}}, r_{b_{2}} − r_{b_{3}}, …, r_{b_{k−1}} − r_{b_{k}}, r_{b_{k}}, respectively, and r_{i} ≠ r_{j} for any 1 ≤ i < j ≤ m. Therefore, for a given n-element semiorder R_{m} of length at most one and exactly m elements on the first level, the value and position of the right-to-left minima of the permutation σ = (a_{1}, a_{2}, …, a_{m}) uniquely determines T (R_{m}, σ).

For instance, in the example above, we have σ = (1, 5, 3, 2, 4) and ρ(R_{5}) = (r_{1}, r_{2}, …, r_{12}) = (7, 5, 4, 2, 1, 0, 0, 0, 0, 0, 0, 0). The right-to-left-minima of σ and their positions with σ is given by 1, ∗, ∗, 2, 4. Then the corresponding tree T (R_{5}, σ) has five nodes on the main trunk, r_{1} − r_{2} = 2 leaves attached to the first node, r_{2} − r_{4} = 3 leaves attached to the forth node, and r_{4} = 2 leaves attached to the fifth node.

Therefore, the number of all possible nonisomorphic unlabeled trees in {T (R_{m}, σ)|σ ∈ S_{m}} is equal to the number of ways to specify the values and positions of the right-to-left minima of permutations σ ∈ S_{m}. That is, if we let RtLM(σ) = {(a, σ(a))|1 ≤ a ≤ m, σ(a) is a right-to-left minima in σ}, then #{T (R_{m}, σ)|σ ∈ S_{m}} = #{RtLM(σ)|σ ∈ S_{m}}. We calculate #{RtLM(σ)|σ ∈ S_{m}} in the following lemma.

Lemma 25. Let RL(σ) be the number of right-to-left minima of the permutation σ. For 1 ≤ k ≤ m, let f(m, k) = #{RtLM(σ)|σ ∈ S_{m}, RL(σ) = k}. Then f(m, k) = N(m, k) = \frac{1}{m} \binom{m}{k}\binom{m}{k−1}, a Narayana number.

For example, for m = 3 and k = 2, f(3, 2) = #{RtLM(σ)|σ ∈ S_{3}, RL(σ) = 2} = #{RtLM(σ)|σ = (23), (12), or (132)} = #{{(3, 2), (1, 1)}, {(3, 3), (2, 1)}, {(3, 2), (2, 1)}} = 3.

Proof. For 1 ≤ k ≤ m, the Narayana number N(m, k) is equal to the number of Dyck paths of semilength m with k peaks, which are the turning points from a (1, 1) step to a (1, −1) step on the path. We prove the lemma by establishing a bijection between (i) Dyck paths of semilength m with k peaks, and (ii) the collection of different RtLM(σ)’s for σ ∈ S_{m}, RL(σ) = k. We define a map from (i) to (ii) as follows:

Given a Dyck path of semilength m with k peaks, let us read the Dyck path from left to right and do the following:

• Label the endpoints of (1, 1) steps from left to right with 1 to m. Since there are m (1, 1) steps, there should be m such endpoints.

• Label the startpoints of (1, −1) steps from left to right with 1 to m. Since there are m (1, −1) steps, there should be m such startpoints.

• Notice that a point on the Dyck path is a peak if and only if it is both an endpoint of a (1, 1) step and a startpoint of a (1, −1) step. Let (i, j) be the coordinate of a peak, if the peak is the i^{th} endpoint and the j^{th} startpoint. Assume the coordinate of the k peaks are (a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{k}, b_{k}). Then a_{1} < a_{2} < ⋯ < a_{k} = m and 1 = b_{1} < b_{2} < ⋯ < b_{k}.

• Obtain a specification of the values and positions of the right-to-left minima of a permutation by putting the number b_{i} on position a_{i}, 1 ≤ i ≤ k.

Proposition 26. The above map is valid, i.e., {(a_{i}, b_{i}), 1 ≤ i ≤ k} = RtLM(σ), for some σ ∈ S_{m}, RL(σ) = k, and the above map is a bijection.

For example, if we have the following Dyck path:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 1; 2; 3; 4; 5; 6; 7; 1; 2; 3; 4; 5; 6; 7]

The semilength of the Dyck path is m = 7, and it has 4 peaks. The numbers in bold face are the labels for the endpoints of (1, 1) steps, and the numbers in ordinary type are the labels for the startpoints of (−1, 1) steps. Then the coordinates of the 4 peaks are (3, 1), (4, 3), (6, 4), (7, 7). We put 1 on position 3, 3 on position 4, 4 on position 6, 7 on position 7, and then we get a possible specification of the values and positions of the rightto-left minima of a permutation:

∗, ∗, 1, 3, ∗, 4, 7.  (16)

Proof. • We first show that the above map gives us a valid specification of the values and positions of the right-to-left minima of some permutation σ ∈ S_{m}. We prove the validity by constructing such σ.

Assume the labels of the m − k endpoints of the (1, 1) steps which are not peaks, are c_{1} < c_{2} < ⋯ < c_{m−k}; assume the labels of the m − k startpoints of the (1, −1) steps which are not peaks are d_{1} < d_{2} < ⋯ < d_{m−k}. Then

{a_{1}, a_{2}, …, a_{k}, c_{1}, c_{2}, …, c_{m−k}} = {b_{1}, b_{2}, …, b_{k}, d_{1}, d_{2}, …, d_{m−k}} = {1, 2, …, m}.

Since the path never goes below the x-axis, we must have c_{j} < d_{j} for every 1 ≤ j ≤ m − k.

Let σ be a permutation such that σ(a_{i}) = b_{i}, 1 ≤ i ≤ k, and σ(c_{j}) = d_{j}, 1 ≤ j ≤ m−k. We will show that RtLM(σ) = {(a_{i}, b_{i}), 1 ≤ i ≤ k}.

For every j, 1 ≤ j ≤ m − k, since the Dyck path never goes below the x axis, there must be a peak i on the path between c_{j} and d_{j}. Then c_{j} < a_{i} and b_{i} < d_{j}, and thus in σ, b_{i} = σ(a_{i}) is smaller than d_{j} = σ(c_{j}), while a_{i} > c_{j}, i.e., b_{i} is to the right of d_{j}. Therefore d_{j} cannot be a right-to-left minimum.

On the other hand, for every i, 1 ≤ i ≤ k, there does not exist some 1 ≤ i′ ≤ k such that b_{i′} < b_{i} and a_{i′} > a_{i}. In addition, if there exists some 1 ≤ j ≤ m − k such that d_{j} = σ(c_{j}) < b_{i} = σ(a_{i}) and c_{j} < a_{i}, then by the above paragraph there exists 1 ≤ i′ ≤ k, such that b_{i′} < d_{j} < b_{i} and a_{i′} > c_{j} > a_{i}. We obtain a contradiction. As a result, RtLM(σ) = {(a_{i}, b_{i}), 1 ≤ i ≤ k}.

For example, let us construct the permutation σ for the above example: c_{1} = 1, c_{2} = 2, c_{3} = 5 and d_{1} = 2, d_{2} = 5, d_{3} = 6. We obtain σ = (2, 5, 1, 3, 6, 4, 7), and this permutation exactly corresponds to the right-to-left minima as shown in Example 16.

• We now show that the inverse of the map is well-defined, and thus the map is bijective.

For a given specification {(a_{i}, b_{i}), 1 ≤ i ≤ k} = RtLM(σ), for some σ ∈ S_{m}, we have a_{1} < a_{2} < ⋯ < a_{k} = m and 1 = b_{1} < b_{2} < ⋯ < b_{k}. We construct the corresponding Dyck path as follows: when we walk along the path from left to right, we first walk up a_{1} steps and then turn down, and walk down b_{2} − b_{1} steps and then turn up. We continue to walk up a_{2} − a_{1} steps and then turn down, and walk down b_{3} − b_{2} steps and then turn up. In general, we walk up a_{i} − a_{i−1} steps and then turn down, and walk down b_{i+1} − b_{i} steps, 2 ≤ i ≤ m − 1. In the end, we walk up a_{m} − a_{m−1} steps and walk down m + 1 − b_{m} steps. During the walk, we walk up in total a_{1} + (a_{2} − a_{1}) + ⋯ + a_{m} − a_{m−1} = a_{m} = m steps, and walk down in total (b_{2} − b_{1}) + ⋯ + (b_{m} − b_{m−1}) + m + 1 − b_{m} = m + 1 − b_{1} = m steps, and we make k turns from up to down. Since {(a_{i}, b_{i}), 1 ≤ i ≤ k} is a collection of right-to-left minima of some permutation, for any 1 ≤ i ≤ k − 1, a_{i} ≤ a_{i+1} − 1 ≤ b_{i+1} − 1 = b_{i+1} − b_{1}, so we never walk below the x-axis on the path. Therefore we get a unique Dyck path with semilength m and k peaks. Hence the inverse map is well-defined, so Lemma 25 is proved.

To conclude the proof of Theorem 24, note that the Catalan number C_{m} = ∑_{k=1}^{m} N(m, k). Hence, we have that the number of nonisomorphic unlabeled trees in {T (R_{m}, σ)|σ ∈ S_{m}} is equal to #\{RtLM(σ)|σ ∈ S_{m}\} = ∑_{k=1}^{m} f(m, k) = ∑_{k=1}^{m} N(m, k) = C_{m} = \frac{1}{m+1} \binom{2m}{m}.

Remark 27. Theorem 24, along with Lemma 25, gives another combinatorial explanation of the Catalan number.

5.3 The generating function for the number of nonisomorphic labeled n-element semiorders of length at most one

Recall that an ordered partition of a set is a partition of the set into some pairwise disjoint nonempty subsets, together with a linear ordering of these subsets. From the generating function (9) for G_{≤h}(x), we get G_{≤1}(x) = (1 − e^{−x})/(2e^{−x} − 1) = (e^{x} − 1)/(2 − e^{x}), which is exactly the exponential generating function for the number of ordered partitions [5, p. 472]. As a result, we can get the following theorem:

Theorem 28. The number of nonisomorphic labeled n-element semiorders of length at most one is equal to the number of ordered partitions of [n].

We give a simple bijective proof to Theorem 28.

Proposition 29. For an ordered partition (A_{1}, …, A_{k}) of [n], let |A_{i}| = a_{i}, 1 ≤ i ≤ k, so n = a_{1} + a_{2} + ⋯ + a_{k}. Define the semiorder R by ρ(R) = (m, m − 1, …, 1, 0, …, 0), where m = ⌊\frac{k}{2}⌋, and there are ⌈\frac{k}{2}⌉ 0’s. Then R has k elements. Say the elements are t_{1}, t_{2}, …, t_{k}, with t_{i} corresponding to the i^{th} entry of R’s integer vector. Let R′ be another semiorder such that its contraction c(R′) (defined in Lemma 13) is R, and in R′, the sizes of the equivalence classes are a_{1}, a_{2}, …, a_{k}, respectively, with a_{i} corresponding to equivalence class t_{i}. Label the elements in the i^{th} equivalence class with the corresponding numbers in A_{i}, 1 ≤ i ≤ k.

We claim that the above defines a bijective map from ordered partitions of [n] to n-element labeled semiorders R′ of length at most one.

For example, if we have an ordered partition {1, 4}{2, 6, 8}{7}{3, 5}, then k = 4, m = 2, and (a_{1}, a_{2}, a_{3}, a_{4}) = (2, 3, 1, 2). We have ρ(R) = (2, 1, 0, 0), and then the map works as follows:

[figure: •; •; •; •; R; ⟶; •; •; •; •; •; •; •; •; unlabeled R′; ⟶; •; •; •; •; •; •; •; •; labeled R′; 1; 4; 7; 2; 6; 8; 3; 5]

Proof. We first show that the map takes an ordered partition of [n] to a labeled n-element semiorder of length at most one. The size of every equivalence class of R is one, and thus semiorder R is a valid contraction. The length of R is at most one, and thus R′ also has length at most one. In addition, R has k elements, so R′ has k equivalence classes. Therefore, we can construct the equivalence classes of R to have sizes a_{1}, a_{2}, …, a_{k}. Moreover, within an equivalence class with a_{i} elements, 1 ≤ i ≤ k, since we only consider nonisomorphic semiorders, it does not matter which of the a_{i} numbers in A_{i} is assigned to which element in this equivalence class. Hence the way to label elements is unique up to isomorphism. Thus each ordered partition of [n] uniquely corresponds to a labeled n-element semiorder of length at most one.

Next we show that the inverse map is well-defined and uniquely determines an ordered partition of [n]. Let the labeled n-element semiorder R′ of length at most one have k equivalence classes. Let us group up the labels within every equivalence class, so

[n] = ⋃{labels in each equivalence class}.

To obtain an ordered partition of [n], it suffices to find the way to order the k equivalence classes of R′. The contraction c(R′) must have length at most one with ρ(c(R′)) = (⌊\frac{k}{2}⌋, ⌊\frac{k}{2}⌋− 1, …, 1, 0, …, 0), where there are ⌈\frac{k}{2}⌉ 0’s.

Order the k elements of c(R′) such that the i^{th} element corresponds to the i^{th} entry of ρ(c(R′)). Afterwards, we can order the k equivalence classes of R′ correspondingly. Thus we get a unique ordered partition of [n], so the inverse map is well-defined.

5.4 The number of nonisomorphic unlabeled n-element semiorders of length at most three

Theorem 30. For n ≥ 1, we have

f_{≤3}^{n} = \frac{3^{n−1} + 1}{2}.  (17)

Corollary 31. For n ≥ 2, f_{3}^{n} = 3f_{3}^{n−1} + f_{≤2}^{n−2} − 1 = 3f_{3}^{n−1} + f_{2}^{n−2} + f_{1}^{n−2}.

Proof. By Theorem 18, f_{≤2}^{n} = 3f_{≤2}^{n−1} − f_{≤2}^{n−2}. By equation (17), f_{≤3}^{n} = 3f_{≤3}^{n−1} − 1. Therefore,

f_{3}^{n} = f_{≤3}^{n} − f_{≤2}^{n} = 3f_{≤3}^{n−1} − 1 − (3f_{≤2}^{n−1} − f_{≤2}^{n−2})
= 3(f_{≤3}^{n−1} − f_{≤2}^{n−1}) + f_{≤2}^{n−2} − 1
= 3f_{3}^{n−1} + f_{2}^{n−2} + f_{1}^{n−2}.

Remark 32. Theorem 30 can be directly derived from equation (8), or from the recurrence formula in Theorem 18. Like Theorem 22, there might also be a more straightforward bijective proof for Theorem 30, which may give us a more intuitive way to understand why f_{≤3}^{n} grows roughly exponentially with a base 3. This leaves an open question for this paper.

This paper studies the number of unlabeled semiorders of size n and length H and gives an explicit formula for this number by establishing a bijection between semiorders and ordered trees. With this result, we derive a series of related results including the number of fixedlength labeled semiorders, some recurrence relations of semiorders of fixed length, and some interesting properties of the number of semiorders of small length. Bijections are widely used in this paper and as can be seen, bijective proofs can sometimes provide us pretty neat ways to view the semiorder and its relationship with some other sets of combinatorial objects. Further research may combine the results of this paper with some other bijective results of (2 + 2)-free posets and find more interesting results about semiorders.

6 Acknowledgments

The author would like to thank Richard Stanley for valuable suggestions and careful readings of the manuscript.

References

[1] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), 884–909.

[2] N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees, Graph Theory and Computing, Academic Press, 1972, pp. 15–22.

[3] J. L. Chandon, J. Lemaire, and J. Pouget, Dénombrement des quasi-ordres sur un ensemble fini, Math. Sci. Hum. 62 (1978), 61–80.

[4] P. C. Fishburn and W. T. Trotter, Linear extensions of semiorders: A maximization problem, Discrete Math. 103 (1992), 25–40.

[5] R. P. Stanley, Enumerative Combinatorics, Vol. 1, second edition, Cambridge University Press, Cambridge, 2011.

[6] R. L. Wine and J. E. Freund, On the enumeration of decision patterns involving n means, Ann. Math. Stat. 28, (1957), 256–259.

[7] Y. X. Zhang, private communication, 2011.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: semiorder, ordered tree, Dyck path.

(Concerned with sequence \underline{A000108}.)

Received June 26 2013; revised versions received October 28 2013; November 25 2013. Published in Journal of Integer Sequences, December 16 2013.

Return to Journal of Integer Sequences home page.