Discrete Mathematics & Theoretical Computer Science |

We introduce a new boundedness condition for affine permutations, motivatedby the fruitful concept of periodic boundary conditions in statistical physics.We study pattern avoidance in bounded affine permutations. In particular, weshow that if $\tau$ is one of the finite increasing oscillations, then every$\tau$-avoiding affine permutation satisfies the boundedness condition. We alsoexplore the enumeration of pattern-avoiding affine permutations that can bedecomposed into blocks, using analytic methods to relate their exact andasymptotic enumeration to that of the underlying ordinary permutations.Finally, we perform exact and asymptotic enumeration of the set of all boundedaffine permutations of size $n$. A companion paper will focus on avoidance ofmonotone decreasing patterns in bounded affine permutations.

In this paper, we study the staircase encoding of permutations, which maps apermutation to a staircase grid with cells filled with permutations. Weconsider many cases, where restricted to a permutation class, the staircaseencoding becomes a bijection to its image. We describe the image of thoserestrictions using independent sets of graphs weighted with permutations. Wederive the generating function for the independent sets and then for theirweighted counterparts. The bijections we establish provide the enumeration ofpermutation classes. We use our results to uncover some unbalancedWilf-equivalences of permutation classes and outline how to do random samplingin the permutation classes. In particular, we cover the classes$\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$,$\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as manysubclasses.

We give three applications of a recently-proven "Decomposition Lemma," whichallows one to count preimages of certain sets of permutations under West'sstack-sorting map $s$. We first enumerate the permutation class$s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new exampleof an unbalanced Wilf equivalence. This result is equivalent to the enumerationof permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubblesort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$,$s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$,and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ arecounted by the so-called "Boolean-Catalan numbers," settling a conjecture ofthe current author and another conjecture of Hossain. This completes theenumerations of all sets of the form$s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for$\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set$\{321\}$. We also find an explicit formula for$|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents.This allows us to prove a conjectured identity involving Catalan numbers andorder ideals in Young's lattice.

Flip-sort is a natural sorting procedure which raises fascinatingcombinatorial questions. It finds its roots in the seminal work of Knuth onstack-based sorting algorithms and leads to many links with permutationpatterns. We present several structural, enumerative, and algorithmic resultson permutations that need few (resp. many) iterations of this procedure to besorted. In particular, we give the shape of the permutations after oneiteration, and characterize several families of permutations related to thebest and worst cases of flip-sort. En passant, we also give some links betweenpop-stack sorting, automata, and lattice paths, and introduce several tacticsof bijective proofs which have their own interest.

Catalan words are particular growth-restricted words counted by the eponymousinteger sequence. In this article we consider Catalan words avoiding a pair ofpatterns of length 3, pursuing the recent initiating work of the first and lastauthors and of S. Kirgizov where (among other things) the enumeration ofCatalan words avoiding a patterns of length 3 is completed. More precisely, weexplore systematically the structural properties of the sets of words underconsideration and give enumerating results by means of recursive decomposition,constructive bijections or bivariate generating functions with respect to thelength and descent number. Some of the obtained enumerating sequences areknown, and thus the corresponding results establish new combinatorialinterpretations for them.

Defant, Engen, and Miller defined a permutation to be uniquely sorted if ithas exactly one preimage under West's stack-sorting map. We enumerate classesof uniquely sorted permutations that avoid a pattern of length three and apattern of length four by establishing bijections between these classes andvarious lattice paths. This allows us to prove nine conjectures of Defant.

In this paper, we enumerate Dumont permutations of the fourth kind avoidingor containing certain permutations of length 4. We also conjecture aWilf-equivalence of two 4-letter patterns on Dumont permutations of the firstkind.

A skew shape is the difference of two top-left justified Ferrers shapessharing the same top-left corner. We study integer fillings of skew shapes. Asour first main result, we show that for a specific hereditary class of skewshapes, which we call D-free shapes, the fillings that avoid a north-east chainof size $k$ are in bijection with fillings that avoid a south-east chain of thesame size. Since Ferrers shapes are a subclass of D-free shapes, this resultcan be seen as a generalization of previous analogous results for Ferrersshapes. As our second main result, we construct a bijection between 01-fillings of anarbitrary skew shape that avoid a south-east chain of size 2, and the01-fillings of the same shape that simultaneously avoid a north-east chain ofsize 2 and a particular non-square subfilling. This generalizes a previousresult for transversal fillings.

Two permutation classes, the X-class and subpermutations of the increasingoscillation are shown to exhibit an exponential Wilf-collapse. This means thatthe number of distinct enumerations of principal subclasses of each of theseclasses grows much more slowly than the class itself whereas a priori, basedonly on symmetries of the class, there is no reason to expect this. Theunderlying cause of the collapse in both cases is the ability to apply someform of local symmetry which, combined with a greedy algorithm for detectingpatterns in these classes, yields a Wilf-collapse.

As a step towards resolving a question of Ruškuc on the decidability ofjoint embedding for hereditary classes of permutations, which may be viewed asstructures in a language of 2 linear orders, we show the corresponding problemis undecidable for hereditary classes of structures in a language of 3 linearorders.

We enumerate permutations in the two permutation classes $\text{Av}_n(312,4321)$ and $\text{Av}_n(321, 4123)$ by the number of cycles each permutationadmits. We also refine this enumeration with respect to several statistics.

We show that permutations avoiding both of the (classical) patterns 4321 and3241 have the algebraic generating function conjectured by Vladimir Kruchinin.

We show that the counting sequence for permutations avoiding both of the(classical) patterns 1243 and 2134 has the algebraic generating functionsupplied by Vaclav Kotesovec for sequence A164651 in The On-Line Encyclopediaof Integer Sequences.