Michael Albert ; Robert Brignall.
In this note, we prove that all $2 \times 2$ monotone grid classes are
finitely based, i.e., defined by a finite collection of minimal forbidden
permutations. This follows from a slightly more general result about certain $2
\times 2$ (generalized) grid classes having two monotone cells in the same row.
Section:
Permutation Patterns
Sylvie Corteel ; Megan A. Martinez ; Carla D. Savage ; Michael Weselcouch.
Permutations that avoid given patterns have been studied in great depth for
their connections to other fields of mathematics, computer science, and
biology. From a combinatorial perspective, permutation patterns have served as
a unifying interpretation that relates a vast array of combinatorial
structures. In this paper, we introduce the notion of patterns in inversion
sequences. A sequence $(e_1,e_2,\ldots,e_n)$ is an inversion sequence if $0
\leq e_i<i$ for all $i \in [n]$. Inversion sequences of length $n$ are in
bijection with permutations of length $n$; an inversion sequence can be
obtained from any permutation $\pi=\pi_1\pi_2\ldots \pi_n$ by setting $e_i =
|\{j \ | \ j < i \ {\rm and} \ \pi_j > \pi_i \}|$. This correspondence makes it
a natural extension to study patterns in inversion sequences much in the same
way that patterns have been studied in permutations. This paper, the first of
two on patterns in inversion sequences, focuses on the enumeration of inversion
sequences that avoid words of length three. Our results connect patterns in
inversion sequences to a number of well-known numerical sequences including
Fibonacci numbers, Bell numbers, Schröder numbers, and Euler up/down numbers.
Section:
Permutation Patterns
Mitchell Paukner ; Lucy Pepin ; Manda Riehl ; Jarred Wieser.
We have extended classical pattern avoidance to a new structure: multiple
task-precedence posets whose Hasse diagrams have three levels, which we will
call diamonds. The vertices of each diamond are assigned labels which are
compatible with the poset. A corresponding permutation is formed by reading
these labels by increasing levels, and then from left to right. We used Sage to
form enumerative conjectures for the associated permutations avoiding
collections of patterns of length three, which we then proved. We have
discovered a bijection between diamonds avoiding 132 and certain generalized
Dyck paths. We have also found the generating function for descents, and
therefore the number of avoiders, in these permutations for the majority of
collections of patterns of length three. An interesting application of this
work (and the motivating example) can be found when task-precedence posets
represent warehouse package fulfillment by robots, in which case avoidance of
both 231 and 321 ensures we never stack two heavier packages on top of a
lighter package.
Section:
Permutation Patterns
Vincent Vatter.
Let $\mathcal{C}$ be a permutation class that does not contain all layered
permutations or all colayered permutations. We prove that there is a constant
$c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a
monotone subsequence of length $cn$.
Section:
Permutation Patterns
Eric S. Egge ; Kailee Rubin.
Caffrey, Egge, Michel, Rubin and Ver Steegh recently introduced snow leopard
permutations, which are the anti-Baxter permutations that are compatible with
the doubly alternating Baxter permutations. Among other things, they showed
that these permutations preserve parity, and that the number of snow leopard
permutations of length $2n-1$ is the Catalan number $C_n$. In this paper we
investigate the permutations that the snow leopard permutations induce on their
even and odd entries; we call these the even threads and the odd threads,
respectively. We give recursive bijections between these permutations and
certain families of Catalan paths. We characterize the odd (resp. even) threads
which form the other half of a snow leopard permutation whose even (resp. odd)
thread is layered in terms of pattern avoidance, and we give a constructive
bijection between the set of permutations of length $n$ which are both even
threads and odd threads and the set of peakless Motzkin paths of length $n+1$.
Section:
Permutation Patterns
Ran Pan ; Jeffrey B. Remmel.
A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if
any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share
at most one element. Bóna \cite{B} showed that the proportion of minimal
overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation $\sigma$,
we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study
the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in
the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in
$S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that
$\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of
the minimal overlapping permutations for such classes of permutations and we
study the proportion of minimal overlapping patterns for each such class. We
show that the proportion of minimal overlapping permutations in such classes
approaches $1$ as $k$ goes to infinity. We also study the proportion of minimal
overlapping patterns in standard Young tableaux of shape $(n^k)$.
Section:
Permutation Patterns
Josefran de Oliveira Bastos ; Leonardo Nagami Coregliano.
In this paper, we present two new results of layered permutation densities.
The first one generalizes theorems from Hästö (2003) and Warren (2004)
to compute the permutation packing of permutations whose layer sequence
is~$(1^a,\ell_1,\ell_2,\ldots,\ell_k)$ with~$2^a-a-1\geq k$ (and similar
permutations). As a second result, we prove that the minimum density of
monotone sequences of length~$k+1$ in an arbitrarily large layered permutation
is asymptotically~$1/k^k$. This value is compatible with a conjecture from
Myers (2003) for the problem without the layered restriction (the same problem
where the monotone sequences have different lengths is also studied).
Section:
Permutation Patterns
David Bevan ; Derek Levin ; Peter Nugent ; Jay Pantone ; Lara Pudwell ; Manda Riehl ; ML Tlachac.
We investigate pattern avoidance in permutations satisfying some additional
restrictions. These are naturally considered in terms of avoiding patterns in
linear extensions of certain forest-like partially ordered sets, which we call
binary shrub forests. In this context, we enumerate forests avoiding patterns
of length three. In four of the five non-equivalent cases, we present explicit
enumerations by exhibiting bijections with certain lattice paths bounded above
by the line $y=\ell x$, for some $\ell\in\mathbb{Q}^+$, one of these being the
celebrated Duchon's club paths with $\ell=2/3$. In the remaining case, we use
the machinery of analytic combinatorics to determine the minimal polynomial of
its generating function, and deduce its growth rate.
Section:
Permutation Patterns
Jonathan Bloom ; Dan Saracino.
In 2000 Klazar introduced a new notion of pattern avoidance in the context of
set partitions of $[n]=\{1,\ldots, n\}$. The purpose of the present paper is to
undertake a study of the concept of Wilf-equivalence based on Klazar's notion.
We determine all Wilf-equivalences for partitions with exactly two blocks, one
of which is a singleton block, and we conjecture that, for $n\geq 4$, these are
all the Wilf-equivalences except for those arising from complementation. If
$\tau$ is a partition of $[k]$ and $\Pi_n(\tau)$ denotes the set of all
partitions of $[n]$ that avoid $\tau$, we establish inequalities between
$|\Pi_n(\tau_1)|$ and $|\Pi_n(\tau_2)|$ for several choices of $\tau_1$ and
$\tau_2$, and we prove that if $\tau_2$ is the partition of $[k]$ with only one
block, then $|\Pi_n(\tau_1)| <|\Pi_n(\tau_2)|$ for all $n>k$ and all partitions
$\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds
for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for
all partitions $\tau$ of $[4]$.
Section:
Permutation Patterns
David Bevan.
We determine the structure of permutations avoiding the patterns 4213 and
2143. Each such permutation consists of the skew sum of a sequence of plane
trees, together with an increasing sequence of points above and an increasing
sequence of points to its left. We use this characterisation to establish the
generating function enumerating these permutations. We also investigate the
properties of a typical large permutation in the class and prove that if a
large permutation that avoids 4213 and 2143 is chosen uniformly at random, then
it is more likely than not to avoid 2413 as well.
Section:
Permutation Patterns
Michael H. Albert ; Marie-Louise Lackner ; Martin Lackner ; Vincent Vatter.
The Permutation Pattern Matching problem, asking whether a pattern
permutation $\pi$ is contained in a permutation $\tau$, is known to be
NP-complete. In this paper we present two polynomial time algorithms for
special cases. The first algorithm is applicable if both $\pi$ and $\tau$ are
$321$-avoiding; the second is applicable if $\pi$ and $\tau$ are skew-merged.
Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $\pi$ and
$n$ the length of $\tau$.
Section:
Permutation Patterns
Cyril Banderier ; Jean-Luc Baril ; Céline Moreira Dos Santos.
We study the iteration of the process "a particle jumps to the right" in
permutations. We prove that the set of permutations obtained in this model
after a given number of iterations from the identity is a class of pattern
avoiding permutations. We characterize the elements of the basis of this class
and we enumerate these "forbidden minimal patterns" by giving their bivariate
exponential generating function: we achieve this via a catalytic variable, the
number of left-to-right maxima. We show that this generating function is a
D-finite function satisfying a nice differential equation of order~2. We give
some congruence properties for the coefficients of this generating function,
and we show that their asymptotics involves a rather unusual algebraic exponent
(the golden ratio $(1+\sqrt 5)/2$) and some unusual closed-form constants. We
end by proving a limit law: a forbidden pattern of length $n$ has typically
$(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations.
Section:
Permutation Patterns
Quang T. Bach ; Jeffrey B. Remmel.
Let $S_n$ denote the symmetric group. For any $\sigma \in S_n$, we let
$\mathrm{des}(\sigma)$ denote the number of descents of $\sigma$,
$\mathrm{inv}(\sigma)$ denote the number of inversions of $\sigma$, and
$\mathrm{LRmin}(\sigma)$ denote the number of left-to-right minima of $\sigma$.
For any sequence of statistics $\mathrm{stat}_1, \ldots \mathrm{stat}_k$ on
permutations, we say two permutations $\alpha$ and $\beta$ in $S_j$ are
$(\mathrm{stat}_1, \ldots \mathrm{stat}_k)$-c-Wilf equivalent if the generating
function of $\prod_{i=1}^k x_i^{\mathrm{stat}_i}$ over all permutations which
have no consecutive occurrences of $\alpha$ equals the generating function of
$\prod_{i=1}^k x_i^{\mathrm{stat}_i}$ over all permutations which have no
consecutive occurrences of $\beta$. We give many examples of pairs of
permutations $\alpha$ and $\beta$ in $S_j$ which are $\mathrm{des}$-c-Wilf
equivalent, $(\mathrm{des},\mathrm{inv})$-c-Wilf equivalent, and
$(\mathrm{des},\mathrm{inv},\mathrm{LRmin})$-c-Wilf equivalent. For example, we
will show that if $\alpha$ and $\beta$ are minimally overlapping permutations
in $S_j$ which start with 1 and end with the same element and
$\mathrm{des}(\alpha) = \mathrm{des}(\beta)$ and $\mathrm{inv}(\alpha) =
\mathrm{inv}(\beta)$, then $\alpha$ and $\beta$ are
$(\mathrm{des},\mathrm{inv})$-c-Wilf equivalent.
Section:
Permutation Patterns
Both Neou ; Romeo Rizzi ; Stéphane Vialette.
Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where only σ avoids 213 and 231, we present a O(max(kn 2 , n 2 log log n)-time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn 4)-time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231.
Section:
Permutation Patterns
Michael W. Schroeder ; Rebecca Smith.
We consider a sorting machine consisting of two stacks in series where the
first stack has the added restriction that entries in the stack must be in
decreasing order from top to bottom. The class of permutations sortable by this
machine are known to be enumerated by the Schröder numbers. In this paper, we
give a bijection between these sortable permutations of length $n$ and
Schröder paths -- the lattice paths from $(0,0)$ to $(n-1,n-1)$ composed of
East steps $(1,0)$, North steps $(0,1)$, and Diagonal steps $(1,1)$ that travel
weakly below the line $y=x$.
Section:
Permutation Patterns