Decomposing labeled interval orders as pairs of permutations

Anders Claesson, Stuart A. Hannah

Research output: Contribution to journalArticlepeer-review

62 Downloads (Pure)


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
Issue number4
Publication statusPublished - 16 Oct 2014


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


Dive into the research topics of 'Decomposing labeled interval orders as pairs of permutations'. Together they form a unique fingerprint.

Cite this