Partition and composition matrices

Anders Claesson, Mark Dukes, Martina Kubitzke

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.

We show 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 X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, 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
Pages (from-to)1624-1637
Number of pages14
JournalJournal of Combinatorial Theory Series A
Volume118
Issue number5
DOIs
Publication statusPublished - Jul 2011

Keywords

  • partition matrix
  • composition matrix
  • ascent sequences
  • inversion table
  • permutation
  • (2+2)-free poset

Fingerprint Dive into the research topics of 'Partition and composition matrices'. Together they form a unique fingerprint.

  • Cite this