Generation and Enumeration of Some Classes of Interval Orders |
| |
Authors: | F Disanto E Pergola R Pinzani S Rinaldi |
| |
Institution: | 1. Dipartimento di Scienze Matematiche e Informatiche, Università di Siena, Pian dei Mantellini 44, Siena, Italy 2. Dipartimento di Sistemi e Informatica, Università di Firenze, Viale Morgagni 65, Firenze, Italy
|
| |
Abstract: | In this paper we consider the class of interval orders, recently considered by several authors from both an algebraic and an enumerative point of view. According to Fishburn’s Theorem (Fishburn J Math Psychol 7:144–149, 1970), these objects can be characterized as posets avoiding the poset 2?+?2. We provide a recursive method for the unique generation of interval orders of size n?+?1 from those of size n, extending the technique presented by El-Zahar (1989) and then re-obtain the enumeration of this class, as done in Bousquet-Melou et al. (2010). As a consequence we provide a method for the enumeration of several subclasses of interval orders, namely AV(2?+?2, N), AV(2?+?2, 3?+?1), AV(2?+?2, N, 3?+?1). In particular, we prove that the first two classes are enumerated by the sequence of Catalan numbers, and we establish a bijection between the two classes, based on the cardinalities of the principal ideals of the posets. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|