Decomposing labeled interval orders as pairs of permutations

Anders Claesson, Stuart Alexander Hannah

Research output: Contribution to journalArticle

52 Downloads (Pure)

Abstract

We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.
Original languageEnglish
Article numberP4.16
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number4
Publication statusPublished - 16 Oct 2014

Keywords

  • ballot matrix
  • composition matrix
  • sign reversing involution
  • interval order
  • 2+2-free posset
  • ascent bottom

Cite this