 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 21 no. 2, Permutation Patters 2018
1. Expected size of a tree in the fixed point forest
We study the local limit of the fixed-point forest, a tree structure associated to a simple sorting algorithm on permutations. This local limit can be viewed as an infinite random tree that can be constructed from a Poisson point process configuration on $[0,1]^\mathbb{N}$. We generalize this random tree, and compute the expected size and expected number of leaves of a random rooted subtree in the generalized version. We also obtain bounds on the variance of the size.
2. A code for square permutations and convex permutominoes
In this article we consider square permutations, a natural subclass of permutations defined in terms of geometric conditions, that can also be described in terms of pattern avoiding permutations, and convex permutoninoes, a related subclass of polyominoes. While these two classes of objects arised independently in various contexts, they play a natural role in the description of certain random horizontally and vertically convex grid configurations. We propose a common approach to the enumeration of these two classes of objets that allows us to explain the known common form of their generating functions, and to derive new refined formulas and linear time random generation algorithms for these objects and the associated grid configurations.
3. Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order
Super-strong Wilf equivalence classes of the symmetric group ${\mathcal S}_n$ on $n$ letters, with respect to the generalized factor order, were shown by Hadjiloucas, Michos and Savvidou (2018) to be in bijection with pyramidal sequences of consecutive differences. In this article we enumerate the latter by giving recursive formulae in terms of a two-dimensional analogue of non-interval permutations. As a by-product, we obtain a recursively defined set of representatives of super-strong Wilf equivalence classes in ${\mathcal S}_n$. We also provide a connection between super-strong Wilf equivalence and the geometric notion of shift equivalence---originally defined by Fidler, Glasscock, Miceli, Pantone, and Xu (2018) for words---by showing that an alternate way to characterize super-strong Wilf equivalence for permutations is by keeping only rigid shifts in the definition of shift equivalence. This allows us to fully describe shift equivalence classes for permutations of size $n$ and enumerate them, answering the corresponding problem posed by Fidler, Glasscock, Miceli, Pantone, and Xu (2018).
Section:
Permutation Patterns
4. Classical pattern distributions in $\mathcal{S}_{n}(132)$ and $\mathcal{S}_{n}(123)$
Classical pattern avoidance and occurrence are well studied in the symmetric group $\mathcal{S}_{n}$. In this paper, we provide explicit recurrence relations to the generating functions counting the number of classical pattern occurrence in the set of 132-avoiding permutations and the set of 123-avoiding permutations.
Section:
Permutation Patterns
5. On the number of pancake stacks requiring four flips to be sorted
Using existing classification results for the 7- and 8-cycles in the pancake graph, we determine the number of permutations that require 4 pancake flips (prefix reversals) to be sorted. A similar characterization of the 8-cycles in the burnt pancake graph, due to the authors, is used to derive a formula for the number of signed permutations requiring 4 (burnt) pancake flips to be sorted. We furthermore provide an analogous characterization of the 9-cycles in the burnt pancake graph. Finally we present numerical evidence that polynomial formulae exist giving the number of signed permutations that require $k$ flips to be sorted, with $5\leq k\leq9$.
6. Consecutive Patterns in Inversion Sequences
An inversion sequence of length $n$ is an integer sequence $e=e_{1}e_{2}\dots e_{n}$ such that $0\leq e_{i}<i$ for each $i$. Corteel--Martinez--Savage--Weselcouch and Mansour--Shattuck began the study of patterns in inversion sequences, focusing on the enumeration of those that avoid classical patterns of length 3. We initiate an analogous systematic study of consecutive patterns in inversion sequences, namely patterns whose entries are required to occur in adjacent positions. We enumerate inversion sequences that avoid consecutive patterns of length 3, and generalize some results to patterns of arbitrary length. Additionally, we study the notion of Wilf equivalence of consecutive patterns in inversion sequences, as well as generalizations of this notion analogous to those studied for permutation patterns. We classify patterns of length up to 4 according to the corresponding Wilf equivalence relations.
7. Uniquely-Wilf classes
Two permutations in a class are Wilf-equivalent if, for every size, $n$, the number of permutations in the class of size $n$ containing each of them is the same. Those infinite classes that have only one equivalence class in each size for this relation are characterised provided either that they avoid at least one permutation of size 3, or at least three permutations of size 4.
8. Cyclic permutations avoiding pairs of patterns of length three
We complete the enumeration of cyclic permutations avoiding two patterns of length three each by providing explicit formulas for all but one of the pairs for which no such formulas were known. The pair $(123,231)$ proves to be the most difficult of these pairs. We also prove a lower bound for the growth rate of the number of cyclic permutations that avoid a single pattern $q$, where $q$ is an element of a certain infinite family of patterns.
Section:
Permutation Patterns
9. The undecidability of joint embedding and joint homomorphism for hereditary graph classes
We prove that the joint embedding property is undecidable for hereditary graph classes, via a reduction from the tiling problem. The proof is then adapted to show the undecidability of the joint homomorphism property as well.
10. Prolific Compositions
Under what circumstances might every extension of a combinatorial structure contain more copies of another one than the original did? This property, which we call prolificity, holds universally in some cases (e.g., finite linear orders) and only trivially in others (e.g., permutations). Integer compositions, or equivalently layered permutations, provide a middle ground. In that setting, there are prolific compositions for a given pattern if and only if that pattern begins and ends with 1. For each pattern, there is an easily constructed automaton that recognises prolific compositions for that pattern. Some instances where there is a unique minimal prolific composition for a pattern are classified.
Section:
Permutation Patterns
11. Statistics on Linear Chord Diagrams
Linear chord diagrams are partitions of $\left[2n\right]$ into $n$ blocks of size two called chords. We refer to a block of the form $\{i,i+1\}$ as a short chord. In this paper, we study the distribution of the number of short chords on the set of linear chord diagrams, as a generalization of the Narayana distribution obtained when restricted to the set of noncrossing linear chord diagrams. We provide a combinatorial proof that this distribution is unimodal and has an expected value of one. We also study the number of pairs $(i,i+1)$ where $i$ is the minimal element of a chord and $i+1$ is the maximal element of a chord. We show that the distribution of this statistic on linear chord diagrams corresponds to the second-order Eulerian triangle and is log-concave.