2011/06/11 by Vít Jelínek · 21 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Bijection #Combinatorics #Computer science #Discrete mathematics #Dual (grammatical number) #Enumeration #Function (biology) #Generating function #Interval (graph theory) #Mathematics #Pure mathematics #Row #Row and column spaces #Triangular matrix #Zero (linguistics) #math.CO #semigroups and automata theory
paper · pdf · doi:10.1016/j.jcta.2011.11.010
published in Journal of Combinatorial Theory Series A 119(3), 599-614 (Elsevier BV) · 20 pages
arxiv created 2011/06/11 · openalex publication_date 2011/11/22 · arxiv updated 2011/11/28 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
In this paper, we present a new method to derive formulas for the generating functions of interval orders, counted with respect to their size, magnitude, and number of minimal and maximal elements. Our method allows us not only to generalize previous results on refined enumeration of general interval orders, but also to enumerate self-dual interval orders with respect to analogous statistics. Using the newly derived generating function formulas, we are able to prove a bijective relationship between self-dual interval orders and upper-triangular matrices with no zero rows. Previously, a similar bijective relationship has been established between general interval orders and upper-triangular matrices with no zero rows and columns.