Authors: Anders Claesson ¹; Mark Dukes ¹; Martina Kubitzke ²

• 1 Department of Computer and Information Sciences [Univ Strathclyde]
• 2 Fakultät für Mathematik [Wien]

This paper introduces two matrix analogues for set partitions; partition and composition matrices. These two analogues are the natural result of lifting the mapping between ascent sequences and integer matrices given in Dukes & Parviainen (2010). We prove that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel. We show that composition matrices on the set $X$ are in one-to-one correspondence with (2+2)-free posets on $X$.We show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on $\{1,\ldots,n\}$.