Partition and composition matrices: two matrix analogues of set partitions

Anders Claesson, Mark Dukes, Martina Kubitzke

Research output: Chapter in Book/Report/Conference proceedingChapter

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,…,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
Pages221-232
Number of pages12
VolumeAO
Publication statusPublished - 2011

    Fingerprint

Keywords

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

Cite this

Claesson, A., Dukes, M., & Kubitzke, M. (2011). Partition and composition matrices: two matrix analogues of set partitions. In DMTCS Proceedings: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (Vol. AO, pp. 221-232). Nancy, France.