On the Number of Fixed-Length Semiorders
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,
(Concerned with sequence
Received June 26 2013;
revised versions received October 28 2013; November 25 2013.
Published in Journal of Integer Sequences, December 16 2013.
Journal of Integer Sequences home page