### Abstract

Language | English |
---|---|

Title of host publication | DMTCS Proceedings |

Subtitle of host publication | 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) |

Place of Publication | Nancy, France |

Pages | 221-232 |

Number of pages | 12 |

Volume | AO |

Publication status | Published - 2011 |

### Fingerprint

### Keywords

- partition matrix
- composition matrix
- ascent sequence
- inversion table

### Cite this

*DMTCS Proceedings: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)*(Vol. AO, pp. 221-232). Nancy, France.

}

*DMTCS Proceedings: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011).*vol. AO, Nancy, France, pp. 221-232.

**Partition and composition matrices : two matrix analogues of set partitions.** / Claesson, Anders; Dukes, Mark; Kubitzke, Martina .

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Partition and composition matrices

T2 - two matrix analogues of set partitions

AU - Claesson, Anders

AU - Dukes, Mark

AU - Kubitzke, Martina

PY - 2011

Y1 - 2011

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

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

KW - partition matrix

KW - composition matrix

KW - ascent sequence

KW - inversion table

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAO0121

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs

M3 - Chapter

VL - AO

SP - 221

EP - 232

BT - DMTCS Proceedings

CY - Nancy, France

ER -