q \Leftrightarrow p>q, \text{ for all } q\in P.$$ \end{definition} \vspace{12pt} \begin{lemma}\label{Yan} Define the following two operations on an unlabeled poset $P$. \begin{itemize} \item The \emph{expansion} of $P$ at $p \in P$ is obtained from $P$ by adjoining a new element $p'$ such that $p$ and $p'$ are equivalent. \item The \emph{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 \emph{seed} if $P = c(P)$. Call a seed $P$ \emph{rigid} if $P$ has no nontrivial automorphisms. \end{itemize} 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)=\sum_{P\in C}x^{\#P}$ and $G(x)=\sum_{P\in 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\hspace{3pt}P)}$, where $aut\hspace{3pt}P$ is the automorphism group of $P$. Then $G(x) = F(1-e^{-x})$. \end{lemma} The class of semiorders of length $h$ is closed under expansion and contraction. Zhang has observed that all $(\bm{2}+\bm{2})$-free seeds are rigid. Since semiorders are $(\bm{2}+\bm{2})$-free, all seeds of semiorders are rigid. As a result, Lemma \ref{Yan} implies the following corollary. \begin{corollary} For $h\geq 0$, \begin{equation}\label{3.8} 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})} \end{equation} and \begin{equation}\label{3.10} G_{\leq h}(x)=F_{\leq h}(1-e^{-x})=F_{\leq h}(1-e^{-x}) = \frac{p_{h}(1-e^{-x})}{p_{h+1}(1-e^{-x})}. \end{equation} \end{corollary} \section{Recurrence Relations}\label{sec5} 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 (\ref{eq4.1}) is a standard result that is known for ordered trees \cite[p.17]{first}, but only a proof using generating functions was given, while the second recurrence formula (\ref{eq4.2}) 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. \subsection{Recurrence formula 1} \begin{theorem}\label{5.7} For $n \geq 2$ and $h \geq 1$, \begin{equation}\label{eq4.1} f_{\leq h}^{n}=\sum_{t=0}^{n-1} f_{\leq h}^{t}f_{\leq h-1}^{n-1-t}, \end{equation} where $f_{\leq h}^0=1.$ \end{theorem} \begin{proof} Let us prove this theorem by first defining the relative positions of elements on the same level of a semiorder. \vspace{6pt} \begin{definition}\label{rightmost} For elements $a$ and $b$ on the same level of a semiorder $S$, we say that element $b$ is \emph{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. \end{definition} \begin{remark} 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 \ref{ch1}, is $(r_1, r_2, \dots, r_n)$, then element $b$ is \emph{to the right of} element $a$ if $b$ corresponds to $r_j$, while $a$ corresponds to $r_i$, $ib_1$, since $a$ is the rightmost, i.e., $a$ is to the right of $b_1$, there must exist some $i$, $1\leq i \leq s$, such that $a_i$ is not larger than $b_1$. Then $\{a_i>a, b>b_1\}$ forms a $(\bm{2}+\bm{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 $(\bm{2}+\bm{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. \end{proof} We are now ready to deduce the recurrence formula (\ref{5.1}). 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, \dots, 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^{\mathrm{th}}$ level. \begin{itemize} \item If $l=1$, let the new element be larger than all elements on the $i^{\mathrm{th}}$ level, $i \geq 3$, and be not comparable with any other element. \item If $l\geq2$, and the $(l-1)^{\mathrm{th}}$ level originally has at least one element, we let the new element be smaller than all elements on the $(l-1)^{\mathrm{th}}$ level, be larger than all elements on the $i^{\mathrm{th}}$ level, $i \geq l+2$, and be not comparable with any other element. \item If $l\geq2$, and the $(l-1)^{\mathrm{th}}$ level originally has no element, we \emph{hang} the new element on the $l^{\mathrm{th}}$ level, that is, we place it as an isolated vertex on the $l^{\mathrm{th}}$ level. We then call the new semiorder an \emph{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 \emph{disguise} of $r_0$. \end{itemize} By Definition \ref{badelement}, 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, \dots, h+1$. Therefore, including multiplicity and the invalid ones, we can obtain $\binom{h+2-k}{k}\cdot f_{\leq h}^{n-k}$ $n$-element semiorders from $(n-k)$-element semiorders by adjoining $k$ elements. Let $\mathcal{S}^k$ be the set of all such $n$-element semiorders, including multiplicity. Then $|\mathcal{S}^k|=\binom{h+2-k}{k}\cdot f_{\leq h}^{n-k}$. Let $\mathcal{R}$ be the set of all $n$-element semiorders of length at most $h$, and $\mathcal{R'}$ be the set of all semiorders with at most $n-1$ elements and length at most $h$. By Proposition \ref{5.3}, every semiorder has bad elements, so every semiorder $r\in \mathcal{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\in\mathcal{S}^k$, for some $1 \leq k \leq \lfloor \frac{h+2}{2} \rfloor$. However, $r$ might be in $\mathcal{S}^k$ for multiple $k$'s, and $r$ may have multiple copies in $\mathcal{S}^k$. Meanwhile, $\mathcal{S}^k$ may contain some semiorders not in $\mathcal{R}$, but are the disguises of some semiorders $r' \in \mathcal{R'}$. Notice that $|\mathcal{R}|=f_{\leq h}^n$. In the following argument, we calculate the number of copies of a semiorder in each $\mathcal{S}^k$ and obtain a formula connecting $|\mathcal{R}|$ and $|\mathcal{S}^k|$, $1 \leq k \leq \lfloor \frac{h+2}{2} \rfloor$. For a semiorder $r_0\in \mathcal{R} \cup \mathcal{R'}$, let $\mathcal{S}_{r_0}^k$ be the set of all semiorders in $\mathcal{S}^k$ which are equal to $r_0$ or a disguise of $r_0$. Then $\mathcal{S}^k = \bigcup_{r \in \mathcal{R} \cup \mathcal{R'}} \mathcal{S}_r^k$, and \begin{equation}\label{SR} \sum_{r \in \mathcal{R} \cup \mathcal{R'}} |\mathcal{S}_r^k| =|\mathcal{S}^k|=\binom{h+2-k}{k}\cdot f_{\leq h}^{n-k}. \end{equation} Next, we show that $\sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_r^k|=1$, for every $r \in \mathcal{R}$, and $\sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_{r'}^{k}|=0$, for every $r'\in\mathcal{R'}$. 1. For a semiorder $r\in \mathcal{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 \leq m$. Further notice that for a given $k$, $1\leq k \leq 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 $|\mathcal{S}_r^k|=\binom{m}{k}\cdot 1$, and \begin{equation} \label{R} \sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_r^k|=\sum_{k=1}^{m}(-1)^{k-1}|\mathcal{S}_r^k|=\sum_{k=1}^{m}(-1)^{k-1}\binom{m}{k}\cdot1=1. \end{equation} 2. For a semiorder $r'\in \mathcal{R'}$, assume $r'$ has $n'$ elements, $m'$ of which are bad. Further assume that semiorder $r'$ has length $h'$. For a given $k$, $1\leq k \leq \lfloor\frac{h+2}{2}\rfloor$, 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, \dots, h+1$. As a result, $\left \lceil \frac{h-h'}{2} \right \rceil \geq 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, \dots, 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, \dots, h+1$. Thus, $$|\mathcal{S}_{r'}^k|=|S_{r'}^{t'-n'+n}|= \binom{m'}{t'}\cdot\binom{h-h'+1-(n-n')}{n-n'}\cdot 1.$$ Then \begin{align}\label{Rr} \sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_{r'}^k| &=\sum_{t'=0}^{m'}(-1)^{t'-n'+n-1}|\mathcal{S}_{r'}^{t'-n'+n}|\notag\\ &=\sum_{t'=0}^{m'}(-1)^{t'-n'+n-1}\binom{m'}{t'}\cdot \binom{h-h'+1-(n-n')}{n-n'}\cdot 1\notag\\ &=(-1) ^{n-n'-1}\cdot \binom{h-h'+1-(n-n')}{n-n'} \sum_{t'=0}^{m'}(-1)^{t'}\binom{m'}{t'}=0. \end{align} However, we should be careful with the special case when $t' \geq 1$ and the $(h'+1)^{\mathrm{th}}$ level of $r'$ has bad elements. In this case, the $(h'+1)^{\mathrm{th}}$ level and the $(h'+2)^{\mathrm{th}}$ level might be both chosen when we choose $n-n'$ nonadjacent levels among levels $h'+2, h'+3, \dots, h+1$ and choose $t'$ levels among the $m'$ levels where bad elements are (note that here the $(h'+1)^{\mathrm{th}}$ level is among the $m'$ levels). Further notice that $\mathcal{S}_{r'}^k \in \mathcal{S}^k$ and $\mathcal{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 $|\mathcal{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' \geq 1$ and the $(h'+1)^{\mathrm{th}}$ level of $r'$ has bad elements, \begin{align*} |\mathcal{S}_{r'}^k|&=|\mathcal{S}_{r'}^{t'-n'+n}|\\ &=\binom{m'}{t'}\cdot\binom{h-h'+1-(n-n')}{n-n'}\cdot 1 -\binom{m'-1}{t'-1}\cdot\binom{h-h'-1-(n-n'-1)}{n-n'-1}\cdot 1 \end{align*} By similar calculations, we have $\sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_{r'}^k|=0$. To conclude the proof, by equations (\ref{SR}), (\ref{R}), and (\ref{Rr}), we have \begin{align*} f_{\leq h}^{n} = |\mathcal{R}| = \sum _{r\in \mathcal{R}} 1 + \sum_{r'\in \mathcal{R'}} 0 &= \sum_{r\in \mathcal{R}} \sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_r^k|+\sum_{r'\in \mathcal{R'}} \sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}|\mathcal{S}_{r'}^k|\\ &=\sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}\sum_{r\in \mathcal{R}\cup \mathcal{R'}} |\mathcal{S}_{r}^k|\\&=\sum_{k=1}^{\lfloor\frac{h+2}{2}\rfloor}(-1)^{k-1}\binom{h+2-k}{k}\cdot f_{\leq h}^{n-k}. \end{align*} \end{proof} \section{The Number of Semiorders of Small Length}\label{sec6} 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. \subsection{$f_{\leq 1}^n$, the number of nonisomorphic unlabeled $n$-element semiorders of length at most one} \begin{theorem}\label{f1n} For $n\geq 1$, $f_{\leq 1}^n=2^{n-1}$. \end{theorem} We give a simple bijective proof here. \begin{proposition} For $n$ elements $a_1, a_2, \dots, a_n$, put $a_1$ on the upper level, and each of $a_2, \dots, 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 a_j$, $a_k>a_m$, $a_i\sim a_k$, $a_i\sim a_m$, $a_k\sim a_j$, $a_m\sim 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 m$; since $a_k\sim 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 $\rho(r)=(r_1, r_2, \dots, r_n)$. Then $r_{m+1} = r_{m+2} = \dots = r_n=0$. Say element $a_{t_i}$ corresponds to $r_i$, $1 \leq i\leq 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}, \dots, 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. \end{proof} As an example, if we have $(r_1, r_2, \dots, 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, \dots, 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. \subsection{The number of nonisomorphic trees derived from semiorders of length at most one}\label{tree} 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 $\rho(S)=(r_1, r_2, \dots, r_m, 0, 0, \dots, 0)$, where there are $n-m$ $0$'s and $n-m\geq r_1 \geq r_2 \geq \dots \geq r_m \geq 0$. Let the elements of the semiorder be $s_1, s_2, \dots, s_n$, with $s_i$ corresponding to $r_i$, $1\leq i \leq m$, and then $s_1, s_2, \dots, s_m$ are on the upper level. For a permutation $\sigma=(a_1, a_2, \dots, a_m)$ of $\{1, 2, \dots, m\}$, if we add the relations $s_{a_1}>s_{a_2}>\dots>s_{a_m}$ to the original semiorder, we get a tree with the main trunk $s_{a_1}>s_{a_2}>\dots>s_{a_m}$, and the elements $s_{m+1}, s_{m+2}, \dots, s_n$ attached to one of the elements on the main trunk in the following manner. For $m+1\leq i \leq 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\leq j \leq m$. We denote the tree derived from semiorder $S$ and permutation $\sigma$ by $T(S, \sigma)$. For example, the Hasse diagram of the semiorder $S$ with $\rho(S)=(7, 5, 4, 2, 1, 0, 0, 0, 0, 0, 0)$ is as follows: $$ \xy 0;/r.45pc/: (0,0)*{\bullet}="a"; (5,0)*{\bullet}="b"; (10,0)*{\bullet}="c"; (15,0)*{\bullet}="d"; (20,0)*{\bullet}="e"; (0,-10)*{\bullet}="f"; (5,-10)*{\bullet}="g"; (10,-10)*{\bullet}="h"; (15,-10)*{\bullet}="i"; (20,-10)*{\bullet}="j"; (25,-10)*{\bullet}="k"; (30,-10)*{\bullet}="l"; (-1,1)*{s_1}; (4,1)*{s_2}; (9,1)*{s_3}; (14,1)*{s_4}; (19,1)*{s_5}; (-1,-11)*{s_6}; (4,-11)*{s_7}; (9,-11)*{s_8}; (14,-11)*{s_9}; (19,-11)*{s_{10}}; (24,-11)*{s_{11}}; (29,-11)*{s_{12}}; "a";"f"**\dir{-}; "a";"g"**\dir{-}; "a";"h"**\dir{-}; "a";"i"**\dir{-}; "a";"j"**\dir{-}; "a";"k"**\dir{-}; "a";"l"**\dir{-}; "b";"h"**\dir{-}; "b";"i"**\dir{-}; "b";"j"**\dir{-}; "b";"k"**\dir{-}; "b";"l"**\dir{-}; "c";"i"**\dir{-}; "c";"j"**\dir{-}; "c";"k"**\dir{-}; "c";"l"**\dir{-}; "d";"k"**\dir{-}; "d";"l"**\dir{-}; "e";"l"**\dir{-}; \endxy$$ \vspace{6pt} Suppose that $\sigma=(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,\sigma)$ is $$ \xy 0;/r.35pc/: (0,0)*{\bullet}="a"; (0,-21)*{\bullet}="b"; (0,-14)*{\bullet}="c"; (0,-28)*{\bullet}="d"; (0,-7)*{\bullet}="e"; (7,-3)*{\bullet}="f"; (5,-5)*{\bullet}="g"; (7,-24)*{\bullet}="h"; (6,-25)*{\bullet}="i"; (5,-26)*{\bullet}="j"; (7,-31)*{\bullet}="k"; (5,-33)*{\bullet}="l"; (-2,1)*{s_1}; (-2,-20)*{s_2}; (-2,-13)*{s_3}; (-2,-27)*{s_4}; (-2,-6)*{s_5}; (9,-4)*{s_6}; (7,-6)*{s_7}; (9,-24)*{s_8}; (8,-26)*{s_9}; (6,-27.5)*{s_{10}}; (9,-32)*{s_{11}}; (7,-34)*{s_{12}}; "a";"e"**\dir{-}; "a";"f"**\dir{-}; "a";"g"**\dir{-}; "e";"c"**\dir{-}; "c";"b"**\dir{-}; "b";"d"**\dir{-}; "b";"h"**\dir{-}; "b";"i"**\dir{-}; "b";"j"**\dir{-}; "d";"k"**\dir{-}; "d";"l"**\dir{-}; \endxy$$ 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. \begin{theorem}\label{catalan} Given an $n$-element semiorder $R_{m}$ of length at most one and exactly $m$ elements on the first level, let $\rho(R_{m})=(r_1, r_2, \dots, r_n)$. If $r_i \neq r_j$ for any $1 \leq i < j \leq m$, then the number of nonisomorphic unlabeled trees in $\{T(R_{m}, \sigma) | \sigma \in S_m\}$ is the Catalan number $C_m$. \end{theorem} \begin{proof} A permutation $\sigma=(a_1, a_2, \dots, a_m)$ of $\{1, 2, \dots, m\}$ uniquely determines the main trunk. For $m+1\leq i\leq n$, assume element $s_i$ is smaller than $t_i$ elements. Then $s_i$ must be smaller than $s_1, s_2, \dots, 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, \dots, 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, \dots, s_t$, for some $1\leq t \leq m$. In other words, assume $b_1 < b_2< \dots < b_k$ are the set of right-to-left minima of the permutation $\sigma=(a_1, a_2, \dots, a_m)$, and then only the elements $s_{b_1}, s_{b_2}, \dots, s_{b_k}$ may have leaves. Further notice that the numbers of leaves attached to $s_{b_1}, s_{b_2}, \dots, s_{b_k}$ are $r_{b_1}-r_{b_2}, r_{b_2}-r_{b_3}, \dots, r_{b_{k-1}}-r_{b_k}, r_{b_k}$, respectively, and $r_i \neq r_j$ for any $1 \leq i < j \leq 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 $\sigma=(a_1, a_2, \dots, a_m)$ uniquely determines $T(R_m,\sigma)$. For instance, in the example above, we have $\sigma=(1, 5, 3, 2, 4)$ and $\rho(R_5)=(r_1, r_2, \dots, r_{12})=(7, 5, 4, 2, 1, 0, 0, 0, 0, 0, 0, 0)$. The right-to-left-minima of $\sigma$ and their positions with $\sigma$ is given by $1, \ast, \ast, 2, 4$. Then the corresponding tree $T(R_5, \sigma)$ 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}, \sigma) | \sigma \in S_m\}$ is equal to the number of ways to specify the values and positions of the right-to-left minima of permutations $\sigma \in S_m$. That is, if we let $RtLM(\sigma)=\{(a,\sigma(a)) | 1\leq a \leq m, \sigma(a) \text{ is a right-to-left minima in }\sigma\}$, then $\#\{T(R_{m}, \sigma) | \sigma \in S_m\}=\#\{RtLM(\sigma) | \sigma \in S_m\}$. We calculate $\#\{RtLM(\sigma) | \sigma \in S_m\}$ in the following lemma. \begin{lemma}\label{Narayana} Let $RL(\sigma)$ be the number of right-to-left minima of the permutation $\sigma$. For $1\leq k \leq m$, let $f(m,k)=\#\{RtLM(\sigma) | \sigma \in S_m, RL(\sigma)=k\}$. Then $f(m,k)=N(m,k)=\frac{1}{m}\binom{m}{k}\binom{m}{k-1}$, a Narayana number. \end{lemma} For example, for $m=3$ and $k=2$, $f(3,2)=\#\{RtLM(\sigma) | \sigma \in S_3, RL(\sigma)=2\}=\#\{RtLM(\sigma) | \sigma=(23), (12), \text{or }(132)\}=\#\{\{(3,2), (1,1)\}, \{(3,3), (2,1)\}, \{(3,2), (2,1)\}\}=3$. \begin{proof} For $1 \leq k \leq 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(\sigma)$'s for $\sigma \in S_m, RL(\sigma)=k$. We define a map from (i) to (ii) as follows: \vspace{6pt} Given a Dyck path of semilength $m$ with $k$ peaks, let us read the Dyck path from left to right and do the following: \begin{itemize} \item 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. \item 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. \item 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^{\mathrm{th}}$ endpoint and the $j^{\mathrm{th}}$ startpoint. Assume the coordinate of the $k$ peaks are $(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$. Then $a_1 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 \leq i \leq k$, there does not exist some $1\leq i'\leq k$ such that $b_{i'} a_i$. In addition, if there exists some $1\leq j \leq m-k$ such that $d_{j}=\sigma(c_j) c_j>a_i$. We obtain a contradiction. As a result, $RtLM(\sigma)=\{(a_i, b_i), 1\leq i \leq k\}$. For example, let us construct the permutation $\sigma$ 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 $\sigma=(2, 5, 1, 3, 6, 4, 7)$, and this permutation exactly corresponds to the right-to-left minima as shown in Example \ref{permutation}. \item 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\leq i \leq k\}=RtLM(\sigma)$, for some $\sigma \in S_m$, we have $a_1