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 language | English |
---|---|
Article number | P4.16 |
Number of pages | 20 |
Journal | The Electronic Journal of Combinatorics |
Volume | 21 |
Issue number | 4 |
DOIs | |
Publication status | Published - 16 Oct 2014 |
Keywords
- ballot matrix
- composition matrix
- sign reversing involution
- interval order
- 2+2-free posset
- ascent bottom