### Abstract

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

Original language | English |
---|---|

Pages (from-to) | 1624-1637 |

Number of pages | 14 |

Journal | Journal of Combinatorial Theory Series A |

Volume | 118 |

Issue number | 5 |

DOIs | |

Publication status | Published - Jul 2011 |

### Fingerprint

### Keywords

- partition matrix
- composition matrix
- ascent sequences
- inversion table
- permutation
- (2+2)-free poset

### Cite this

*Journal of Combinatorial Theory Series A*,

*118*(5), 1624-1637 . https://doi.org/10.1016/j.jcta.2011.02.001

}

*Journal of Combinatorial Theory Series A*, vol. 118, no. 5, pp. 1624-1637 . https://doi.org/10.1016/j.jcta.2011.02.001

**Partition and composition matrices.** / Claesson, Anders; Dukes, Mark; Kubitzke, Martina .

Research output: Contribution to journal › Article

TY - JOUR

T1 - Partition and composition matrices

AU - Claesson, Anders

AU - Dukes, Mark

AU - Kubitzke, Martina

PY - 2011/7

Y1 - 2011/7

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

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

KW - partition matrix

KW - composition matrix

KW - ascent sequences

KW - inversion table

KW - permutation

KW - (2+2)-free poset

UR - http://www.scopus.com/inward/record.url?scp=79951982755&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2011.02.001

DO - 10.1016/j.jcta.2011.02.001

M3 - Article

VL - 118

SP - 1624

EP - 1637

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

IS - 5

ER -