Balof, Barry; Menashe, Jacob

Semiorders and Riordan numbers

J. Integer Seq. 10(7), Article 07.7.6, 18 p., electronic only (2007)


Summary: 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 $n$th 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.

Mathematics Subject Classification

05A15, 06A07


riordan numbers, interval orders, semiorders, lattice paths