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

Chemical analysis
Transfer matrix method

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.
Claesson, Anders ; Dukes, Mark ; Kubitzke, Martina . / Partition and composition matrices : two matrix analogues of set partitions. DMTCS Proceedings: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011). Vol. AO Nancy, France, 2011. pp. 221-232
@inbook{9a888c4f34214e9ab6913d0c2ea033ef,
title = "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,…,n}.",
keywords = "partition matrix, composition matrix, ascent sequence, inversion table",
author = "Anders Claesson and Mark Dukes and Martina Kubitzke",
year = "2011",
language = "English",
volume = "AO",
pages = "221--232",
booktitle = "DMTCS Proceedings",

}

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, Nancy, France, pp. 221-232.

Partition and composition matrices : two matrix analogues of set partitions. / Claesson, Anders; Dukes, Mark; Kubitzke, Martina .

DMTCS Proceedings: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011). Vol. AO Nancy, France, 2011. p. 221-232.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Partition and composition matrices

T2 - two matrix analogues of set partitions

AU - Claesson, Anders

AU - Dukes, Mark

AU - Kubitzke, Martina

PY - 2011

Y1 - 2011

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

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

KW - partition matrix

KW - composition matrix

KW - ascent sequence

KW - inversion table

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAO0121

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs

M3 - Chapter

VL - AO

SP - 221

EP - 232

BT - DMTCS Proceedings

CY - Nancy, France

ER -

Claesson A, Dukes M, Kubitzke M. 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. Nancy, France. 2011. p. 221-232