Mathematics – Combinatorics
Scientific paper
2010-06-07
Journal of Combinatorial Theory Series A 118 (2011), no. 5, 1624-1637
Mathematics
Combinatorics
14 pages
Scientific paper
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}.
Claesson Anders
Dukes Mark
Kubitzke Martina
No associations
LandOfFree
Partition and composition matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Partition and composition matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partition and composition matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-367615