# Wilf collapse in permutation classes

Michael Albert University of Otago, Dunedin, New Zealand. Vít Jelínek Computer
Science Institute, Charles University, Prague, Czechia. Supported by project
Impuls of the Neuron Fund for Support of Science, by project SVV–2017–260452,
and by project 18-19158S of the Czech Science Foundation. Michal
Opler22footnotemark: 2

###### Abstract

For a hereditary permutation class ${\mathcal{C}}$, we say that two
permutations $\pi$ and $\sigma$ of ${\mathcal{C}}$ are _Wilf-equivalent in
${\mathcal{C}}$_, if ${\mathcal{C}}$ has the same number of permutations
avoiding $\pi$ as those avoiding $\sigma$. We say that a permutation class
${\mathcal{C}}$ exhibits a _Wilf collapse_ if the number of permutations of
size $n$ in ${\mathcal{C}}$ is asymptotically larger than the number of Wilf-
equivalence classes formed by these permutations.

Previously, only a few specific examples of classes were known to exhibit Wilf
collapse. In this paper, we show that Wilf collapse is a surprisingly common
phenomenon. Among other results, we show that Wilf collapse occurs in any
permutation class with unbounded growth and finitely many sum-indecomposable
permutations.

Our proofs are based on encoding the elements of a permutation class
${\mathcal{C}}$ as words and analyzing the structure of a random permutation
in ${\mathcal{C}}$ using this representation.

##  1 Introduction

Given a collection, ${\mathcal{C}}$, of finite structures one associates with
it the _growth function_ $n\mapsto c_{n}$ where $c_{n}$ is the number of
structures in ${\mathcal{C}}$ of size $n$. There seems to be no generally
accepted word for the concept of “two classes having the same growth function”
– we have decided to say that such classes are _rank-equinumerous_. In the
study of permutation classes (exact definitions follow in the next section)
much attention has been paid to examples of rank-equinumerosity, perhaps the
most famous being that the collection of permutations that do not contain the
permutation $231$ as a subpermutation, and the class of those that do not
contain $321$ are rank-equinumerous. While such equivalences are interesting
they are perhaps not too surprising given that simple questions tend to have
simple answers and there are only so many simple answers to go around.

We are concerned with a special sort of rank-equinumerosity. This arises when
we begin with a universe, ${\mathcal{U}}$, of finite structures carrying a
containment relation denoted $\leqslant$. The collections we then consider are
down-sets in ${\mathcal{U}}$, i.e., subcollections of ${\mathcal{U}}$ closed
under containment (sometimes called _hereditary_ subsets of ${\mathcal{U}}$).
Even more specifically, we consider only those down-sets that are defined by
the _avoidance_ of a single structure $A$, i.e., they consist of all the
elements of ${\mathcal{U}}$ that do not contain $A$. We then say that $A$ and
$B$ are _Wilf-equivalent_ (in ${\mathcal{U}}$ if the context is not clear), if
the down-set of structures avoiding $A$ is rank-equinumerous to the down-set
of structures avoiding $B$. For example, the rank-equinumerosity mentioned in
the previous paragraph arises then when ${\mathcal{U}}$ is the set of all
permutations, $A=231$ and $B=321$.

We will also say that ${\mathcal{U}}$ exhibits a _Wilf collapse_ if the number
of Wilf-equivalence classes on structures of size $n$ is small when compared
to the total number of structures of size $n$, i.e., the average size of a
Wilf class tends to infinity as $n$ grows. We further say that ${\mathcal{U}}$
exhibits an _exponential Wilf collapse_ if the average size of a Wilf class is
exponential in $n$.

While there have been many previous investigations that deal with specific
examples of Wilf equivalence, or even a few general groups of Wilf-equivalent
structures, there has been relatively little attention paid to the phenomenon
of Wilf collapse. In [AlbertBouvel] it was demonstrated that the universe of
312-avoiding permutations exhibits a Wilf collapse, and in [AlbertLi] that
every permutation class with two basis elements of size 3 and itself having an
unbounded growth function (which is of course a prerequisite for Wilf
collapse!) exhibits a Wilf collapse. Notably, as of this moment, we still do
not know if the universe of 321-avoiding permutations exhibits a Wilf collapse
and the results of this paper do not speak to this case.

In this paper, rather than focusing on individual examples of permutation
classes, we derive general structural criteria that imply Wilf collapse, or
even exponential Wilf collapse. Our approach is based on decomposing
permutations into indecomposable blocks using the sum operation (see Section 2
for precise definitions). Specifically, we can prove the following results.

  * •

Any permutation class ${\mathcal{C}}$ obtained as a sum-closure of finitely
many permutations exhibits an exponential Wilf collapse, except for the class
of 21-avoiding permutations, whose growth function is bounded. See Corollary
4.2.

  * •

Any permutation class ${\mathcal{C}}$ with unbounded growth function and with
only finitely many indecomposable permutations has a Wilf collapse. See
Theorem 4.3.

We remark that the first of these results is in fact a special case of a more
general theorem (Theorem 4.1), which deals with sum-closures of possibly
infinite sets satisfying certain additional restrictions.

While our results focus on permutation classes, the underlying arguments can
be generalised easily to some other contexts. The basis of our approach is the
observation that any permutation can be uniquely expressed as a sum of a
sequence of sum-indecomposable components. This yields a representation of a
permutation by a word over an alphabet consisting of the indecomposable
permutations. The containment of permutations then corresponds to a certain
“greedy” embedding of words. We then identify, for a permutation class
${\mathcal{C}}$ satisfying suitable closure properties, a number of “local
modifications” of the word which preserve the Wilf class of the corresponding
permutation. These local modifications often take the form of applying a
symmetry operation to a subword. Finally, and this is usually the most
difficult part of the argument, we analyse the structure of a word
representing a random permutation $\pi$ of ${\mathcal{C}}$, and show that with
high probability it offers many opportunities for such local modifications,
showing that $\pi$ belongs to a large Wilf class.

Our emphasis in this paper is simply on establishing the existence of a Wilf
collapse: we make no attempt to determine the precise number of Wilf classes,
or even an accurate asymptotic estimate. This is because our results are
necessarily based on general criteria for Wilf equivalence, while specific
permutation classes may often admit additional rules or coincidences that
cause further collapse. Besides, even in quite simple settings such as those
considered in [AlbertLi] where the precise nature of a collapse can be
computed, dealing with the exact answers can become quite technical. That is,
demonstrating that certain groups of structures are Wilf-equivalent is easy,
but demonstrating that no others are seems hard. Similarly, in [AlbertBouvel]
there is a conjectural description of the exact nature of the Wilf collapse
within certain classes enumerated by the Catalan numbers, and while the
experimental evidence in its favour seems quite strong, there is no known way
to rule out some other “accidental” coincidences.

The structure of the remainder of this paper is as follows. In Section 2, we
provide the basic definitions needed to discuss permutation classes and Wilf
collapse. Section 3 then carries out some necessary preparatory work about
words and generalisations of the subword relation. Section 4 is devoted to the
statements and proofs of our main results. Our two main results there are
Theorem 4.1 which deals with sum-closed classes, and Theorem 4.3 concerning
classes having only finitely many sum-indecomposable permutations. Finally, in
Section 5 we discuss the significance and limitations of our results, and pose
some further questions which we consider pertinent.

##  2 Basic definitions

We refer the reader to Vatter’s excellent survey [Vatter-survey] for a much
more detailed consideration of permutation classes (as well as an historical
introduction) providing here only the essential elements for our work. We are
concerned only with permutations of size $n$ which we generally think of in
one-line notation i.e., as sequences of length $n$ consisting of the elements
of $[n]=\\{1,2,\dots,n\\}$ in some order. We write $|\pi|$ for the size of a
permutation $\pi$111We generally try to avoid using the word “length” here
although it is quite common and natural due to a possible confusion with the
notion of length of a permutation arising in algebraic combinatorics..

When we take a subsequence of size $k$ of such a sequence and then relabel it
so that its least element is labelled 1, its second least element 2, …, and
its greatest element $k$ then we obtain another permutation and this
relationship defines the notion of containment between permutations (sometimes
called “containment as patterns”). To rephrase: a permutation $\tau$ of size
$n$ _contains_ a permutation $\pi$ of size $k$ if there is a subsequence of
$\tau$ consisting of $k$ elements whose relabelling by relative value yields
$\pi$. If this occurs we write $\pi\leqslant\tau$, and if not we say that
$\tau$ _avoids_ $\pi$ and write $\pi\not\leqslant\tau$. For instance the
permutation $31524$ contains the patterns $123$ (as $124$) and $213$ (as
either $315$ or $314$) but not the pattern $321$ (since no three of its
elements form a descending sequence). A _permutation class_ is a collection of
permutations, ${\mathcal{C}}$, closed downwards under containment, i.e., if
$\tau\in{\mathcal{C}}$ and $\pi\leqslant\tau$ then $\pi\in{\mathcal{C}}$.

The partially ordered set ${\mathcal{S}}$ of all finite permutations ordered
by containment admits eight symmetries corresponding to the action of the
dihedral group on a square. These symmetries are easy to understand if we
think of a permutation $\pi$ as being represented by the set of points
$(i,\pi_{i})$ contained in an axis-aligned square. Reflection in a vertical
axis is called “reverse”, in a horizontal axis “complement”, and in an upward
sloping diagonal “inverse”.

Given a permutation class ${\mathcal{C}}$ other than the class of all
permutations, there are some $\leqslant$-minimal permutations in its
complement and these are called its _basis_. So ${\mathcal{C}}$ can also be
described as the set of all permutations avoiding any permutation in its
basis. If $X$ is any set of permutations then we write $\operatorname{Av}(X)$
for the class of permutations that avoid every element of $X$. If $X$ is an
antichain with respect to containment then $X$ will be the basis of
$\operatorname{Av}(X)$.

Given two permutations $\alpha$ and $\beta$ define their _sum_
$\alpha\oplus\beta$ to be the concatenation of $\alpha$ and $a+\beta$ where
$a$ is the size of $\alpha$. For instance $231\oplus 2413=2315746$. It is easy
to see that this operation is associative on permutations. A class
${\mathcal{C}}$ is _sum-closed_ if whenever $\alpha,\beta\in{\mathcal{C}}$
then also $\alpha\oplus\beta\in{\mathcal{C}}$. A permutation is _sum-
indecomposable_ if it cannot be written as a proper sum of two permutations.
There is a dual notion of _skew-sum_ ($\ominus$) where $\alpha\ominus\beta$ is
the concatenation of $b+\alpha$ with $\beta$ (where the size of $\beta$ is
$b$). It is easy to see that a permutation class is sum- (resp. skew-) closed
if and only if all of its basis elements are sum- (resp. skew-)
indecomposable.

It is particularly convenient to work with (and within) sum-closed classes
because there is a natural representation of any permutation $\alpha$ in such
a class as the unique sequence of sum-indecomposable permutations
$\alpha_{1}\alpha_{2}\cdots\alpha_{k}$ for which

$\alpha=\alpha_{1}\oplus\alpha_{2}\oplus\cdots\oplus\alpha_{k}.$

This identifies the class with the language of words over its sum-
indecomposables. Given any set $X$ of permutations there is a smallest class
${\mathcal{C}}$ which is sum-closed and contains $X$ (obtained simply by
finding all the sum-indecomposable permutations that are contained in some
element of $X$ and then taking all sums of those). This class is called the
_sum-closure_ of $X$.

Let a class ${\mathcal{C}}$ be given. Two permutations
$\alpha,\beta\in{\mathcal{C}}$ are _Wilf-equivalent in ${\mathcal{C}}$_
(written $\alpha\equiv_{{\mathcal{C}}}\beta$) if the two classes
${\mathcal{C}}\cap\operatorname{Av}(\alpha)$ and
${\mathcal{C}}\cap\operatorname{Av}(\beta)$ are rank-equinumerous, i.e., have
the same growth functions. The equivalence classes of $\equiv_{\mathcal{C}}$
are known as the _Wilf classes_.

######  Observation 2.1.

If $\alpha\equiv_{{\mathcal{C}}}\beta$ then $|\alpha|=|\beta|$.

###### Proof.

Without loss of generality suppose that $k=|\alpha|\leq|\beta|$. The number of
permutations in ${\mathcal{C}}\cap\operatorname{Av}(\alpha)$ of size $k$ is
exactly one less than the number of permutations in ${\mathcal{C}}$ of size
$k$ and for this to be true of ${\mathcal{C}}\cap\operatorname{Av}(\beta)$ as
well we must have $|\beta|=k$, otherwise every permutation in ${\mathcal{C}}$
of size $k$ belongs to ${\mathcal{C}}\cap\operatorname{Av}(\beta)$. ∎

For a positive integer $n$, let ${\mathcal{C}}_{n}$ denote the set of
permutations in ${\mathcal{C}}$ of size $n$, let $c_{n}$ be the cardinality of
${\mathcal{C}}_{n}$, and let $w_{n}$ denote the number of Wilf classes formed
by the permutations in ${\mathcal{C}}_{n}$. This allows us at last to define
the fundamental concept which we will investigate.

######  Definition 2.2.

The class ${\mathcal{C}}$ has a _Wilf collapse_ if $w_{n}=o(c_{n})$ and an
_exponential Wilf collapse_ if, for some $r<1$, $w_{n}=o(r^{n}c_{n})$.

If ${\mathcal{C}}$ is closed under some symmetry $\phi$ of ${\mathcal{S}}$ and
$\alpha\in{\mathcal{C}}$ then $\alpha\equiv_{{\mathcal{C}}}\phi(\alpha)$.
However, this never provides a Wilf collapse since ${\mathcal{S}}$ has only
eight symmetries. That said, these equivalences will form the core of many of
our constructions that do demonstrate Wilf collapse.

##  3 A digression on words

Let ${\mathcal{A}}$ be a set of symbols which we will call the _letters_ of an
_alphabet_. A _word_ over ${\mathcal{A}}$ is just a finite sequence (possibly
empty) of elements of ${\mathcal{A}}$ — the set of all words over
${\mathcal{A}}$ is denoted ${\mathcal{A}}^{\ast}$ and the set of non-empty
words is denoted ${\mathcal{A}}^{+}$. The empty word is denoted $\epsilon$.
The set ${\mathcal{A}}^{\ast}$ has an associative operation which is normally
simply represented by concatenation.

We generally use lower case letters from near the beginning of the alphabet to
denote elements of ${\mathcal{A}}$ and upper case letters from near the end of
the alphabet to denote words. That said, we will freely identify a letter
$a\in{\mathcal{A}}$ with the corresponding word of length $1$, and thus treat
${\mathcal{A}}$ as a subset of ${\mathcal{A}}^{+}$.

If $W=a_{1}a_{2}\cdots a_{n}$ then we say that $a_{i}$ is the character of
_index_ $i$. If $W\in{\mathcal{A}}^{+}$ then $\operatorname{first}(W)$ and
$\operatorname{last}(W)$ denote the first and last letter of $W$ respectively;
this notation is not defined for the empty word, i.e., when used contains an
implicit condition that $W\neq\epsilon$.

We will further assume that each letter $a\in{\mathcal{A}}$ has a _weight_ ,
denoted $\operatorname{wt}(a)$, which is a positive integer. We extend the
weight function to ${\mathcal{A}}^{\ast}$ by setting

$\operatorname{wt}(a_{1}a_{2}\cdots
a_{k})=\sum_{i=1}^{k}\operatorname{wt}(a_{i}).$

An _embedding order_ is any partial order $\leqslant$ on
${\mathcal{A}}^{\ast}$ satisfying these conditions:

  * •

For any $W\in{\mathcal{A}}^{\ast}$, we have $\epsilon\leqslant W$.

  * •

If $W\leqslant V$ for some $V,W\in{\mathcal{A}}^{\ast}$ with $W\neq V$, then
$\operatorname{wt}(W)<\operatorname{wt}(V)$.

  * •

Suppose that $V=a_{1}a_{2}\cdots a_{k}$. Then, for any
$W\in{\mathcal{A}}^{*}$, we have $W\leqslant V$ if and only if $W$ admits a
factorisation $W=W_{1}W_{2}\cdots W_{k}$ such that $W_{i}\leqslant a_{i}$ for
each $i$.

A familiar example of an embedding order is the _subword order_ , where
$W=a_{1}a_{2}\cdots a_{k}$ is a subword of $V=b_{1}b_{2}\cdots b_{\ell}$ if
the sequence $a_{1},\dotsc,a_{k}$ is a (not necessarily consecutive)
subsequence of $b_{1},\dotsc,b_{\ell}$. In fact, if $W$ is a subword of $V$,
then in any embedding order $\leqslant$ we must have $W\leqslant V$.

From now on, we assume that $\leqslant$ is an embedding order for a weighted
alphabet ${\mathcal{A}}$. A useful feature of such orders is that containment
can be tested by a natural “greedy” procedure, as shown by the next
proposition.

######  Proposition 3.1.

Let $W,V\in{\mathcal{A}}^{\ast}$ be two words with $V=b_{1}b_{2}\cdots b_{m}$,
let $X=b_{1}\cdots b_{i}$ be a prefix of $V$, and let $Y=b_{i+1}\cdots b_{m}$
be the corresponding suffix. Let $P$ be the maximal prefix of $W$ such that
$P\leqslant X$, and write $W=PS$. Then $W\leqslant V$ if and only if
$S\leqslant Y$.

###### Proof.

If $P\leqslant X$ and $S\leqslant Y$, then $W=PS\leqslant XY=V$ by the
properties of embedding order. Conversely, if $W\leqslant V$ then we can write
$W=W_{1}W_{2}\cdots W_{m}$ with $W_{j}\leqslant b_{j}$. In particular,
$W_{1}W_{2}\cdots W_{i}$ is either $P$ or a proper prefix of $P$. Then $S$ is
a (not necessarily proper) suffix of $W_{i+1}\cdots W_{m}$ and hence
$S\leqslant Y$. ∎

######  Definition 3.2.

Let $W,V\in{\mathcal{A}}^{\ast}$. If $W\leqslant V$ and $W\not\leqslant P$ for
any proper prefix $P$ of $V$ then we say that $V$ is a _minimal container_ for
$W$ and write $W\leqslant^{\ast}V$. Further we define generating functions:

$\displaystyle A(x)$
$\displaystyle=\sum_{a\in{\mathcal{A}}}x^{\operatorname{wt}(a)},$
$\displaystyle I_{W}(x)$ $\displaystyle=\sum_{W\leqslant
V}x^{\operatorname{wt}(V)},$ $\displaystyle I_{W}^{\ast}(x)$
$\displaystyle=\sum_{W\leqslant^{\ast}V}x^{\operatorname{wt}(V)}.$

Observe that $W\leqslant V$ if and only if $V$ can be written as $V=PZ$ where
$W\leqslant^{\ast}P$ and $Z\in{\mathcal{A}}^{\ast}$ is arbitrary; moreover $P$
is uniquely determined as the minimal prefix of $V$ which is greater than or
equal to $W$. This corresponds to the following identity of generating
functions.

######  Observation 3.3.

For any $W\in{\mathcal{A}}^{\ast}$

$I_{W}(x)=\frac{I^{\ast}_{W}(x)}{1-A(x)}.$

In particular $I_{W}(x)=I_{V}(x)$ if and only if
$I^{\ast}_{W}(x)=I^{\ast}_{V}(x)$.

Let us say that two words $W$ and $V$ are _equivalent_ , denoted by $W\equiv
V$, if $I_{W}(x)=I_{V}(x)$. Our goal is to show that, under certain
assumptions about $\leqslant$, there are many pairs of equivalent words.

######  Definition 3.4.

Let $a,b\in{\mathcal{A}}$ be two letters. The ordered pair $(a,b)$ is
_incompatible_ if there is no $c\in{\mathcal{A}}$ such that $ab\leqslant c$.

######  Definition 3.5.

Let $W_{1},W_{2},\dots,W_{k}\in{\mathcal{A}}^{+}$. The factorisation
$W=W_{1}W_{2}\cdots W_{k}$ is _incompatible_ if for $1\leqslant i<k$,
$(\operatorname{last}(W_{i}),\operatorname{first}(W_{i+1}))$ are incompatible
pairs.

######  Proposition 3.6.

Suppose that that $W=W_{1}W_{2}\cdots W_{k}$ is an incompatible factorisation.
Then

$I_{W}(x)=\frac{\prod_{i=1}^{k}I^{\ast}_{W_{i}}(x)}{1-A(x)}.$

###### Proof.

The proof is by induction on $k$. For $k=1$ it is simply Observation 3.3. Now
suppose that $k>1$ and the result holds for all lesser $k$. To complete the
proof, it suffices to show that

$I_{W}(x)=I^{\ast}_{W_{1}}(x)I_{W_{2}W_{3}\cdots W_{k}}(x),$ (1)

and apply induction. To prove (1), we will show that a word
$V\in{\mathcal{A}}^{\ast}$ satisfies $W\leqslant V$ if and only if $V$ can be
written as $V=XY$ with $W_{1}\leqslant^{\ast}X$ and $W_{2}W_{3}\cdots
W_{k}\leqslant Y$, and moreover, the $X$ and $Y$ are then determined uniquely.

Clearly, for any choice of $X$ and $Y$ satisfying $W_{1}\leqslant^{\ast}X$ and
$W_{2}W_{3}\cdots W_{k}\leqslant Y$, we have $W\leqslant XY$. To prove the
converse, choose $V$ such that $W\leqslant V$. Then there is a unique prefix
$X$ of $V$ such that $W_{1}\leqslant^{\ast}X$. Let $V=XY$,
$a=\operatorname{last}(W_{1})$, $b=\operatorname{first}(W_{2})$ and
$X=c_{1}c_{2}\cdots c_{n}$. By the definition of an embedding order, $W_{1}$
can be written as $W_{1}=Z_{1}Z_{2}\cdots Z_{n}$ with $Z_{i}\leqslant c_{i}$.
Moreover, from the minimality of $X$, it follows that $Z_{n}\neq\epsilon$ and
that $W_{1}\not\leqslant c_{1}\cdots c_{n-1}$. In particular,
$a=\operatorname{last}(Z_{n})\leq c_{n}$. Since $a$ and $b$ are incompatible,
we know that $ab\not\leqslant c_{n}$, and therefore $W_{1}$ is the longest
prefix of $W$ such that $W_{1}\leqslant X$. By Proposition 3.1, we get
$W_{2}\cdots W_{k}\leqslant Y$, as claimed. ∎

The following direct corollary of Proposition 3.6 and Observation 3.3 is the
keystone in constructing many examples of equivalent words:

######  Corollary 3.7.

Suppose that for $1\leqslant i\leqslant k$, $W_{i}\equiv V_{i}$, and that
$\pi\in{\mathcal{S}}_{k}$. If both factorisations $W=W_{1}W_{2}\cdots W_{k}$
and $V=V_{\pi(1)}V_{\pi(2)}\cdots V_{\pi(k)}$ are incompatible then $W\equiv
V$.

###  3.1 Uniform sampling of words

We will often need to refer to the properties of uniformly random words of a
given weight in a given set ${\mathcal{A}}^{\ast}$. Recall that

$A(x)=\sum_{a\in{\mathcal{A}}}x^{\operatorname{wt}(a)}$

is the generating function of the alphabet ${\mathcal{A}}$, and define

$A^{*}(x)=\sum_{W\in{\mathcal{A}}^{\ast}}x^{\operatorname{wt}(W)}=\frac{1}{1-A(x)}.$

Let $\rho_{A}$ be the radius of convergence of $A(x)$. We say that
${\mathcal{A}}^{*}$ is _supercritical_ if

$\lim_{x\to\rho_{A}^{-}}A(x)>1.$

If ${\mathcal{A}}^{*}$ is supercritical, then the radius of convergence of
$A^{\ast}(x)$ is the unique positive value $\kappa<\rho_{A}$ such that
$A(\kappa)=1$.

We say that ${\mathcal{A}}^{\ast}$ is _aperiodic_ if the greatest common
divisor of $\\{\operatorname{wt}(a);\;a\in{\mathcal{A}}\\}$ is 1.

In our setting, where the alphabet ${\mathcal{A}}$ will generally correspond
to the sum-indecomposable elements of a permutation class, aperiodicity is
satisfied since there is a letter of weight $1$. But even more generally it is
not a significant restriction, since we can simply divide all the weights by
their greatest common divisor. Supercriticality, on the other hand, is a more
fundamental property.

In the rest of Subsection 3.1, we assume that ${\mathcal{A}}^{\ast}$ is
supercritical, with $A(x)$ and $\kappa$ as above, and we fix a probability
measure on ${\mathcal{A}}$ defined by
$\mathbb{P}(a)=\kappa^{\operatorname{wt}(a)}$. This will be the underlying
probability measure whenever we speak of a random letter from ${\mathcal{A}}$.

Let $\overline{w}=\mathbb{E}[\operatorname{wt}(a)]$ denote the expected weight
of a letter from ${\mathcal{A}}$. Then

$\overline{w}=\sum_{a\in{\mathcal{A}}}\operatorname{wt}(a)\kappa^{\operatorname{wt}(a)}=\kappa
A^{\prime}(\kappa),$

where $A^{\prime}$ is the derivative of $A$, and $A^{\prime}(\kappa)$ is
finite since $A$ is analytic at $\kappa$.

As a technical tool, we will use the following concentration inequality, which
follows from standard probabilistic results; see e.g. the books of Dembo and
Zeitouni [Dembo, Chapter 2.2] or Flajolet and Sedgewick [Flajolet, Chapter
IX.10]. We include the proof here for completeness.

######  Proposition 3.8.

For every $\varepsilon>0$ there is a $\delta>0$ such that for a random word
$W=a_{1}a_{2}\dotsb a_{k}$ obtained by concatenating $k$ random independent
letters from ${\mathcal{A}}$, we have

$\displaystyle\mathbb{P}\bigl{(}\operatorname{wt}(W)\geq(1+\varepsilon)k\overline{w}\bigr{)}$
$\displaystyle\leq e^{-\delta k}$ and
$\displaystyle\mathbb{P}\bigl{(}\operatorname{wt}(W)\leq(1-\varepsilon)k\overline{w}\bigr{)}$
$\displaystyle\leq e^{-\delta k}.$

###### Proof.

Let $X$ be the random variable on ${\mathcal{A}}$ defined as
$X=\operatorname{wt}(a)$ where $a\in{\mathcal{A}}$ is a random letter. Define
the function $K(t)=\ln(\mathbb{E}[e^{tX}])=\ln\left(\sum_{k\geq
0}\mathbb{E}[X^{k}]\frac{t^{k}}{k!}\right)$. In probability theory, the
function $K$ is known as the ‘cumulant generating function’. It can also be
written as $K(t)=\ln\left(A(\kappa e^{t})\right)$. We may then easily check
that $K(t)$ is analytic at $t=0$ and has a Taylor series expansion of the form
$K(t)=\overline{w}t+O(t^{2})$ in a neighborhood of $t=0$.

Let $W=a_{1}a_{2}\dotsb a_{k}$ be a word of $k$ letters chosen independently
from ${\mathcal{A}}$, and let $X_{i}$ be the weight of $a_{i}$. In particular,
$X_{1},\dotsc,X_{k}$ are independent random variables of the same distribution
as $X$. Let $Y=X_{1}+X_{2}+\dotsb+X_{k}$.

Fix an $\varepsilon>0$ and write $w^{+}=(1+\varepsilon)\overline{w}$. Let $Q$
denote the event $Y\geq kw^{+}$, and let $\mathbb{1}_{Q}$ be the indicator
function of this event, i.e., the function equal to 1 when the event occurs
and 0 otherwise. Observe that for any $t\geq 0$, the function $\mathbb{1}_{Q}$
is bounded from above by $\exp(tY-tkw^{+})$. We then have

$\displaystyle\mathbb{P}(Y\geq kw^{+})$
$\displaystyle=\mathbb{E}[\mathbb{1}_{Q}]$
$\displaystyle\leq\mathbb{E}[\exp(tY-tkw^{+})]$
$\displaystyle=\exp(-tkw^{+})\mathbb{E}[\exp(tY)]$
$\displaystyle=\exp(-tkw^{+})\mathbb{E}\left[\prod_{i=1}^{k}\exp(tX_{i})\right]$
$\displaystyle=\exp(-tkw^{+})\prod_{i=1}^{k}\mathbb{E}\left[\exp(tX_{i})\right]$
$\displaystyle=\exp(-tkw^{+})\exp(kK(t))$
$\displaystyle=\exp\left(k(K(t)-tw^{+})\right).$

Recalling that $K(t)=\overline{w}t+O(t^{2})$, we can find a sufficiently small
value $t>0$ such that $K(t)<tw^{+}$. Choosing such a $t$ and putting
$\delta=tw^{+}-K(t)>0$, we obtain $\mathbb{P}(Y\geq kw^{+})\leq e^{-\delta
k}$, as claimed.

The second inequality of the proposition is proven by an analogous argument,
except now we consider the values $t\leq 0$. ∎

Our main concern will be to understand the structure of random words of fixed
weight, which is usually much more challenging than dealing with words of
fixed length. Let ${\mathcal{A}}^{\ast}_{n}$ be set of words of
${\mathcal{A}}^{\ast}$ of weight $n$. Clearly, ${\mathcal{A}}^{\ast}_{n}$ is
finite, and we will consider the uniform probability measure on this set,
i.e., the measure where every word $W\in{\mathcal{A}}^{\ast}_{n}$ has
probability $1/|{\mathcal{A}}^{\ast}_{n}|$.

To generate such a random word from $W\in{\mathcal{A}}^{\ast}_{n}$, we may use
the following process, known as _Boltzmann sampler with rejection_. The
process works in two phases, where in the first phase, it generates a random
word of weight at least $n$, and in the next phase, it rejects the generated
word if its weight is not exactly $n$. More precisely, the Boltzmann sampler
works as follows.

First phase. For $i=1,2,\dotsc$, select randomly and independently a letter
$a_{i}\in{\mathcal{A}}$. Stop as soon as $\operatorname{wt}(a_{1}a_{2}\dotsb
a_{i})\geq n$, and let $W=a_{1}a_{2}\dotsb a_{i}$ be the generated word.
Second phase. For the word $W$ generated by the first phase, check whether $W$
has weight $n$. If it does, the second phase succeeds, and $W$ is output. If
not, the second phase fails and the whole sampler is restarted.

Samplers of this form were analyzed by Duchon et al. [DFLS, Section 7]. Let us
summarize the main results of their analysis.

######  Fact 3.9 (Duchon et al. [DFLS]).

Suppose that ${\mathcal{A}}^{\ast}$ is aperiodic and supercritical. Then the
second phase of the Boltzmann sampler with rejection succeeds with probability
$\Omega(1)$. The word output by the sampler is a uniformly random element of
${\mathcal{A}}^{\ast}_{n}$, i.e., each word $W\in{\mathcal{A}}^{\ast}_{n}$ is
generated with probability $1/{|{\mathcal{A}}^{\ast}_{n}|}$.

We will use the Boltzmann sampler to obtain an insight into the structure of a
typical word in ${\mathcal{A}}^{\ast}_{n}$ as $n$ tends to infinity. For a
word $P=p_{1}p_{2}\dotsb p_{k}$, a _$P$ -block_ in another word
$W=w_{1}w_{2}\dotsb w_{n}$ is a sequence $w_{j+1}w_{j+2}\dotsb w_{j+k}$ of
consecutive letters such that $p_{i}=w_{j+i}$ for every $i=1,\dotsc,k$.

######  Proposition 3.10.

For every word $P=p_{1}p_{2}\dotsb p_{k}$ from ${\mathcal{A}}^{\ast}$, there
is an $\varepsilon\equiv\varepsilon_{P}>0$ such that, with probability at
least $1-\frac{1}{2^{\Omega(n)}}$, a uniformly random word
$X\in{\mathcal{A}}^{\ast}_{n}$ contains at least $\varepsilon n$ pairwise
disjoint $P$-blocks.

###### Proof.

The first phase of the Boltzmann sampler can equivalently be implemented by
the following procedure: first choose a sequence $V=a_{1}a_{2}\dotsb a_{n}$ of
$n$ random independent letters from ${\mathcal{A}}$, and then output the word
$W=a_{1}a_{2}\dotsb a_{i}$ determined as the shortest prefix of $V$ of weight
at least $n$.

Recall that $\overline{w}$ is the expected weight of a letter in
${\mathcal{A}}$. Define $m=\left\lfloor\frac{n}{2\overline{w}}\right\rfloor$.
We will consider two possible ‘bad’ outcomes of the above random procedure:
the first bad outcome is that the length $i$ of $W$ is smaller than $m$, the
second bad outcome is that the prefix of $V$ of length $m$ has fewer than
$\varepsilon n$ pairwise disjoint $P$-blocks, for an $\varepsilon>0$ to be
specified later. We will show that both bad outcomes have exponentially small
probability. Clearly, if neither of the two bad outcomes occurs, then the
first phase of the Boltzmann sampler generates a word with at least
$\varepsilon n$ pairwise disjoint $P$-blocks, and since the second phase
succeeds with constant probability, this implies that only an exponentially
small fraction of the words in ${\mathcal{A}}^{\ast}_{n}$ contain fewer than
$\varepsilon n$ pairwise disjoint $P$-blocks.

The probability of the first bad outcome (i.e., $i<m$) is at most as large as
the probability that the first $m$ letters of $V$ have weight at least $n\geq
2m\overline{w}$, which is exponentially small by Proposition 3.8.

To estimate the probability of the second bad outcome, let $Y$ be the prefix
of $V$ of length $m$. Define $q=\left\lfloor\frac{m}{k}\right\rfloor$, and
partition $Y$ into subwords as $Y_{1}Y_{2}\dotsb Y_{q}Z$, where
$Y_{1},\dotsc,Y_{q}$ all have length exactly $k$, and $Z$ is a possibly empty
word of length at most $k-1$. The words $Y_{1},\dotsc,Y_{q}$ are pairwise
independent, and each of them is a random word of length $k$. In particular,
there is a positive probability $\delta>0$ depending on $P$ such that for
every $j\in[q]$ we have $\mathbb{P}(Y_{j}=P)=\delta$.

There are, therefore, on average $\delta q$ values of $j$ for which $Y_{j}=P$,
and each such value corresponds to a $P$-block. By the standard
Chernoff–Hoeffding bound [Hoeffding], the probability that there are fewer
than $\delta q/2$ values of $j$ satisfying $Y_{j}=P$ is exponentially small in
$q$, and therefore also in $n$.

We conclude that the word output by the sampler, which is a uniformly random
word from ${\mathcal{A}}^{\ast}_{n}$, contains at least $\delta q/2$ disjoint
$P$-blocks, up to exceptions of exponentially small probability. Since
$q=\Omega(n)$ this completes the proof. ∎

##  4 Wilf collapse

In this section, we will present our two main results demonstrating Wilf
collapse in a permutation class ${\mathcal{C}}$ under different sets of
assumptions. The two results deal with sum-closed classes and with classes
with finitely many sum-indecomposables, respectively. Their proofs all follow
the same general strategy:

  * •

Represent the elements of ${\mathcal{C}}$ as words over the alphabet
consisting of the sum-indecomposable permutations in ${\mathcal{C}}$.

  * •

Using Corollary 3.7 characterise some “good” elements of ${\mathcal{C}}$ whose
equivalence classes with respect to $\equiv_{{\mathcal{C}}}$ are “large”,

  * •

Show that permutations in ${\mathcal{C}}$ are bad with “sufficiently small”
probability.

The number of Wilf classes for ${\mathcal{C}}$ among elements of size $n$ is
bounded above by the sum of the number of good permutations in
${\mathcal{C}}_{n}$ divided by the smallest size of a good Wilf class, and the
number of bad permutations in ${\mathcal{C}}_{n}$. Therefore, the scheme above
is sufficient to prove a Wilf collapse provided that “large” implies tending
to infinity, and “sufficiently small” means tending to 0. To obtain an
exponential Wilf collapse it is sufficient that “large” should mean “of
exponential size” and that the probability of a permutation being bad is
exponentially small.

###  4.1 Sum-closed classes

Let ${\mathcal{C}}$ be a sum-closed class. Take the alphabet ${\mathcal{A}}$
to consist of the sum-indecomposable permutations of ${\mathcal{C}}$ with the
weight of a letter simply being equal to its size. Then we already have an
obvious bijection between ${\mathcal{C}}$ and ${\mathcal{A}}^{\ast}$ which we
now treat as implicit, i.e., we make no distinction between a permutation in
${\mathcal{C}}$ and its representation as (the sum of) a sequence of sum-
indecomposable permutations. In particular, we say that ${\mathcal{C}}$ is
supercritical whenever ${\mathcal{A}}^{\ast}$ is. We also extend the
containment order on ${\mathcal{C}}$ to words of ${\mathcal{A}}^{\ast}$; that
is, for $W,V\in{\mathcal{A}}^{\ast}$ we write $W\leqslant V$ if the
permutation represented by $W$ is contained in the permutation represented by
$V$. Observe that this partial order on ${\mathcal{A}}^{\ast}$ is an embedding
order.

######  Theorem 4.1.

Any supercritical sum-closed class, ${\mathcal{C}}$, that contains an
incompatible pair has an exponential Wilf collapse, unless ${\mathcal{C}}$ is
the class of increasing permutations.

###### Proof.

Let ${\mathcal{C}}$ be a supercritical sum-closed class containing an
incompatible pair $(a,b)$ and not equal to the class of increasing
permutations. The set, ${\mathcal{A}}$, of sum-indecomposable permutations in
${\mathcal{C}}$ has at least the two elements $1$ and $21$. Let $c$ and $d$ be
two arbitrary distinct elements from ${\mathcal{A}}$. Consider the words
$X=bca$, $Y=bda$, $P=aXYb=abcabdab$, and $P^{\prime}=aYXb=abdabcab$. Notice
that both $P=aXYb$ and $P^{\prime}=aYXb$ are incompatible factorisations.

By Proposition 3.10, there is an $\varepsilon>0$ such that for every $n$, a
uniformly random permutation $\pi\in{\mathcal{C}}$ of order $n$ has a sum
decomposition in which there are at least $\varepsilon n$ disjoint $P$-blocks,
except for an exponentially small fraction of ‘bad’ permutations. By Corollary
3.7, if a permutation $\pi^{\prime}$ is obtained from $\pi$ by replacing some
$P$-blocks by $P^{\prime}$-blocks, then $\pi$ and $\pi^{\prime}$ are Wilf-
equivalent. In particular, the Wilf class of a permutation that has at least
$\varepsilon n$ disjoint $P$-blocks has size at least $2^{\varepsilon n}$. The
theorem follows. ∎

######  Corollary 4.2.

If ${\mathcal{C}}$ is a sum-closed class that contains 21 and has only
finitely many sum-indecomposable permutations, then ${\mathcal{C}}$ has an
exponential Wilf collapse.

###### Proof.

Such a class is clearly supercritical. It also has an incompatible pair, e.g.,
1 and any sum-indecomposable permutation of maximum size, so Theorem 4.1
applies. ∎

###  4.2 Classes with finitely many sum-indecomposables

The aim of this subsection is to prove the following result.

######  Theorem 4.3.

Any permutation class with finitely many sum-indecomposable permutations and
an unbounded growth function exhibits a Wilf collapse.

The proof of this result is rather technical so we will begin with a few words
about its general strategy. Let ${\mathcal{C}}$ be a permutation class with
finitely many indecomposables and an unbounded growth function. As in
Subsection 4.1, we will represent the elements of ${\mathcal{C}}$ as words
over the alphabet ${\mathcal{A}}$ of indecomposable elements of
${\mathcal{C}}$. However, not all words from ${\mathcal{A}}^{\ast}$ now
correspond to elements of ${\mathcal{C}}$, so we cannot directly use the
properties of ${\mathcal{A}}^{\ast}$ to prove the Wilf collapse of
${\mathcal{C}}$. Instead, we consider a finite state automaton over
${\mathcal{A}}$ that accepts only the words which represent elements of
${\mathcal{C}}$. The underlying graph of this automaton is directed and
acyclic except for loops on certain states. These loops represent certain sum-
closed subclasses of ${\mathcal{C}}$ whose elements occur as consecutive
subwords (“loop blocks”) within the elements of ${\mathcal{C}}$.

Since the classes corresponding to loop blocks are sum-closed, Corollary 4.2
applies to them, and so, unless the only symbol that allows for a loop at a
given state is $1$, they have exponential Wilf collapse. We will then show
that under suitable technical assumptions, which a random permutation of
${\mathcal{C}}$ satisfies with high probability, the Wilf equivalences within
the class generated by a loop block can be lifted to Wilf equivalences for the
whole class ${\mathcal{C}}$.

We begin with a general lemma dealing with the growth rate of a set of words
generated by a finite alphabet.

######  Lemma 4.4.

Let ${\mathcal{L}}$ be a finite alphabet, with every letter
$a\in{\mathcal{L}}$ having a positive integer weight $\operatorname{wt}(a)$.
Let $k$ be the largest weight of a letter of ${\mathcal{L}}$, and let
$\alpha_{i}$ be the number of letters in ${\mathcal{L}}$ of weight $i$, for
$i=1,\dotsc,k$. Assume that $\alpha_{1}=1$, i.e., there is a unique letter of
weight 1. Let $L(x)=\sum_{i=1}^{k}\alpha_{i}x^{i}$ be the generating
polynomial of ${\mathcal{L}}$.

The polynomial $1-L(x)$ has a unique positive real root $\rho$, this root
belongs to the interval $(0,1]$, has multiplicity 1, and any other complex
root $\lambda$ of $1-L(x)$ satisfies $|\lambda|>\rho$. Moreover, $\rho$ is
equal to $1$ if and only if $|{\mathcal{L}}|=1$. There are constants $c>0$ and
$\varepsilon>0$ such that
$|{\mathcal{L}}^{\ast}_{n}|=c\rho^{-n}+O((\rho+\varepsilon)^{-n})$.

###### Proof.

Noting that $\alpha_{1}=1$ and $\alpha_{2},\dotsc,\alpha_{k}$ are all
nonnegative, we observe that $1-L(0)=1$ and $1-L(1)\leq 0$, and therefore
there is a $\rho\in(0,1]$ such that $1-L(\rho)=0$. We also see that $\rho=1$
if and only if $L(x)=x$, or equivalently, $|{\mathcal{L}}|=1$. Since the
derivative of $1-L(x)$ is negative for every $x>0$, we conclude that $\rho$ is
the unique positive root of $1-L(x)$, and that it has multiplicity 1.

Suppose now that $\lambda$ is a complex root of $1-L(x)$, with
$|\lambda|\leq\rho$. We claim that $\lambda=\rho$. Let $\Re(z)$ denote the
real part of a complex number $z$. We then obtain

$1=\sum_{i=1}^{k}\alpha_{i}\lambda^{i}=\sum_{i=1}^{k}\alpha_{i}\Re(\lambda^{i})\leq\sum_{i=1}^{k}\alpha_{i}|\lambda|^{i}\leq\sum_{i=1}^{k}\alpha_{i}\rho^{i}=1.$

In particular, all the inequalities hold with equality. Since for each
$i\in[k]$, we have $\Re(\lambda^{i})\leq|\lambda|^{i}\leq\rho^{i}$, and since
$\alpha_{1}>0$, we easily deduce that $\lambda=\rho$.

The generating function of ${\mathcal{L}}^{\ast}$ is $L^{\ast}(x)=1/(1-L(x))$.
We see that $L(x)$ is a rational function that has a simple pole at $x=\rho$,
and any other pole has absolute value greater than $\rho+\varepsilon$, for
some $\varepsilon>0$. From this, the asymptotics of
$|{\mathcal{L}}^{\ast}_{n}|$ follow, by standard singularity analysis
[Flajolet]. ∎

We call the value $\rho^{-1}$ from the previous lemma the _growth rate_ of
${\mathcal{L}}^{\ast}$.

Suppose from now on that ${\mathcal{C}}$ is a permutation class with finitely
many sum-indecomposable permutations, and that its growth function is
unbounded. Let ${\mathcal{A}}$ be the set of sum-indecomposable permutations
in ${\mathcal{C}}$. By the above assumptions, ${\mathcal{A}}$ is finite and
contains at least two distinct elements, namely $1$ and $21$. Let $K$ denote,
from now on, the largest weight of a letter of ${\mathcal{A}}$.

As in Subsection 4.1, we will represent the permutations in ${\mathcal{C}}$ as
words over the alphabet ${\mathcal{A}}$, and assign to each letter of
${\mathcal{A}}$ the weight equal to the size of the corresponding sum-
indecomposable permutation. Since Corollary 4.2 deals with the sum-closed
case, suppose from now on that ${\mathcal{C}}$ is not sum-closed, i.e., not
every word in ${\mathcal{A}}^{\ast}$ corresponds to a permutation from
${\mathcal{C}}$.

Let $F$ be the set of minimal elements of ${\mathcal{A}}^{\ast}$ not belonging
to ${\mathcal{C}}$; in particular, we have
${\mathcal{C}}={\mathcal{A}}^{\ast}\cap\operatorname{Av}(F)$. By the classical
Higman Lemma [Higman], the set $F$ is finite. Let us write $f=|F|$ and
$F=\\{\phi^{1},\phi^{2},\dotsc,\phi^{f}\\}$. The forbidden permutations
$\phi^{i}$ will again be interpreted as words over ${\mathcal{A}}$. We let
$\ell_{i}$ denote the number of symbols of the word $\phi^{i}$.

For a word $W=a_{1}a_{2}\dotsb a_{m}\in{\mathcal{A}}^{\ast}$, let $W_{\leq i}$
denote its prefix $a_{1}a_{2}\dotsb a_{i}$, and $W_{\geq i}$ its suffix
$a_{i}a_{i+1}\dotsb a_{m}$. We will also use the notation $W_{<i}$ and
$W_{>i}$ for $W_{\leq i-1}$ and $W_{\geq i+1}$, respectively.

Let $W\in{\mathcal{A}}^{\ast}$ be a word. The _prefix state_ of $W$ is the
$f$-tuple $(p_{1},p_{2},\allowbreak\dotsc,p_{f})$ where $p_{i}$ is the length
of the longest prefix of $\phi^{i}$ that is contained in $W$, or in other
words, for every $i=1,\dotsc,f$, the word $W$ contains $\phi^{i}_{\leq p_{i}}$
but avoids $\phi^{i}_{\leq p_{i}+1}$.

We say that the prefix state $p=(p_{1},\dotsc,p_{f})$ is _valid_ , if
$p_{i}<\ell_{i}$ for each $i$. Observe that a word $W\in{\mathcal{A}}^{\ast}$
is in ${\mathcal{C}}$ if and only if its prefix state is valid. Let
${\mathcal{P}}$ be the set of all possible prefix states of the elements of
${\mathcal{C}}$. The empty word has prefix state $(0,0,\dotsc,0)$, which we
will call _the initial prefix state_.

For two prefix states $p=(p_{1},\dotsc,p_{f})$ and
$p^{\prime}=(p^{\prime}_{1},\dotsc,p^{\prime}_{f})$, we write $p\leq
p^{\prime}$ if $p_{i}\leq p^{\prime}_{i}$ for every $i\in[f]$, and we write
$p<p^{\prime}$ if $p\leq p^{\prime}$ and $p\neq p^{\prime}$.

Let $X$ be a word with a prefix state $p$, and let $a\in{\mathcal{A}}$ be a
symbol. The prefix state of the word $Y=Xa$ is then uniquely determined by $p$
and $a$. Moreover, if $p^{\prime}$ the prefix state of $Y$, then $p\leq
p^{\prime}$. If $p=p^{\prime}$, we say that the symbol $a$ is a _loop symbol
for $p$_, otherwise we say that $a$ is a _transition symbol from $p$ to
$p^{\prime}$_. The _loop alphabet of $p$_, denoted ${\mathcal{L}}_{p}$, is the
set of the loop symbols of $p$.

A symbol $a\in{\mathcal{A}}$ is in the loop alphabet of a valid prefix state
$p=(p_{1},\dotsc,p_{f})$ if and only if for each $i=1,\dotsc,f$, the
$(p_{i}+1)$-st symbol of $\phi^{i}$ is not contained in $a$. In particular,
the loop alphabet of $p$ is a down-set of ${\mathcal{A}}$.

Consider a word $W=a_{1}a_{2}\dotsb a_{m}$ from ${\mathcal{C}}$. We will say
that $W$ has a _prefix transition_ at position $i$ if $W_{<i}$ has a different
prefix state than $W_{\leq i}$. Let $k$ be the number of prefix transitions in
$W$, and let $i(1)<i(2)<\dotsb<i(k)$ be the positions where the transitions
occur. We call the sequence of prefix states $p(0)<p(1)<\dotsb<p(k)$ such that
the transition at position $i(j)$ is from $p(j-1)$ to $p(j)$ the _prefix
transition path_ of $W$. The words in ${\mathcal{C}}$ determine only finitely
many possible prefix transition paths. The word $W$ can then be written as

$W=B_{0}a_{i(1)}B_{1}a_{i(2)}B_{2}\dotsb B_{k-1}a_{i(k)}B_{k},$ (2)

where $B_{j}$ is a (possibly empty) word over the loop alphabet
${\mathcal{L}}_{p(j)}$. We call $B_{j}$ the _$j$ -th loop block_ of $W$, and
we call the right-hand side of (2) the _prefix decomposition_ of $W$.

Conversely, suppose that $p(0)<p(1)<\dotsb<p(k)$ is an increasing sequence of
valid prefix states where $p(0)$ is the initial state, that
$t_{j}\in{\mathcal{A}}$ is a transition symbol from $p(j-1)$ to $p(j)$, and
that $B_{j}$ is a possibly empty word over the alphabet
${\mathcal{L}}_{p(j)}$. Then the expression

$B_{0}t_{1}B_{1}t_{2}B_{2}\dotsb B_{k-1}t_{k}B_{k}$

is the prefix decomposition of a word from ${\mathcal{C}}$ whose prefix
transition path is $p(0)<p(1)<\dotsb<p(k)$.

For a prefix state $p\in{\mathcal{P}}$, the _growth rate of $p$_, denoted
$\gamma_{p}$, is the growth rate of the language ${\mathcal{L}}_{p}^{\ast}$.
The _dominant growth rate_ of ${\mathcal{C}}$ is the value
$\gamma=\max_{p\in{\mathcal{P}}}\gamma_{p}$. We say that a prefix state $p$ is
_dominant_ if $\gamma_{p}=\gamma$, and we call a loop block in a prefix
decomposition _dominant_ if it corresponds to a dominant state. Let $D$ denote
the largest number of dominant states that can appear on a single prefix
transition path of a word from ${\mathcal{C}}$.

######  Proposition 4.5.

Let $T=(p(0)<p(1)<\dotsb<p(k))$ be a prefix transition path, and let
$\tau=(t_{1},\dotsc,t_{k})\in{\mathcal{A}}^{k}$ be a sequence of symbols where
$t_{j}$ is a transition symbol from $p(j-1)$ to $p(j)$. Let
${\mathcal{C}}_{n}(T,\tau)$ be the set of words in ${\mathcal{C}}_{n}$ that
have prefix transition path $T$, with $j$-th transition on the symbol $t_{j}$.
Let $\gamma_{T}$ be the maximum of $\gamma_{p(i)}$ for $i\in\\{0,\dotsc,k\\}$,
and let $d_{T}$ be the number of values $i\in\\{0,\dotsc,k\\}$ for which
$\gamma_{p(i)}=\gamma_{T}$.

Then
$|{\mathcal{C}}_{n}(T,\tau)|=\Theta\left(n^{d_{T}-1}\gamma_{T}^{n}\right).$
Consequently, $|{\mathcal{C}}_{n}|=\Theta\left(n^{D-1}\gamma^{n}\right).$

###### Proof.

Let $n^{\prime}=n-\sum_{i=1}^{k}\operatorname{wt}(t_{i})$. Let $\gamma_{j}$ be
the growth rate of $p(j)$. To count the words $W\in{\mathcal{C}}_{n}(T,\tau)$,
we will count their corresponding prefix decompositions
$W=B_{0}t_{1}B_{1}\dotsb B_{k-1}t_{k}B_{k}$, or equivalently, the
$(k+1)$-tuples $(B_{0},B_{1},\dotsc,B_{k})$ with
$\sum_{j=0}^{k}\operatorname{wt}(B_{j})=n^{\prime}$, where $B_{j}$ is a word
over the alphabet ${\mathcal{L}}_{p(j)}$.

Define the sets of indices
$I=\\{i\in\\{0,\dotsc,k\\};\;\gamma_{i}=\gamma_{T}\\}$ and
$J=\\{0,\dotsc,k\\}\setminus I$. In particular, $|I|=d_{T}$. To estimate the
number of prefix decompositions of elements of ${\mathcal{C}}_{n}(T,\tau)$, we
will first fix two integers $n_{I}$ and $n_{J}$ with $n_{I}+n_{J}=n^{\prime}$,
and then count the decompositions in which the loop blocks with growth rate
$\gamma_{T}$ have total weight $n_{I}$, and the remaining loop blocks have
total weight $n_{J}$.

To count the possible choices for $(B_{i};\;i\in I)$ with $\sum_{i\in
I}\operatorname{wt}(B_{i})=n_{I}$, we first choose a $d_{T}$-tuple
$(n_{i};\;i\in I)$ satisfying $\sum_{i\in I}n_{i}=n_{I}$, and then choose
$B_{i}\in{\mathcal{L}}^{\ast}_{p(i)}$ of weight $n_{i}$. The number of the
suitable $d_{T}$-tuples $(n_{i};\;i\in I)$ is $\Theta(n_{I}^{d_{T}-1})$, and
for any $i\in I$, there are $\Theta(\gamma_{T}^{n_{i}})$ choices for $B_{i}$
by Lemma 4.4. Overall, the number of possible choices of $(B_{i};\;i\in I)$
for a fixed $n_{I}$ is $\Theta(n_{I}^{d_{T}-1}\gamma_{T}^{n_{I}})$.

To count the choices of $(B_{j};\;j\in J)$ satisfying $\sum_{j\in
J}\operatorname{wt}(B_{j})=n_{J}$, let $\delta>0$ be a value smaller than
$\gamma_{T}$ but larger than $\gamma_{j}$ for any $j\in J$. We then have
$\Theta(n_{J}^{|J|-1})$ ways to choose a $|J|$-tuple $(n_{j};j\in J)$ with
$\sum_{j\in J}n_{j}=n_{J}$, and for each $j\in J$,
$\Theta(\gamma_{j}^{n_{j}})$ ways to choose a block
$B_{j}\in{\mathcal{L}}_{p(j)}^{\ast}$ of weight $n_{j}$. The number of choices
for $(B_{j};\;j\in J)$ is thus $\mathcal{O}(\delta^{n_{J}})$.

This yields

$|{\mathcal{C}}_{n}(T,\tau)|=\sum_{(n_{I},n_{J})}\mathcal{O}(\delta^{n_{J}})\Theta\left(n_{I}^{d_{T}-1}\gamma_{T}^{n_{I}}\right),$

where the summation is over all pairs $(n_{I},n_{J})$ satisfying
$n_{I}+n_{J}=n^{\prime}$. We see that the summand corresponding to $n_{J}=0$
in this sum already has order $\Theta(n^{d_{T}-1}\gamma^{n})$, so we only need
an upper bound for $|{\mathcal{C}}_{n}(T,\tau)|$ of the same order. Such an
upper bound can be obtained as follows:

$\displaystyle|{\mathcal{C}}_{n}(T,\tau)|$
$\displaystyle=\sum_{(n_{I},n_{J})}\mathcal{O}(\delta^{n_{J}})\Theta\left(n_{I}^{d_{T}-1}\gamma_{T}^{n_{I}}\right)$
$\displaystyle\leq\Theta\left(n^{d_{T}-1}\gamma_{T}^{n}\right)\sum_{(n_{I},n_{J})}\frac{\delta^{n_{J}}}{\gamma_{T}^{n_{J}}}$
$\displaystyle\leq\Theta\left(n^{d_{T}-1}\gamma_{T}^{n}\right)\sum_{n_{J}=0}^{\infty}\left(\frac{\delta}{\gamma_{T}}\right)^{n_{J}}$
$\displaystyle\leq\Theta\left(n^{d_{T}-1}\gamma_{T}^{n}\right).$

The bound for $|{\mathcal{C}}_{n}|$ then follows by summing
$|{\mathcal{C}}_{n}(T,\tau)|$ over all possible (finitely many) choices of $T$
and $\tau$, noting that these choices are independent of $n$. ∎

######  Lemma 4.6.

Let $W$ be a uniformly random word from the set ${\mathcal{C}}_{n}$. With
probability $1-2^{-\Omega(\sqrt{n})}$, the total weight of the non-dominant
loop blocks in the prefix decomposition of $W$ is smaller than $\sqrt{n}$.

###### Proof.

Proposition 4.5 shows that the fraction of words from ${\mathcal{C}}_{n}$
whose prefix transition path $T$ has no dominant state is exponentially small,
so let us focus on words with at least one dominant loop state. Applying the
argument and the notation of the proof of Proposition 4.5 to such $T$, we have
$\gamma_{T}=\gamma$, $d_{T}\leq D$, and the number of words in
${\mathcal{C}}_{n}(T,\tau)$ whose non-dominant loop blocks have total weight
at least $\sqrt{n}$ is at most

$\displaystyle\sum_{n_{J}=\sqrt{n}}^{n}\\!\mathcal{O}\left(\delta^{n_{J}}n^{D-1}\gamma^{n-n_{J}}\right)$
$\displaystyle\leq\mathcal{O}\left(n^{D-1}\gamma^{n}\right)\sum_{n_{J}=\sqrt{n}}^{\infty}\left(\frac{\delta}{\gamma}\right)^{n_{J}}\leq\mathcal{O}\left(n^{D-1}\gamma^{n}\left(\frac{\delta}{\gamma}\right)^{\\!\sqrt{n}}\right).$

The lemma follows. ∎

Recall that $F=\\{\phi^{1},\dotsc,\phi^{f}\\}$ is the set of minimal elements
of ${\mathcal{A}}^{\ast}$ not belonging to ${\mathcal{C}}$, and that
$\ell_{j}$ is the length of $\phi^{j}$. To proceed with our argument, we now
need to also start considering suffix states of a word, which are analogous to
prefix states. The _suffix state_ of a word $W\in{\mathcal{C}}$ is the
$f$-tuple $(s_{1},\dotsc,s_{f})$ where $s_{j}$ is the length of the longest
suffix of $\phi^{j}$ contained in $W$. We say that a suffix state
$s=(s_{1},\dotsc,s_{f})$ is _valid_ if $s_{j}<\ell_{j}$ for each $j$, and we
let ${\mathcal{S}}$ be the set of all the possible suffix states of the words
from ${\mathcal{C}}$ (which are necessarily valid).

In analogy with prefix states, we can associate to a suffix state
$s\in{\mathcal{S}}$ a _suffix loop alphabet_ ${\mathcal{L}}^{\leftarrow}_{s}$,
which is the set of all the symbols $a\in{\mathcal{A}}$ such that if $W$ has
suffix state $s$ then $aW$ has suffix state $s$ as well. We also say that a
symbol $b$ is a suffix transition symbol from $s$ to $s^{\prime}$, if for a
word $W$ of suffix state $s$, the word $bW$ has suffix state $s^{\prime}$.

We can also define suffix decompositions, analogous to their prefix
counterparts, but obtained when scanning a word from right to left. We say
that a word $W=a_{1}a_{2}\dotsb a_{m}\in{\mathcal{C}}$ has a _suffix
transition_ at position $i$ if $W_{\geq i}$ has a different suffix state than
$W_{>i}$. Let $i(1)>i(2)>\dotsb>i(k)$ be all the positions where $W$ has a
suffix transition, ordered right to left, and let $s(0)<s(1)<\dotsb<s(k)$ be
the corresponding suffix transition path; that is, $W_{>i(j)}$ has suffix
state $s(j-1)$ and $W_{\geq i(j)}$ has suffix state $s(j)$. The _suffix
decomposition_ of $W$ then takes the form $W=B_{k}a_{i(k)}B_{k-1}\dotsb
B_{1}a_{i(1)}B_{0}$, where $B_{j}$ is a word over the suffix loop alphabet of
$s(j)$.

Suffix decompositions satisfy analogous properties as their prefix
counterparts. For instance, Proposition 4.5 and Lemma 4.6 remain true when
restated in the setting of suffix decompositions. This implies, in particular,
that the largest growth rate of a suffix state is the same as the largest
growth rate $\gamma$ of a prefix state, and the maximum number of dominant
blocks in a suffix decomposition is the same as the maximum number $D$ of
dominant blocks in a prefix decomposition.

Let $p=(p_{1},\dotsc,p_{f})$ be a prefix state of a word $X$, and let
$s=(s_{1},\dotsc,s_{f})$ be a suffix state of a word $Y$. Recall that
$\ell_{i}$ is the length of the forbidden word $\phi^{i}\in F$. We say that
the two states $p$ and $s$ _overlap_ , if for some $i\in[f]$, we have
$p_{i}+s_{i}\geq\ell_{i}$. The inequality $p_{i}+s_{i}\geq\ell_{i}$ holds if
and only if $XY$ contains $\phi^{i}$. In particular, $p$ and $s$ overlap if
and only if $XY$ is not in ${\mathcal{C}}$. An invalid prefix state overlaps
with any suffix state and vice versa. If $p$ and $s$ do not overlap, we say
that they are _compatible_.

######  Lemma 4.7.

Let $X$ be a word with $d_{X}$ dominant loop blocks in its prefix
decomposition, and let $Y$ be a word with $d_{Y}$ dominant loop blocks in its
suffix decomposition. If $XY$ is in ${\mathcal{C}}$, then $d_{X}+d_{Y}\leq
D+1$.

###### Proof.

If $d_{X}=0$ or $d_{Y}=0$, the claim follows trivially, so assume that $d_{X}$
and $d_{Y}$ are both positive.

Let $T_{X}$ be the prefix transition path of $X$ and $T_{Y}$ the suffix
transition path of $Y$. Let ${\mathcal{C}}_{n}(T_{X})$ be the subset of
${\mathcal{C}}_{n}$ of those words that have prefix transition path $T_{X}$,
and ${\mathcal{C}}^{\leftarrow}_{n}(T_{Y})$ be the subset of
${\mathcal{C}}_{n}$ of words whose suffix transition path is $T_{Y}$. In
particular, any word in ${\mathcal{C}}_{n}(T_{X})$ has prefix state $p$, while
words in ${\mathcal{C}}^{\leftarrow}_{n}(T_{Y})$ have suffix state $s$. This
means that a concatenation of a word from ${\mathcal{C}}_{n}(T_{X})$ with a
word from ${\mathcal{C}}^{\leftarrow}_{n}(T_{Y})$ yields a word from
${\mathcal{C}}_{2n}$. With the help of Proposition 4.5, we get

$|{\mathcal{C}}_{2n}|\geq|{\mathcal{C}}_{n}(T_{X})|\cdot|{\mathcal{C}}^{\leftarrow}_{n}(T_{Y})|=\Theta(n^{d_{X}-1}\gamma^{n})\cdot\Theta(n^{d_{Y}-1}\gamma^{n})=\Theta(n^{d_{X}+d_{Y}-2}\gamma^{2n}).$

On the other hand, we know that
$|{\mathcal{C}}_{2n}|=\Theta(n^{D-1}\gamma^{2n})$. The lemma follows. ∎

Let us say that a prefix state $p^{\prime}\in{\mathcal{P}}$ is a _prefix
successor_ of $p\in{\mathcal{P}}$ if $p^{\prime}\neq p$ and there is a symbol
$b\in{\mathcal{A}}$ which is a transition symbol from $p$ to $p^{\prime}$.
Suffix successors are defined analogously.

For a prefix state $p\in{\mathcal{P}}$ and a suffix state $s\in{\mathcal{S}}$,
we say that $p$ and $s$ _match_ , if they are compatible, but every prefix
successor of $p$ overlaps with $s$, and every suffix successor of $s$ overlaps
with $p$.

As an example, consider ${\mathcal{A}}=\\{a,b,c,d\\}$ and
$F=\\{\phi^{1},\phi^{2}\\}$ with $\phi^{1}=abc$ and $\phi^{2}=dbdbc$. Let
$X=da$ and $Y=c$. Then $X$ has prefix state $p=(1,1)$ and $Y$ has suffix state
$s=(1,1)$. The two states match: the only prefix successor of $p$ is the state
$(2,2)$ which overlaps $s$, and the only suffix successor of $s$, namely
$(2,2)$, overlaps $p$. Consider now the word $X^{\prime}=dba$: its prefix
state $p^{\prime}=(1,2)$ is also compatible with $s$, but it does not match
with $s$, since it has the successor $(1,3)$ compatible with $s$. Notice that,
perhaps non-intuitively, although $p$ and $s$ match and $p<p^{\prime}$ (in
fact $X<X^{\prime}$), the two compatible states $p^{\prime}$ and $s$ do not
match.

######  Lemma 4.8.

If $p\in{\mathcal{P}}$ and $s\in{\mathcal{S}}$ match, then
${\mathcal{L}}_{p}={\mathcal{L}}^{\leftarrow}_{s}$.

###### Proof.

Suppose for contradiction that
${\mathcal{L}}_{p}\neq{\mathcal{L}}^{\leftarrow}_{s}$. Assume, without loss of
generality, that there is a symbol
$b\in{\mathcal{L}}_{p}\setminus{\mathcal{L}}^{\leftarrow}_{s}$. Consider a
word $X$ with prefix state $p$ and a word $Y$ with suffix state $s$. Since $p$
and $s$ are compatible, $XY$ is in ${\mathcal{C}}$. Note that since $b$ is in
${\mathcal{L}}_{p}$, $Xb$ has prefix state $p$. Let $s^{\prime}$ be the suffix
state of $bY$. Then $s^{\prime}$ is a suffix successor of $s$, and therefore
it overlaps with $p$. Then the word $W=XbY$ is in ${\mathcal{C}}$, since the
prefix state of $Xb$ is compatible with the suffix state of $Y$; on the other
hand, $W$ is not in ${\mathcal{C}}$, since the suffix state of $bY$ overlaps
the prefix state of $X$. This is a contradiction. ∎

######  Lemma 4.9.

Let $p\in{\mathcal{P}}$ and $s\in{\mathcal{S}}$ be a pair of compatible states
with ${\mathcal{L}}_{p}={\mathcal{L}}^{\leftarrow}_{s}$. Then the following
are equivalent:

  1. (I)

The states $p$ and $s$ do not match.

  2. (II)

The state $p$ has a prefix successor compatible with $s$.

  3. (III)

The state $s$ has a suffix successor compatible with $p$.

  4. (IV)

There is a symbol $b\in{\mathcal{A}}\setminus{\mathcal{L}}_{p}$ such that for
any word $X$ with prefix state $p$ and any word $Y$ with suffix state $s$, the
word $XbY$ is in ${\mathcal{C}}$.

###### Proof.

If (IV) holds, then the prefix state of $Xb$ is a prefix successor of $p$
compatible with $s$, while the suffix state of $bY$ is a suffix successor of
$s$ compatible with $p$, so (II) and (III) hold as well, and clearly both (II)
and (III) implies (I). We also easily see that (II) implies (IV) and (III)
implies (IV), and therefore (II), (III) and (IV) are equivalent. Finally, (I)
implies that (II) or (III) holds, and therefore (I) implies (IV), completing
the proof. ∎

######  Lemma 4.10.

Let $X$ be a word with prefix state $p$ and with $d_{X}$ dominant blocks in
its prefix decomposition, and $Y$ a word with suffix state $s$ and $d_{Y}$
dominant blocks in its suffix decomposition. Suppose that $p$ and $s$ are
compatible, that $d_{X}+d_{Y}=D+1$, that
${\mathcal{L}}_{p}={\mathcal{L}}^{\leftarrow}_{s}$, and that the state $p$
(and therefore also $s$) is dominant. Then the two states $p$ and $s$ match.

###### Proof.

Suppose that $p$ and $s$ do not match. Then, by part (IV) of Lemma 4.9, there
is a symbol $b\in{\mathcal{A}}\setminus{\mathcal{L}}_{p}$ such that $XbY$ is
in ${\mathcal{C}}$. Let $U$ be the word obtained by concatenating all the
symbols of ${\mathcal{L}}_{p}$ in any order, and let $W$ be the concatenation
of $|{\mathcal{P}}|$ disjoint copies of $U$. Consider the word $Z=XbWY$. Since
$W$ is a word over the alphabet ${\mathcal{L}}_{p}$, which is equal to
${\mathcal{L}}^{\leftarrow}_{s}$, we know that $WY$ has the same suffix state
as $Y$, namely $s$. Since the prefix state of $Xb$ is compatible with $s$
(recall that $XbY\in{\mathcal{C}}$), we conclude that $XbWY$ is in
${\mathcal{C}}$.

We claim that the prefix decomposition of $XbW$ has more dominant blocks than
the prefix decomposition of $X$, i.e., $XbW$ has at least $d_{X}+1$ dominant
blocks. To see this, note that the prefix decomposition of a word in
${\mathcal{C}}$ has at most $|{\mathcal{P}}|-1$ transitions. This means that
in $W$, there is a copy of $U$ which does not contain any prefix transition.
This copy of $U$ is thus entirely contained in a single loop block $B$, whose
corresponding loop alphabet therefore contains all the symbols of
${\mathcal{L}}_{p}$. Since ${\mathcal{L}}_{p}$ is dominant by assumption, the
loop block $B$ is also dominant. Moreover, $B$ is entirely contained in $W$,
since $b$ is a transition symbol by construction. Thus, $XbW$ has at least
$d_{X}+1$ dominant blocks. This contradicts Lemma 4.7, applied to the
decomposition of $Z$ into $XbW$ and $Y$. ∎

We remark that the assumptions of Lemma 4.10 are actually redundant: the lemma
remains true even without assuming that
${\mathcal{L}}_{p}={\mathcal{L}}^{\leftarrow}_{s}$ and that $p$ and $s$ are
dominant. In fact, these two assumptions are themselves consequences of
$d_{X}+d_{Y}=D+1$. However, we will not need this stronger fact.

Fix now the constant $Q=3(|{\mathcal{P}}|+|{\mathcal{S}}|)$. The choice of $Q$
guarantees that whenever a word $W\in{\mathcal{C}}$ is expressed as a
concatenation of $Q$ subwords $W=W_{1}W_{2}\dotsb W_{Q}$, there will be three
consecutive subwords $W_{i-1},W_{i},W_{i+1}$ such that none of them contains a
prefix transition or a suffix transition of $W$; this is because each
$W\in{\mathcal{C}}$ has at most $|{\mathcal{P}}|-1$ prefix transitions and at
most $|{\mathcal{S}}|-1$ suffix transitions.

An _equitable partition_ of a word $W\in{\mathcal{C}}_{n}$ is the expression
$W=W_{1}W_{2}\dotsb W_{Q}$, where the $W_{j}$ are chosen in such a way that
for every $j\in[Q]$, the prefix $W_{1}W_{2}\dotsb W_{j}$ is the shortest
prefix of $W$ whose weight is at least $jn/Q$. We call $W_{j}$ the _$j$ -th
slice_ of the equitable partition. Recall that $K$ is the largest weight of a
symbol in ${\mathcal{A}}$, and note that the above definition guarantees that
$jn/Q\leq\operatorname{wt}(W_{1}\dotsb W_{j})<jn/Q+K$ for every $j\in[Q]$. In
particular, each $W_{j}$ satisfies $n/Q-K<\operatorname{wt}(W_{j})<n/Q+K$.

A slice $W_{j}$ in the equitable partition of a word $W\in{\mathcal{C}}_{n}$
is _free_ if it does not contain any prefix transition or suffix transition of
$W$. This means that in the prefix decomposition of $W$, as well as in the
suffix decomposition of $W$, the free slice belongs to a single loop block.
Our choice of $Q$ guarantees that the equitable partition of any word
$W\in{\mathcal{C}}$ contains three consecutive free slices. Let
${\mathcal{C}}_{n}(j)$ be the subset of ${\mathcal{C}}_{n}$ containing the
words whose $j$-th slice is free.

Recall that $D$ is the largest number of dominant loop blocks in a prefix
decomposition of a word from $W$, which is also equal to the largest number of
dominant loop blocks in a suffix decomposition of a word in $W$. We say that a
word $W\in{\mathcal{C}}_{n}$ is _typical_ , if for every free slice $W_{j}$ in
the equitable partition of $W$, the following conditions hold:

  1. 1.

$W_{j}$ is contained in a dominant loop block both in the prefix decomposition
of $W$ and in the suffix decomposition of $W$.

  2. 2.

Let $X_{j}=W_{1}W_{2}\dotsb W_{j-1}$ and $Y_{j}=W_{j+1}W_{j+2}\dotsb W_{Q}$.
Let $d_{X}$ be the number of dominant loop blocks in the prefix decomposition
of $X_{j}$, and let $d_{Y}$ be the number of dominant loop blocks in the
suffix decomposition of $Y_{j}$. Then $d_{X}+d_{Y}=D+1$.

  3. 3.

With $X_{j}$ and $Y_{j}$ as above, let $p_{j}$ be the prefix state of $X_{j}$
and let $s_{j}$ be the suffix state of $Y_{j}$. Then $p_{j}$ and $s_{j}$
match.

  4. 4.

Let ${\mathcal{L}}_{j}$ be the prefix loop alphabet of the state $p_{j}$. Then
for any word $P$ of length $\max\\{4,|{\mathcal{L}}_{j}|\\}$ over the alphabet
${\mathcal{L}}_{j}$, $W_{j}$ contains at least $\sqrt{n}$ disjoint $P$-blocks.

######  Lemma 4.11.

A uniformly random word $W\in{\mathcal{C}}_{n}$ is typical with probability
$1-\mathcal{O}(1/n)$.

###### Proof.

Lemma 4.6 shows that with probability $1-2^{-\Omega(\sqrt{n})}$, the total
weight of non-dominant loop blocks in $W$ is at most $\sqrt{n}$, and in
particular, for $n$ large enough, no slice can be contained in a single non-
dominant loop block. Therefore, any free slice is contained in a dominant loop
block, both in the prefix and in the suffix decomposition.

Let $W_{j}$ be a free slice, and let $X_{j}$, $Y_{j}$, $p_{j}$ and $s_{j}$ be
as in the definition of typical word. Let ${\mathcal{L}}_{j}$ be the prefix
loop alphabet of $p_{j}$, and let ${\mathcal{L}}^{\leftarrow}_{j}$ be the
suffix loop alphabet of $s_{j}$. Define
${\mathcal{L}}={\mathcal{L}}_{j}\cap{\mathcal{L}}^{\leftarrow}_{j}$. Since
$W_{j}$ contains no prefix or suffix transitions, all its symbols belong to
${\mathcal{L}}$.

Let us prove that with high probability,
${\mathcal{L}}_{j}={\mathcal{L}}^{\leftarrow}_{j}$. Suppose that this is not
the case, and without loss of generality assume that ${\mathcal{L}}$ is a
proper subset of ${\mathcal{L}}_{j}$. As we have seen, $p_{j}$ and $s_{j}$ are
(with high probability) dominant states, so they both have growth rate
$\gamma$. Since ${\mathcal{L}}$ is a proper subset of ${\mathcal{L}}_{j}$, we
may deduce from Lemma 4.4 that the growth rate of ${\mathcal{L}}^{*}$ is
strictly smaller than $\gamma$. Let $\gamma_{\mathcal{L}}$ be the growth rate
of ${\mathcal{L}}^{\ast}$.

Let $Z$ denote the word $X_{j}Y_{j}$. From the knowledge of $j$ and $Z$, we
can uniquely recover the first $j-1$ slices $W_{1},\dotsc,W_{j-1}$, and
therefore also $Y_{j}$, $p_{j}$, $s_{j}$ and ${\mathcal{L}}$. Also,
$\operatorname{wt}(Z)$ can take at most $2K-1$ values, since

$n(1-1/Q)-K<\operatorname{wt}(Z)<n(1-1/Q)+K.$

It follows that there are $\mathcal{O}(n^{D-1}\gamma^{n(1-1/Q)})$ possible
choices of $j$ and $Z$, and for each such choice, no more than
$\mathcal{O}(\gamma_{\mathcal{L}}^{n/Q})$ choices for $W_{j}$. In total there
are at most

$\mathcal{O}(n^{D-1}\gamma^{n(1-1/Q)}\gamma_{\mathcal{L}}^{n/Q})=o(|{\mathcal{C}}_{n}|/n)$

possible words $W\in{\mathcal{C}}_{n}$ that have a free slice $W_{j}$ with
${\mathcal{L}}_{j}\neq{\mathcal{L}}^{\leftarrow}_{j}$.

Focus now on the situation when
${\mathcal{L}}_{j}={\mathcal{L}}^{\leftarrow}_{j}={\mathcal{L}}$ for every $j$
such that $W_{j}$ is a free slice. Let us fix a value of $j\in[Q]$, and let us
prove that there are at most $O(|{\mathcal{C}}_{n}|/n)$ words
$W\in{\mathcal{C}}_{n}(j)$ for which $d_{X}+d_{Y}<D+1$. We already know from
the previous arguments that we may restrict our attention to cases when
$W_{j}$ is inside a dominant loop block both in the prefix and the suffix
decomposition, which implies that $d_{X}$ and $d_{Y}$ are both nonzero.

Define $m=n/Q$. Note that $\operatorname{wt}(X_{j})$ can only take one of the
$K$ values in the range $[(j-1)m,(j-1)m+K)$, and similarly,
$\operatorname{wt}(Y_{j})$ is in the range $((Q-j)m-K,(Q-j)m]$ and
$\operatorname{wt}(W_{j})$ is in $(m-K,m+K)$.

From Lemma 4.4, the number of possible choices for $X_{j}$ and $Y_{j}$ is,
respectively, $\Theta(m^{d_{X}-1}\gamma^{(j-1)m})$ and
$\Theta(m^{d_{Y}-1}\gamma^{(Q-j)m})$. Together with the $\Theta(\gamma^{m})$
choices for $W_{j}\in{\mathcal{L}}^{\ast}_{m}$, this yields no more than
$\mathcal{O}(m^{d_{X}+d_{Y}-2}\gamma^{Qm})\leq\mathcal{O}(|{\mathcal{C}}_{n}|/n)$
possibilities for a word $W\in{\mathcal{C}}_{n}(j)$ that fails to satisfy
$d_{X}+d_{Y}=D+1$.

By Lemma 4.10, the above conditions already imply that $p_{j}$ and $s_{j}$
match with probability $1-\mathcal{O}(1/n)$.

To prove the last condition of typicality, choose a uniformly random
$W\in{\mathcal{C}}_{n}(j)$ for some fixed $j$. Let $W^{\prime}_{j}$ be a word
over ${\mathcal{L}}^{\ast}$ that has the same weight and the same final symbol
as $W_{j}$, and define $W^{\prime}=X_{j}W^{\prime}_{j}Y_{j}$. Note that
$W^{\prime}$ again belongs to ${\mathcal{C}}_{n}(j)$ and that $W^{\prime}_{j}$
is its $j$-th slice (the reason we require that $W^{\prime}_{j}$ has the same
final symbol as $W_{j}$ is to ensure that the boundary between the $j$-th and
$(j+1)$-st slice is preserved). In particular, for a uniformly random
$W\in{\mathcal{C}}_{n}(j)$, the word obtained from $W_{j}$ by removing its
last symbol is a uniformly random word over ${\mathcal{L}}^{\ast}$, that is,
any two words from ${\mathcal{L}}^{\ast}$ of the same weight are equally
likely to be obtained this way. From Proposition 3.10, we then deduce that,
for $n$ large enough and up to exponentially small probability, for every word
$P\in{\mathcal{L}}^{*}$ of constant length, $W_{j}$ has at least $\sqrt{n}$
disjoint $P$-blocks. Since with probability $1-\mathcal{O}(1/n)$,
${\mathcal{L}}$ is equal to ${\mathcal{L}}_{j}$, the last condition of
typicality follows. ∎

We are now almost ready to prove Theorem 4.3. For the final argument, we will
distinguish two cases. First, we will deal with classes of exponential growth,
i.e., those with $\gamma>1$. Equivalently, those are the classes whose
dominant loop alphabets contain more than one element.

Next, we will handle the classes with $\gamma=1$, i.e., those whose every loop
alphabet is either empty or contains the single symbol $1$. In order to have
unbounded growth, such a class must then satisfy $D>1$.

######  Proposition 4.12.

Any permutation class ${\mathcal{C}}$ with growth rate greater than 1 and with
finitely many sum-indecomposables exhibits a Wilf collapse.

###### Proof.

It is enough to show that every typical word $W\in{\mathcal{C}}_{n}$ belongs
to a Wilf class of size $2^{\Omega(\sqrt{n})}$. We will assume throughout that
$n$ is large enough in comparison to the constants $K$, $D$ and $Q$.

Figure 1: Illustration of the proof of Proposition 4.12

Choose a typical word $W\in{\mathcal{C}}_{n}$, and let $W_{1}W_{2}\dotsb
W_{Q}$ be its equitable partition. By the choice of $Q$, we know that there is
an index $j\in\\{2,\dotsc,Q-1\\}$ such that the three slices $W_{j-1}$,
$W_{j}$ and $W_{j+1}$ are all free. Write $W$ as $W=XW_{j-1}W_{j}W_{j+1}Y$,
with $X=W_{1}\dotsc W_{j-2}$ and $Y=W_{j+2}\dotsb W_{Q}$; see Figure 1. Let
$p$ be the prefix state of $X$ and $s$ the suffix state of $Y$.

By typicality, we know that $p$ and $s$ match, and therefore they share a
common loop alphabet ${\mathcal{L}}$. Moreover, $p$ and $s$ are dominant, and
therefore ${\mathcal{L}}^{\ast}$ has growth rate $\gamma>1$. It follows that
$|{\mathcal{L}}|\geq 2$. Let $a\in{\mathcal{L}}$ be a maximal symbol of
${\mathcal{L}}$ in the containment relation.

Write $W_{j-1}$ as a concatenation of the form $W_{j-1}^{L}aW_{j-1}^{R}$,
where $W_{j-1}^{R}$ is the longest suffix of $W_{j-1}$ that has no occurrence
of $a$. Note that such decomposition is possible, since $W_{j-1}$ contains the
symbol $a$ by typicality. In fact, $W_{j-1}^{L}$ contains at least
$\sqrt{n}-1$ disjoint occurrences of $aaaa$, and therefore has weight more
than $K$, for $n$ large enough. Symmetrically, we partition $W_{j+1}$ as
$W_{j+1}^{L}aW_{j+1}^{R}$, with $W_{j+1}^{L}$ being the longest prefix with no
occurrence of the symbol $a$. Define now $X^{+}=XW_{j-1}^{L}a$,
$Y^{+}=aW_{j+1}^{R}Y$, and $Z=W_{j-1}^{R}W_{j}W_{j+1}^{L}$, so that the word
$W$ can be written as $W=X^{+}ZY^{+}$.

We claim that if $Z^{\prime}\in{\mathcal{L}}^{\ast}$ is Wilf-equivalent to $Z$
in the class ${\mathcal{L}}^{\ast}$, then $W=X^{+}ZY^{+}$ is Wilf-equivalent
to $W^{\prime}=X^{+}Z^{\prime}Y^{+}$ in ${\mathcal{C}}$. To see this, assume
that $\Phi$ is a weight-preserving bijection mapping words in
${\mathcal{L}}^{\ast}$ containing $Z$ to those that contain $Z^{\prime}$. We
now describe a weight preserving bijection from words of ${\mathcal{C}}$
containing $W$ to those that contain $W^{\prime}$.

Let $\widehat{W}\in{\mathcal{C}}$ be a word that contains $W$. Let
$\widehat{X}$ be the shortest prefix of $\widehat{W}$ that contains $X$, and
$\widehat{Y}$ the shortest suffix of $\widehat{W}$ containing $Y$. Let $M$ be
the ‘middle’ part of $\widehat{W}$ between $\widehat{X}$ and $\widehat{Y}$,
i.e., $\widehat{W}=\widehat{X}M\widehat{Y}$. Observe that all the symbols of
$M$ belong to ${\mathcal{L}}$: if $M$ contained a symbol
$c\not\in{\mathcal{L}}$, then $\widehat{W}$ would contain $XcY$ as a subword;
however, since the prefix state of $X$ matches the suffix state of $Y$, $XcY$
is not in ${\mathcal{C}}$. This is a contradiction, as $\widehat{W}$ is in
${\mathcal{C}}$.

Let $\widehat{X}^{+}$ be the shortest prefix of $W$ containing $X^{+}$.
Clearly, $\widehat{X}$ is a prefix of $\widehat{X}^{+}$. It is possible that
in an embedding of $X^{+}$ into $\widehat{X}^{+}$, one or more initial symbols
of $W_{j-1}^{L}$ get mapped to the last symbol of $\widehat{X}$. However,
since $W_{j-1}^{L}$ has weight greater than $K$, it cannot be fully contained
in the last symbol of $\widehat{X}$, and in particular, some of its symbols
get mapped into $M$. Consequently, the final symbol of $X^{+}$ (which is the
symbol $a$) gets mapped to a symbol of $M$. Since $a$ is a maximal symbol of
${\mathcal{L}}$, and $M$ only contains symbols from ${\mathcal{L}}$, we
conclude that the final symbol of $\widehat{X}^{+}$ is also the symbol $a$.
Symmetrically, let $\widehat{Y}^{+}$ be the shortest suffix of $\widehat{W}$
containing $Y^{+}$. We again conclude that the first symbol of
$\widehat{Y}^{+}$ is the symbol $a$.

Let $\widehat{p}$ be the prefix state of $\widehat{X}^{+}$ and $\widehat{s}$
the suffix state of $\widehat{Y}^{+}$. We claim that both these states have
loop alphabet ${\mathcal{L}}$. To see this, let $U$ be a word obtained by
concatenating the maximal symbols of ${\mathcal{L}}$ in any order. By
typicality, $W_{j-1}$ has at least $\sqrt{n}$ disjoint $U$-blocks, of which at
least $\sqrt{n}-1$ are in $W_{j-1}^{L}$ (recall that $W_{j-1}^{R}$ has no
occurrence of the maximal symbol $a$). When embedding $X^{+}$ into
$\widehat{X}^{+}$, at most $K$ of these $U$-blocks can be embedded into the
last symbol of $\widehat{X}$, but for $n$ large enough, at least $Q$ of these
$U$ blocks are embedded into $\widehat{X}^{+}\setminus\widehat{X}$ (i.e., the
suffix of $\widehat{X}^{+}$ that follows after $\widehat{X}$). That means that
$\widehat{X}^{+}\setminus\widehat{X}$ contains $Q$ disjoint blocks
$U_{1},\dotsc,U_{Q}$, each containing $U$ as a subword. Since the symbols of
$U$ are maximal in ${\mathcal{L}}$, each $U_{i}$ must in fact contain the
symbols of $U$ as a subsequence. Since $\widehat{X}^{+}$ has at most $Q-1$
prefix state transitions, there is a $U_{i}$ which does not have any state
transition. Therefore $U_{i}$ is in a loop block of a prefix state
$p^{\prime}$ whose loop alphabet ${\mathcal{L}}_{p^{\prime}}$ contains all the
symbols of $U$, and therefore also all the symbols of ${\mathcal{L}}$. Since
${\mathcal{L}}$ is a dominant loop alphabet, this means that
${\mathcal{L}}_{p^{\prime}}={\mathcal{L}}$. Since all the symbols of
$\widehat{X}^{+}$ after $U_{i}$ belong to ${\mathcal{L}}$, there are no more
prefix state transitions after $U_{i}$, and $p^{\prime}=\widehat{p}$. This
shows that $\widehat{p}$ has loop alphabet ${\mathcal{L}}$, and a symmetric
argument applies to $\widehat{s}$ as well.

Let $\widehat{Z}$ be the part of $\widehat{W}$ between $\widehat{X}^{+}$ and
$\widehat{Y}^{+}$. Since $\widehat{W}$ contains $W$, we conclude that
$\widehat{Z}$ contains $Z$. Note that here we use the fact that the last
symbol of $X^{+}$ is equal to the last symbol of $\widehat{X}^{+}$ and
similarly for $Y^{+}$; this guarantees that in any embedding of $W$ into
$\widehat{W}$, no symbol from $Z$ can be mapped to the last symbol of
$\widehat{X}^{+}$ or the first symbol of $\widehat{Y}^{+}$, and in particular
$Z$ gets mapped entirely into $\widehat{Z}$. We now define
$\widehat{Z}^{\prime}=\Phi(\widehat{Z})$ and
$\widehat{W}^{\prime}=\widehat{X}^{+}\widehat{Z}^{\prime}\widehat{Y}^{+}$.
Since $\widehat{Z}^{\prime}$ contains $Z^{\prime}$, $\widehat{W}^{\prime}$
contains $W^{\prime}$. The mapping $\widehat{W}\mapsto\widehat{W}^{\prime}$ is
easily seen to be the required bijection from words containing $W$ to words
containing $W^{\prime}$ in the class ${\mathcal{C}}$.

To prove the proposition, it now suffices to show that there are many words
Wilf-equivalent to $Z$ in the class ${\mathcal{L}}^{\ast}$. This, however, can
be easily done. Recall that $a$ is a maximal symbol of ${\mathcal{L}}$, and
let $b$ be any other symbol of ${\mathcal{L}}$ (here we use that
$|{\mathcal{L}}|>1$). The word $Z$ contains the free slice $W_{j}$, which, by
typicality, contains at least $\sqrt{n}$ disjoint block occurrences of the
word $aaba$. By Corollary 3.7, replacing any such occurrence by a block
occurrence of $abaa$ preserves the Wilf class in ${\mathcal{L}}^{\ast}$, since
$a$ is maximal in ${\mathcal{L}}$ and hence the pairs $(a,b)$ and $(b,a)$ are
incompatible. This yields at least $2^{\sqrt{n}}$ words in the
${\mathcal{L}}^{\ast}$-Wilf class of $Z$, and therefore also in the
${\mathcal{C}}$-Wilf class of any typical word $W$. ∎

Let us say that a permutation ${\mathcal{C}}$ with finitely many sum-
indecomposables is an _unbounded polynomial class_ if its growth rate $\gamma$
is equal to 1 and its growth function is unbounded. For the rest of this
section, we will only consider unbounded polynomial classes. Since any such
class ${\mathcal{C}}$ has growth rate $1$, it follows that every dominant
prefix or suffix state has loop alphabet $\\{1\\}$, while every non-dominant
state has empty loop alphabet. In particular, any $W\in{\mathcal{C}}$ has
fewer than $Q$ symbols not belonging to dominant loop blocks, and all these
symbols are transition symbols. Consequently, each ${\mathcal{C}}_{n}$ has
only a bounded number of words that have at most one dominant loop block in
their prefix or suffix decomposition. Since $|{\mathcal{C}}_{n}|$ is
unbounded, it follows that $D>1$. Observe that Proposition 4.5 implies that
with probability $1-\mathcal{O}(1/n)$, a uniformly random
$W\in{\mathcal{C}}_{n}$ has $D$ dominant loop blocks in both its prefix and
its suffix decomposition.

Let us say that a loop block in the prefix or suffix decomposition of a word
$W\in{\mathcal{C}}_{n}$ is _large_ if it has length (or equivalently weight)
at least $2KQ+1$. We say that a letter in a loop block is _central_ if the
loop block contains at least $KQ$ letters preceding it and also at least $KQ$
letters following it. In particular, each large block has at least one central
letter.

######  Lemma 4.13.

Let ${\mathcal{C}}$ be an unbounded polynomial class. With probability
$1-\mathcal{O}(1/n)$, in a uniformly random $W\in{\mathcal{C}}_{n}$, all the
dominant loop blocks in the prefix and suffix decomposition are large.

###### Proof.

Recall the notation ${\mathcal{C}}_{n}(T,\tau)$ from Proposition 4.5. Let
${\mathcal{C}}_{n}(T,\tau,i,j)$ denote the set of those elements of
${\mathcal{C}}_{n}(T,\tau)$ whose $i$-th dominant prefix loop block has weight
$j$. It follows from the calculations in the proof of Proposition 4.5 that
${\mathcal{C}}_{n}(T,\tau,i,j)$ has size $O(n^{d_{T}-2})$ for any fixed $i$
and $j$, where $d_{T}$ is the number of dominant states in $T$. Summing these
contributions over all $T$, $\tau$, $i\leq D$ and $j\leq 2KQ$, we conclude
that there are at most $O(n^{D-2})$ words in ${\mathcal{C}}_{n}$ that have a
small dominant loop block. ∎

######  Lemma 4.14.

Let ${\mathcal{C}}$ be an unbounded polynomial class. Let
$W\in{\mathcal{C}}_{n}$ be a word with $k$ dominant loop blocks in its prefix
decomposition, and suppose that all these loop blocks are large. Let
$\widehat{W}\in{\mathcal{C}}$ be a word that contains $W$. Then $\widehat{W}$
has at least $k$ dominant loop blocks in its prefix decomposition. Moreover,
if $\widehat{W}$ has exactly $k$ dominant loop blocks, then in every embedding
of $W$ into $\widehat{W}$, for any dominant loop block $B_{i}$ of $W$, all the
central symbols of $B_{i}$ are mapped to loop symbols of $\widehat{W}$.
Analogous properties hold for suffix decompositions as well.

###### Proof.

Let $B_{1},\dotsc,B_{k}$ be the dominant loop blocks in the prefix
decomposition of $W$. For $i\in[k-1]$, let $t_{i}$ be the symbol of $W$
immediately following $B_{i}$. Necessarily, $t_{i}$ is different from 1. In
particular, for every embedding of $W$ into $\widehat{W}$, the symbol $t_{i}$
gets mapped to a transition symbol $\widehat{t}_{i}$ of $\widehat{W}$. For
$2\leq i\leq k-1$, let $\widehat{W}_{i}$ be the subword of $\widehat{W}$
between $\widehat{t}_{i-1}$ and $\widehat{t}_{i}$, including the two symbols
$\widehat{t}_{i-1}$ and $\widehat{t}_{i}$ themselves; we also define
$\widehat{W}_{1}$ as the prefix of $\widehat{W}$ ending in $\widehat{t}_{1}$
and $\widehat{W}_{k}$ as the suffix of $\widehat{W}$ starting in
$\widehat{t}_{k-1}$. Since $B_{i}$ is mapped into $\widehat{W}_{i}$ and
$B_{i}$ is large, $\widehat{W}_{i}$ has at least $2Q+1$ symbols, and therefore
each $\widehat{W}_{i}$ has a loop symbol. Since each $\widehat{W}_{i}$ begins
or ends with a transition symbol, $\widehat{W}$ has at least $k$ nonempty loop
blocks, which are necessarily dominant.

Suppose now that $\widehat{W}$ has exactly $k$ dominant loop blocks. It
follows that each $\widehat{W}_{i}$ contains a unique dominant loop block
$\widehat{B}_{i}$ of $\widehat{W}$. Therefore, all the symbols of
$\widehat{W}_{i}$ except perhaps the leftmost $Q$ and the rightmost $Q$ belong
to the loop block $\widehat{B}_{i}$. Since the block $B_{i}$ is mapped into
$\widehat{W}_{i}$, all its central symbols must get mapped into
$\widehat{B}_{i}$. ∎

######  Proposition 4.15.

Any unbounded polynomial class ${\mathcal{C}}$ exhibits a Wilf collapse.

###### Proof.

Choose a uniformly random word $W\in{\mathcal{C}}_{n}$. With probability at
least $1-\mathcal{O}(1/n)$, the word is typical, has $D$ dominant loop blocks
in both the prefix and the suffix decomposition, and each of these loop blocks
is large. By typicality, we know that $W$ has a sequence of three slices
$W_{j-1}W_{j}W_{j+1}$ that are all contained in a single prefix loop block
$B$. We may assume, without loss of generality, that $B$ is not the rightmost
dominant prefix loop block of $W$: if $B$ were the rightmost dominant loop
block, we would consider suffix decompositions instead of prefix ones, and
apply the following argument symmetrically.

Figure 2: Illustration of the proof of Proposition 4.15

Let $X$ be the prefix of $W$ that contains all the symbols preceding $B$ and
the first $2KQ+1$ symbols of $B$. See Figure 2. Let $Y$ be the suffix of $W$
containing the rightmost $2KQ+1$ symbols of $B$ and all the symbols to the
right of $B$. Let $C$ be the sequence of symbols of $B$ that are neither in
$X$ nor in $Y$. Note that for $n$ large enough, the slice $W_{j}$ is entirely
contained in $C$, and in particular $C$ is nonempty and we may write $W=XCY$.

Let $d_{X}$ be the number of dominant loop blocks in the prefix decomposition
of $X$, and let $d_{Y}$ be the number of dominant loop blocks in the suffix
decomposition of $Y$. By typicality, we have $d_{X}+d_{Y}=D+1$. Since $B$ is
not the rightmost dominant prefix loop block, we get $d_{X}\leq D-1$, and
hence $d_{Y}\geq 2$. Let $B^{\prime}$ be the leftmost dominant suffix loop
block of $Y$ which is disjoint from $B$. Let $C^{\prime}$ be the subword of
$B^{\prime}$ consisting of its central elements. We may then write $Y$ as
$Y=UC^{\prime}V$, with $U$ and $V$ being the symbols of $Y$ before and after
$C^{\prime}$, respectively.

Let $m$ be the length of $C$ and $m^{\prime}$ the length of $C^{\prime}$. Note
that $m\geq\operatorname{wt}(W_{j})=\Theta(n)$ and $m^{\prime}\geq 1$. Let us
now fix a value $k\in[m]$, and let $W^{\prime}$ be the word obtained from $W$
by removing $k$ symbols from the block $B$ and inserting these $k$ symbols
into $B^{\prime}$ (necessarily all these $k$ symbols are copies of the symbol
‘$1$’). We will now show that $W$ is Wilf-equivalent to $W^{\prime}$ in the
class ${\mathcal{C}}$, implying that $W$ belongs to a Wilf class of size
$\Omega(n)$.

Let $\widehat{W}\in{\mathcal{C}}$ be a word containing $W$. Let $\widehat{X}$
be the shortest prefix of $\widehat{W}$ containing $X$, let $\widehat{Y}$ be
the shortest suffix of $\widehat{W}$ containing $Y$, and let $\widehat{C}$ be
the symbols of $\widehat{W}$ between $\widehat{X}$ and $\widehat{Y}$. Noting
that all the dominant prefix loop blocks of $X$ and all the dominant suffix
loop blocks of $Y$ are large, we may apply Lemma 4.14 to conclude that
$\widehat{X}$ has at least $d_{X}$ dominant prefix loop blocks, and
$\widehat{Y}$ has at least $d_{Y}$ dominant suffix loop blocks. In fact, since
$\widehat{X}\widehat{Y}$ is in ${\mathcal{C}}$ and $d_{X}+d_{Y}=D+1$, we
conclude by Lemma 4.7 that $\widehat{X}$ has exactly $d_{X}$ dominant prefix
loop blocks and $\widehat{Y}$ exactly $d_{Y}$ dominant suffix loop blocks. By
the second part of Lemma 4.14, in any embedding of $Y$ into $\widehat{Y}$, all
the central symbols of the dominant loop blocks, and in particular all the
symbols of $C^{\prime}$, get mapped to loop symbols. Moreover, all the symbols
of $\widehat{C}$ are loop symbols in the prefix decomposition of
$\widehat{W}$, since if $\widehat{C}$ contained a transition symbol, then
$\widehat{W}$ would have more dominant prefix loop blocks than $W$, which is
impossible.

It follows that $\widehat{W}$ can be written as
$\widehat{W}=\widehat{X}\widehat{C}\widehat{Y}$, where $\widehat{C}$ is a
sequence of length at least $m$ in which all symbols are equal to $1$.
Moreover, $\widehat{Y}$ can be further written as
$\widehat{Y}=\widehat{U}\widehat{C}^{\prime}\widehat{V}$, where $\widehat{V}$
is the shortest suffix of $\widehat{Y}$ that contains $V$,
$\widehat{C}^{\prime}$ is a sequence of length $m^{\prime}$ whose all symbols
are equal to $1$, and $\widehat{U}$ contains $U$. We may now transform
$\widehat{W}$ into a word $\widehat{W}^{\prime}$ by moving $k$ symbols from
$\widehat{C}$ to $\widehat{C}^{\prime}$. Then $\widehat{W}^{\prime}$ belongs
to ${\mathcal{C}}$, since it only differs from $\widehat{W}$ by the length of
its loop blocks, $\widehat{W}^{\prime}$ clearly contains $W^{\prime}$, and we
easily see that the map $\widehat{W}\mapsto\widehat{W}^{\prime}$ is a weight-
preserving bijection between the words of ${\mathcal{C}}$ containing $W$ and
those containing $W^{\prime}$.

This shows that $W$ and $W^{\prime}$ are indeed equivalent in ${\mathcal{C}}$,
and the Wilf class of $W$ has size at least $m=\Theta(n)$. It follows that
${\mathcal{C}}$ exhibits a Wilf collapse. ∎

Propositions 4.12 and 4.15 together establish Theorem 4.3.

##  5 Concluding remarks

We have demonstrated that Wilf collapse occurs in a wide variety of
permutation classes. As mentioned in the introduction, the only ingredients we
seem to need to trigger such a collapse are a form of greedy embedding for
detecting permutation involvement, together with a representation in terms of
words that combines with the greedy embedding to allow for local symmetries
that guarantee Wilf equivalence.

A notable example where our methods of establishing Wilf collapse fail is
$\operatorname{Av}(321)$ – the class of permutations containing no occurrence
of a 321 pattern. In [Guillemot] (see also [AlbertLackner]) a greedy approach
to detecting involvement is described in this class but the complexity of the
ways in which sum-indecomposable permutations can be combined here (along
perhaps with the failure of super-criticality) have stymied our attempts to
prove a Wilf collapse in $\operatorname{Av}(321)$. Furthermore, empirical
evidence for this class suggests that if a collapse does occur it is far less
“robust” than we see in our other examples – the largest observed Wilf classes
are those containing the permutations of the form $(d+1)(d+2)\cdots
n\,12\cdots d$ (and some others) previously considered in [MansourV, Mansour].

A related permutation class, the class of “skew-merged” permutations
(permutations that can be written as the merge of a decreasing and an
increasing subsequence) has none of the nice closure properties that we might
hope for, but again the existence of a greedy algorithm for pattern detection
and an underlying structure of “spirals” might yield a Wilf collapse.

######  Question 5.1.

Does $\operatorname{Av}(321)$ have a Wilf collapse? Does the class of skew-
merged permutations?

## References