Skip to Main content Skip to Navigation
Conference papers

Partition and composition matrices: two matrix analogues of set partitions

Abstract : 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\}$.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, October 13, 2015 - 3:06:42 PM
Last modification on : Wednesday, November 25, 2020 - 5:10:02 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:08:52 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01215096, version 1



Anders Claesson, Mark Dukes, Martina Kubitzke. Partition and composition matrices: two matrix analogues of set partitions. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.221-232. ⟨hal-01215096⟩



Record views


Files downloads