(2+2)-free posets, ascent sequences and pattern avoiding permutations

Abstract

We present bijections between four classes of combinatorial objects. Two of them, the class of unlabeled (2+2)-free posets and a certain class of involutions (or chord diagrams), already appeared in the literature, but were apparently not known to be equinumerous. We present a direct bijection between them. The third class is a family of permutations defined in terms of a new type of pattern. An attractive property of these patterns is that, like classical patterns, they are closed under the action of $D_8$, the symmetry group of the square. The fourth class is formed by certain integer sequences, called ascent sequences, which have a simple recursive structure and are shown to encode (2+2)-free posets and permutations. Our bijections preserve numerous statistics. We determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for the class of chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3\bar{1}52\bar{4}$ and use this to enumerate those permutations, thereby settling a conjecture of Pudwell.

Cited by in corpus (25)

• Patterns in Inversion Sequences I
• Counting Self-Dual Interval Orders
• The computational landscape of permutation patterns
• Shape-Wilf-equivalences for vincular patterns
• Enumeration of Graded (3+1)-Avoiding Posets
• Asymptotics of the Extremal Excedance Set Statistic
• Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q,t-Narayana polynomial
• Web worlds, web-colouring matrices, and web-mixing matrices
• Congruences for Fishburn numbers modulo prime powers
• Structure and enumeration of (3+1)-free posets
• Permutation classes and polyomino classes with excluded submatrices
• Asymptotics and statistics on Fishburn matrices and their generalizations
• On the Number of Fixed-Length Semiorders
• Coxeter-biCatalan combinatorics
• Ascent sequences avoiding pairs of patterns
• Partitions and Partial Matchings Avoiding Neighbor Patterns
• On q-Series Identities Related to Interval Orders
• Hamiltonian cycles for the square of the augmentation graphs and Gray codes for restricted permutations and ascent sequences
• Equidistributed statistics on Fishburn matrices and permutations
• Moments of permutation statistics and central limit theorems
• The combinatorics of Jeff Remmel
• Equidistributed statistics on matchings and permutations
• Pattern avoidance in ascent sequences
• Ascent sequences and the binomial convolution of Catalan numbers
• Sieved Enumeration of Interval Orders and Other Fishburn Structures