## Anders Claesson ; Mark Dukes ; Martina Kubitzke - Partition and composition matrices: two matrix analogues of set partitions

dmtcs:2905 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) - https://doi.org/10.46298/dmtcs.2905
Partition and composition matrices: two matrix analogues of set partitions

Authors: Anders Claesson ; Mark Dukes ; Martina Kubitzke

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\}$.

Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
Keywords: partition matrix,composition matrix,ascent sequence,inversion table,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]