Partition and composition matrices
From MaRDI portal
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}.
Recommendations
- scientific article; zbMATH DE number 6683578
- Composition matrices, \((2+2)\)-free posets and their specializations
- Ascent sequences and upper triangular matrices containing non-negative integers
- Enumerating \((2 + 2)\)-free posets by indistinguishable elements
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
Cites work
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- $n!$ matchings, $n!$ posets
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
- Ascent sequences and upper triangular matrices containing non-negative integers
- Combinatorial problems of commutation and rearrangements
- Enumerating \((2 + 2)\)-free posets by indistinguishable elements
- Enumerative combinatorics. Volume 2.
- Pop-stacks in parallel
- The On-Line Encyclopedia of Integer Sequences
- The enumeration of permutations sortable by pop stacks in parallel
- Vassiliev invariants and a strange identity related to the Dedekind eta-function
Cited in
(9)- Web worlds, web-colouring matrices, and web-mixing matrices
- Weak ascent sequences and related combinatorial structures
- Concerning partition regular matrices
- Decomposing labeled interval orders as pairs of permutations
- Refining the bijections among ascent sequences, \((2+2)\)-free posets, integer matrices and pattern-avoiding permutations
- Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Matrix relationships for partition functions
- Composition matrices, \((2+2)\)-free posets and their specializations
This page was built for publication: Partition and composition matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533343)
