Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.6

On the Number of Fixed-Length Semiorders

Yangzhou Hu
Department of Mathematics
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence 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