Semiorders and Riordan Numbers
Barry Balof and Jacob Menashe
Department of Mathematics 
Whitman College 
Walla Walla, WA  99362
USA 
Abstract:
In this paper, we define a class of semiorders (or unit interval
orders) that arose in the context of polyhedral combinatorics.  In the
first section of the paper, we will present a pure counting argument
equating the number of these interesting (connected and irredundant)
semiorders on n+1 elements with the nth Riordan number.  In the
second section, we will make explicit the relationship between the
interesting semiorders and a special class of Motzkin paths, namely,
those Motzkin paths without horizontal steps of height 0, which are
known to be counted by the Riordan numbers.
Full version:  pdf,   
dvi,   
ps,   
latex    
(Concerned with sequences
A000108 and
A005043
.)
Received February 14 2007;
revised version received July 18 2007.
Published in Journal of Integer Sequences, July 23 2007.
Return to
Journal of Integer Sequences home page