Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Partition and composition matrices

Claesson, Anders and Dukes, Mark and Kubitzke, Martina (2011) Partition and composition matrices. Journal of Combinatorial Theory Series A, 118 (5). pp. 1624-1637.

Full text not available in this repository. (Request a copy from the Strathclyde author)

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

Item type: Article
ID code: 34507
Keywords: partition matrix, composition matrix, ascent sequences, inversion table, permutation, (2+2)-free poset, Electronic computers. Computer science, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, Theoretical Computer Science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
Depositing user: Pure Administrator
Date Deposited: 21 Oct 2011 09:50
Last modified: 27 Mar 2014 09:42
URI: http://strathprints.strath.ac.uk/id/eprint/34507

Actions (login required)

View Item