Partition and composition matrices : two matrix analogues of set partitions
Claesson, Anders and Dukes, Mark and Kubitzke, Martina (2011) Partition and composition matrices : two matrix analogues of set partitions. In: DMTCS Proceedings. Discrete Mathematics & Theoretical Computer Science, Nancy, France, pp. 221-232.
Full text not available in this repository.Request a copy from the Strathclyde authorAbstract
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}.
| Author(s): | Claesson, Anders  ORCID: https://orcid.org/0000-0001-5797-8673, Dukes, Mark ORCID: https://orcid.org/0000-0002-2779-2680 and Kubitzke, Martina | Item type: | Book Section |
|---|---|
| ID code: | 51016 |
| Keywords: | partition matrix, composition matrix, ascent sequence, inversion table, Electronic computers. Computer science, Computational Theory and Mathematics |
| Subjects: | Science > Mathematics > Electronic computers. Computer science |
| Department: | Faculty of Science > Computer and Information Sciences |
| Depositing user: | Pure Administrator |
| Date deposited: | 12 Jan 2015 19:47 |
| Last modified: | 18 Sep 2019 00:18 |
| Related URLs: | |
| URI: | https://strathprints.strath.ac.uk/id/eprint/51016 |
| Export data: |
CORE (COnnecting REpositories)
CORE (COnnecting REpositories)