Samuel Regan ; Erik Slivken.
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.
Enrica Duchi.
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.
Ioannis Michos ; Christina Savvidou.
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
Dun Qiu ; Jeffrey Remmel.
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
Saúl A. Blanco ; Charles Buehrle ; Akshay Patidar.
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$.
Juan S. Auli ; Sergi Elizalde.
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.
Michael Albert ; Jinge Li.
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.
Miklos Bona ; Michael Cory.
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
Samuel Braunfeld.
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.
Murray Tannock ; Michael Albert.
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
Naiomi T. Cameron ; Kendra Killpatrick.
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.