Partition and composition matrices: two matrix analogues of set partitions

Anders Claesson, Mark Dukes, Martina Kubitzke

Research output: Chapter in Book/Report/Conference proceedingChapter


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,…,n}.
Original languageEnglish
Title of host publicationDMTCS Proceedings
Subtitle of host publication23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Place of PublicationNancy, France
Number of pages12
Publication statusPublished - 2011


  • partition matrix
  • composition matrix
  • ascent sequence
  • inversion table


Dive into the research topics of 'Partition and composition matrices: two matrix analogues of set partitions'. Together they form a unique fingerprint.

Cite this