### 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 |

Publication status | Published - 16 Oct 2014 |

### Keywords

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

## Cite this

Claesson, A., & Hannah, S. A. (2014). Decomposing labeled interval orders as pairs of permutations.

*The Electronic Journal of Combinatorics*,*21*(4), [P4.16].