Journal of Integer Sequences, Vol. 10 (2007), Article 07.7.6

Semiorders and Riordan Numbers

Barry Balof and Jacob Menashe
Department of Mathematics
Whitman College
Walla Walla, WA 99362


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