Geodesic
On the number of fixed-length semiorders
Journal of integer sequences, Tome 17 (2014) no. 1
A semiorder is a partially ordered set $P$ with two certain forbidden induced sub-posets. 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.
Classification : 05A15, 05A19
Keywords: semiorder, ordered tree, Dyck path 
@article{JIS_2014__17_1_a3,
     author = {Hu,  Yangzhou},
     title = {On the number of fixed-length semiorders},
     journal = {Journal of integer sequences},
     year = {2014},
     volume = {17},
     number = {1},
     zbl = {1292.05026},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2014__17_1_a3/}
}
TY  - JOUR
AU  - Hu,  Yangzhou
TI  - On the number of fixed-length semiorders
JO  - Journal of integer sequences
PY  - 2014
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/JIS_2014__17_1_a3/
LA  - en
ID  - JIS_2014__17_1_a3
ER  - 
%0 Journal Article
%A Hu,  Yangzhou
%T On the number of fixed-length semiorders
%J Journal of integer sequences
%D 2014
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/JIS_2014__17_1_a3/
%G en
%F JIS_2014__17_1_a3
Hu,  Yangzhou. On the number of fixed-length semiorders. Journal of integer sequences, Tome 17 (2014) no. 1. http://geodesic.mathdoc.fr/item/JIS_2014__17_1_a3/