Partition and composition matrices

Anders Claesson, Mark Dukes, Martina Kubitzke

Research output: Contribution to journalArticle

8 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

Fingerprint

Partition
Chemical analysis
One to one correspondence
Poset
Tables
Inversion
Permutation
Parking Functions
Set Partition
Null set or empty set
Upper triangular matrix
Transfer Matrix Method
Ascent
Transfer matrix method
Parking
Finite Set
Analogue
Cycle

Keywords

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

Cite this

Claesson, Anders ; Dukes, Mark ; Kubitzke, Martina . / Partition and composition matrices. In: Journal of Combinatorial Theory Series A . 2011 ; Vol. 118, No. 5. pp. 1624-1637 .
@article{7be79a62264c4326a55ab0458c7f34e3,
title = "Partition and composition matrices",
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}.",
keywords = "partition matrix, composition matrix, ascent sequences, inversion table, permutation, (2+2)-free poset",
author = "Anders Claesson and Mark Dukes and Martina Kubitzke",
year = "2011",
month = "7",
doi = "10.1016/j.jcta.2011.02.001",
language = "English",
volume = "118",
pages = "1624--1637",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",
number = "5",

}

Claesson, A, Dukes, M & Kubitzke, M 2011, 'Partition and composition matrices', Journal of Combinatorial Theory Series A , vol. 118, no. 5, pp. 1624-1637 . https://doi.org/10.1016/j.jcta.2011.02.001

Partition and composition matrices. / Claesson, Anders; Dukes, Mark; Kubitzke, Martina .

In: Journal of Combinatorial Theory Series A , Vol. 118, No. 5, 07.2011, p. 1624-1637 .

Research output: Contribution to journalArticle

TY - JOUR

T1 - Partition and composition matrices

AU - Claesson, Anders

AU - Dukes, Mark

AU - Kubitzke, Martina

PY - 2011/7

Y1 - 2011/7

N2 - 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}.

AB - 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}.

KW - partition matrix

KW - composition matrix

KW - ascent sequences

KW - inversion table

KW - permutation

KW - (2+2)-free poset

UR - http://www.scopus.com/inward/record.url?scp=79951982755&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2011.02.001

DO - 10.1016/j.jcta.2011.02.001

M3 - Article

VL - 118

SP - 1624

EP - 1637

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

IS - 5

ER -