Discrete Mathematics & Theoretical Computer Science 
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 onetoone correspondence with inversion tables. Nondecreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are sdiagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfermatrix method and are equinumerous with permutations which are sortable by two popstacks in parallel. We show that composition matrices on the set $X$ are in onetoone correspondence with (2+2)free posets on $X$.We show that pairs of ascent sequences and permutations are in onetoone 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,\ldots,n\}$.
Source : ScholeXplorer
IsRelatedTo ARXIV 1003.4728 Source : ScholeXplorer IsRelatedTo DOI 10.1090/s000299392010106780 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1003.4728
