Partition and composition matrices

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Claesson, Anders¹  Dukes, Mark¹  Kubitzke, Martina² 

[1] Univ Strathclyde, Dept Comp & Informat Sci, Glasgow G1 1XH, Lanark, Scotland

[2] Univ Vienna, Fak Math, A-1090 Vienna, Austria

关键词: Partition matrix;    Composition matrix;    Ascent sequence;    Inversion table;    Permutation;    (2+2)-free poses;   

DOI  :  10.1016/j.jcta.2011.02.001

来源: Elsevier

【 摘 要 】

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 posers 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). (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free