# Consecutive Pattern Containment and c-Wilf Equivalence

Reza Rastegar Center of Excellence for Data Science and Modeling, Occidental
Petroleum Corporation, Houston, TX 77046 e-mail<EMAIL_ADDRESS>
###### Abstract

We offer elementary proofs for several results in consecutive pattern
containment that were previously demonstrated using ideas from cluster method
and analytical combinatorics. Furthermore, we establish new general bounds on
the growth rates of consecutive pattern avoidance in permutations.

MSC2010:  Primary 05A05, 05A16, 05A15.
Keywords: consecutive pattern containment, c-Wilf-equivalence, asymptotic
growth rate, words, permutations, probabilistic method

##  1 Introduction

Consecutive pattern containment is a variation of the standard definition of
pattern containment in permutations. In this containment, the entries of a
pattern are required to appear in adjacent positions. This problem is
significant in combinatorics, as it naturally arises in descents, peaks, and
alternating permutations. The first systematic analysis of consecutive pattern
containment is credited to Elizalde and Noy [10], who defined it formally and
established several fundamental results. For more information on the broader
subject of pattern containment, we refer the reader to [1] and [13].
Additionally, for a more focused review of consecutive pattern containment,
see [9]. In this paper, we revisit consecutive pattern containment in both
permutations and words, and we present several new and previously known facts.
Our proofs are based on elementary probabilistic arguments.

We begin by establishing some definitions. Let ${\mathbb{N}}$ denote the set
of natural numbers $\\{1,2,3,\ldots\\}$, and let ${\mathbb{N}}_{0}$ denote the
set of non-negative integers, i.e.,
${\mathbb{N}}_{0}={\mathbb{N}}\cup\\{0\\}$. Given a set ${\mathcal{A}}$,
$\\#{\mathcal{A}}$ refers to the cardinality of ${\mathcal{A}}$. The notation
$\widetilde{\mathcal{A}}$ is used to denote the complement of ${\mathcal{A}}$
with respect to the universe set. For a given $k\in{\mathbb{N}}$, we denote
the set $\\{1,2,\cdots,k\\}$ by $[k]$, and the set of all $d$-subsets by
$[k]_{d}$. Denote by ${\mathcal{S}}_{n}$ the set of all permutations of the
set $[n]$. A word $w$ is a sequence $w:=w_{1}\cdots w_{n}$, where $w_{i}$
represents the $i$-th entry of $w$, selected from an arbitrary set of letters
referred to as the alphabet. Throughout this paper, we use
$[\operatorname{\mathtt{K}}]$ as the generic alphabet set, where
$\operatorname{\mathtt{K}}\in{\mathbb{N}}$ is its size. We adopt the
convention that $[\operatorname{\mathtt{K}}]^{0}=\\{\epsilon\\},$ where
$\epsilon$ is an empty word. A _$\operatorname{\mathtt{K}}$ -ary word_ of
length $n$ is an element of $[\operatorname{\mathtt{K}}]^{n},$
$n\in{\mathbb{N}}.$ A _pattern_ with $d$ distinct letters is any word chosen
from the alphabet set $[d]$.

Let us define an occurrence of the pattern $v$ in an arbitrary word $w$ of
length $n\geq d$. Such an occurrence is represented by a sequence of $d$
indices $1\leq j_{1}<j_{2}<\cdots<j_{d}\leq n$ such that the subsequence
$w_{j_{1}}\cdots w_{j_{d}}$ is order-isomorphic to the pattern $v$. In other
words,

$\displaystyle w_{j_{p}}<w_{j_{q}}\iff v_{p}<v_{q}\quad\text{and}\quad
w_{j_{p}}=w_{j_{q}}\iff v_{p}=v_{q},\quad\forall\ 1\leq p,q\leq d.$

Here, we say $w_{j_{1}}\cdots w_{j_{d}}$ reduces to $v$ and write
$\operatorname{\mbox{red}}(w_{j_{1}}\cdots w_{j_{d}})=v$. If $j_{p+1}=j_{p}+1$
for all $p\in[d-1]$, then we call the subsequence $w_{j_{1}}\cdots w_{j_{d}}$
a _consecutive_ occurrence of the pattern $v$. For any arbitrary word $w$ we
denote by $\operatorname{\mbox{con}}_{v}(w)$ the number of consecutive
occurrences of $v$. For instance, if $v$ is the _inversion_ $21$ and
$w=35239$, then there are three occurrences and one consecutive occurrence,
those are $w_{1}w_{3}=32,$ $w_{2}w_{3}=52,$ and $w_{2}w_{4}=53$, and
consequently $\operatorname{\mbox{con}}_{v}(w)=1$. We say that a word $w$
_contains the pattern $v$ consecutively_ exactly $r$ times,
$r\in{\mathbb{N}}_{0},$ if $\operatorname{\mbox{con}}_{v}(w)=r$. For a set of
words ${\mathcal{A}}$ and $r\in{\mathbb{N}}_{0},$ we denote by
${\mathcal{G}}_{r}^{v}({\mathcal{A}})$ the set of words in ${\mathcal{A}}$
containing $v$ consecutively exactly $r$ times. That is,

$\displaystyle{\mathcal{G}}_{r}^{v}({\mathcal{A}})=\\{w\in{\mathcal{A}}:\operatorname{\mbox{con}}_{v}(w)=r\\}.$
(1)

We use $g_{r}^{v}({\mathcal{A}})$ to refer to
$\\#{\mathcal{G}}_{r}^{v}({\mathcal{A}})$. In the case of $r=0,$ we use the
term avoidance instead of occurrence.

An important area of study in pattern containment is to determine when two
patterns are avoided by the same number of permutations or words of the same
length, or more generally when the distribution of occurrences of the two
patterns is the same. We say that two patterns $v$ and $w$ are _c-Wilf-
equivalent in words_ if
$g_{0}^{v}([\operatorname{\mathtt{K}}]^{n})=g_{0}^{w}([\operatorname{\mathtt{K}}]^{n})$
for all $\operatorname{\mathtt{K}},n\in{\mathbb{N}}$. Moreover, they are
_strongly c-Wilf-equivalent_ if
$g_{r}^{v}([\operatorname{\mathtt{K}}]^{n})=g_{r}^{w}([\operatorname{\mathtt{K}}]^{n})$
for all $\operatorname{\mathtt{K}},n\in{\mathbb{N}}$ and
$r\in{\mathbb{N}}_{0}$. Similarly, $v$ and $w$ are _c-Wilf-equivalent in
permutations_ if $g_{0}^{v}({\mathcal{S}}_{n})=g_{0}^{w}({\mathcal{S}}_{n})$
for all $n\in{\mathbb{N}}$, and are _strongly c-Wilf-equivalent_ if
$g_{r}^{v}({\mathcal{S}}_{n})=g_{r}^{w}({\mathcal{S}}_{n})$ for all
$n\in{\mathbb{N}}$ and $r\in{\mathbb{N}}_{0}$. For example, every permutation
pattern $v$ is strongly c-Wilf-equivalent to its reversal both in words and
permutations. An important open problem in consecutive patterns (whose
analogue in the classical pattern avoidance is wide open as well) is

######  Problem 1.1.

Classify all patterns into (strongly) c-Wilf equivalence classes in
permutations (in words).

In contrast to classical patterns, Nakamuta conjectured that the word
“strongly” in the above definition is unnecessary in the context of
permutations (see [20], Conjecture 5.6). Specifically, he proposed that

######  Conjecture 1.2 (Nakamuta’s conjecture).

If two patterns are c-Wilf-equivalent in permutations, then they are also
strongly c-Wilf-equivalent in permutations.

Although these problems remains unsolved, partial progress has been made
towards potential solutions. To describe the progress and state the results,
we first define an essential notion of overlapping concerning the structure of
a pattern. We denote by ${\mathcal{O}}_{v}$ the set of overlaps of $v$, which
we define as the set of indices $i$ with $1\leq i<d$ such that the first and
the last $i$ positions have the same relative order; that is,
$\operatorname{\mbox{red}}(v_{1},\cdots,v_{i})=\operatorname{\mbox{red}}(v_{d-i+1},\cdots,v_{d})$.
Note that $1\in{\mathcal{O}}_{v}$ for every pattern $v\in{\mathcal{S}}_{d}$.
If $d\geq 3$, a pattern $v\in{\mathcal{S}}_{d}$ for which
${\mathcal{O}}_{v}=\\{1\\}$ is said to be non-overlapping, also known as
minimally overlapping. Equivalently, $v$ is non-overlapping if two occurrences
of $v$ in a permutation cannot overlap in more than one position. Duane and
Remmel [4] and Bóna [2] studied non-overlapping patterns, and Bóna proved that
the proportion of non-overlapping patterns of any length $d$ is at least
$0.364$. Additionally, it is straightforward to show that for $d\geq 3,$ the
pattern $v$ is monotone, that is $v\in\\{1\cdots d,d\cdots 1\\}$, if and only
if ${\mathcal{O}}_{v}=[d]$, if and only if $d-1\in{\mathcal{O}}_{v}$; see, for
instance, Lemma 9, [21]. Hence, we can safely consider that the maximum
overlap of a non-monotone pattern $v$ is at most $d-2$.

A sufficient condition for strong c-Wilf-equivalence in permutations for two
paterns of the same overlap set was given independently by Khoroshkin and
Shapiro [14], and Nakamura [20]. They showed for any two patterns
$v,w\in{\mathcal{S}}_{d}$,

If ${\mathcal{O}}_{v}={\mathcal{O}}_{w}$ and if for all
$i\in{\mathcal{O}}_{v},$ we have
$\displaystyle\qquad\qquad\\{v_{1},\cdots,v_{d-i}\\}=\\{w_{1},\cdots,w_{d-i}\\}\quad\mbox{and}\quad\\{v_{i+1},\cdots,v_{d}\\}=\\{w_{i+1},\cdots,w_{d}\\},$
(2)

then $v$ and $w$ are strongly c-Wilf-equivalent in permutations. The
techniques used to prove this result were based on the Goulden-Jackson cluster
method (see [20]) and a homological duality argument applied to specific
clusters (see [14]). Our first result below provides a similar result that
applies to words. Our proof is based on classical findings related to the
observation of a predetermined sequence within an i.i.d. sequence of discrete
experiments. It is more elementary than previous proofs and leads to a
stronger conclusion, which can be extended to permutations using Corollary
3.3. In fact, our approach can establish a form of equivalence known as super-
strong Wilf-equivalence, as defined in [5].

######  Theorem 1.3.

Let $v$ and $w$ be two patterns in ${\mathcal{S}}_{d}.$ Then, $v$ and $w$ are
(strongly) c-Wilf-equivalent in words if (1) holds.

In the case of non-overlapping patterns $v$ and $w$, the condition (1) simply
states that if $v_{1}=w_{1}$ and $v_{d}=w_{d}$, then $v$ and $w$ are strongly
c-Wilf-equivalent in permutations. This fact has been previously shown in [3,
8, 4]. A converse of this statement for non-overlapping patterns was
conjectured by Elizalde in [8] and proved by Lee and Sah [15]. To formally
state the result, we define a pattern $v\in{\mathcal{S}}_{d}$ to be in
standard form if $v_{1}<v_{d}$ and $v_{1}+v_{d}\leq d+1$. It is worth noting
that for any $v\in{\mathcal{S}}_{d}$, at least one permutation among $v$, its
reverse, complement, and reversed-complement is in standard form. The result
of Lee and Sah states that for any two standard form non-overlapping patterns
$v,w\in{\mathcal{S}}_{d}$, if $v$ and $w$ are c-Wild-equivalent in
permutations, then $v_{1}=w_{1}$ and $v_{d}=w_{d}$.

The condition $v_{1}=w_{1}$ and $v_{d}=w_{d}$ is clearly sufficient for non-
overlapping patterns $v,w\in{\mathcal{S}}_{d}$ to be strongly c-Wilf-
equivalent. Therefore, the result of Lee and Sah completely characterizes
(strong) c-Wilf-equivalence classes in permutations for non-overlapping
patterns. See Proposition 1.5 below. Although this result is only applicable
to non-overlapping patterns, Dwyer and Elizalde formulated another statement
without this restriction and showed that it is equivalent to the theorem of
Lee and Sah. More details on this can be found in [5]. Their more general
statement is that for any patterns $v,w\in{\mathcal{S}}_{d}$ in standard form,
if $v$ and $w$ are c-Wilf-equivalent, then $v_{1}=w_{1}$ and $v_{d}=w_{d}$. We
remark that the inverse of this statement does not hold as one can find
counterexamples. More specifically there are known examples of patterns $v$
and $w$ satisfying $v_{1}=w_{1}$ and $v_{d}=w_{d}$ that are not c-Wilf-
equivalent in permutations. See [5] for more information and several examples.

Below, we present several straightforward observations that we think could
help in analyzing consecutive pattern containment for non-overlapping
patterns. To explain these findings, we define

$\displaystyle
a^{(r+1)}_{n}(v):=\frac{g^{v}_{r}({\mathcal{S}}_{n+d-1})}{(n+d-1)!}\quad\mbox{and}\quad
h^{(r+1)}_{\operatorname{\mathtt{K}},n}(v):=\frac{g^{v}_{r}([\operatorname{\mathtt{K}}]^{n+d-1})}{\operatorname{\mathtt{K}}^{n+d-1}}.$
(3)

The first observation establishes a linear recursive equation for
$a^{(r)}_{n}(v)$ and $h^{(r)}_{\operatorname{\mathtt{K}},n}(v)$. The arguments
are based on repetitive exclusion-inclusion of probability events.

######  Theorem 1.4.

  * (a)

Let $v\in{\mathcal{S}}_{d}$ be a non-overlapping pattern. For a given $n\geq
d,$ set $m:=\lfloor\frac{n-1}{d-1}\rfloor$. Then

$\displaystyle
a_{n}^{(1)}(v)-a_{n-1}^{(1)}(v)-\frac{1}{d!}a^{(1)}_{n-d}(v)-\sum_{j=1}^{m}(-1)^{j}\operatorname{\mathtt{A}}_{j}(v)a^{(1)}_{n-jd+j-d}(v)=0,$
(4)

where $\operatorname{\mathtt{A}}_{j}(v)$s are constants defined by (12).

  * (b)

Fix $\operatorname{\mathtt{K}}\in{\mathbb{N}}$. Let $v\in{\mathcal{S}}_{d}$ be
any non-overlapping permutation pattern with $v_{1}<v_{d}$. Then, there is
$n_{0}\in{\mathbb{N}}$ such that for any $n\geq n_{0}$

$\displaystyle
h_{\operatorname{\mathtt{K}},n}^{(1)}(v)-h_{\operatorname{\mathtt{K}},n-1}^{(1)}(v)-\frac{1}{\operatorname{\mathtt{K}}^{d}}h^{(1)}_{\operatorname{\mathtt{K}},n-d}(v)-\sum_{j=1}^{\operatorname{\mathtt{K}}}(-1)^{j}\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},j}(v)h^{(1)}_{\operatorname{\mathtt{K}},n-jd+j-d}(v)=0,$
(5)

where $\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},j}(v)$ is defined
by (25).

The proof of the first part is given in Section 2.1. As for the second part,
the proof is very similar to the proof of the first part and we sketch it in
the beginning of Section 3.

As a consequence of this result, we present the following proposition that had
been previously established for permutations by Elizalde and Noy [11],
utilizing alternative techniques such as cluster method and analytical
combinatorics. In contrast, our proof relies on elementary probability
arguments and is presented for permutations in Section 2.1.

######  Proposition 1.5.

Suppose $w,v\in{\mathcal{S}}_{d}$ are two non-overlapping patterns that are
c-Wilf-equivalent in permutations (resp. words). Then, they are also strongly
c-Wilf-equivalent in permutations (resp. words).

It is noteworthy that the proof for words is identical and is omitted.

Next, following the approach of Theorem 1.4, we express a recursive equation
for monotone patterns. This can be formulated as follows:

######  Theorem 1.6.

Let $v\in{\mathcal{S}}_{d}$ be a monotone pattern, that is $v=1\cdots d$ or
$v=d\cdots 1$. For $k\geq 2$ and $n\geq k(d-1),$ set
$m:=\lfloor\frac{n-1}{d}\rfloor$. Then,

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)+\sum_{k=1}^{m}(-1)^{k}M_{k}a_{n-kd-1}^{(1)}(v)+\widetilde{M}_{m}=0,$

where $M_{k}$ and $\widetilde{M}_{m}$ are defined by (14), (15), and (16).

Obtaining equations similar to those demonstrated by Theorem 1.4 and Theorem
1.6 is often challenging, if not impossible, in most cases. However, we can
derive the following inequality applicable to any permutation pattern.

######  Theorem 1.7.

Let $v$ be any pattern in $S_{d}$. Fix $\ell\geq 2$. Then, for $n>\ell+2d$ we
have

$\displaystyle 0\leq
a_{n}^{(1)}(v)-a_{n-1}^{(1)}(v)+\beta_{\ell-1}(v)a_{n-\ell-d+1}^{(1)}(v)\leq\frac{d-1}{d!}a_{n-\ell-2d+2}^{(1)}(v),$

where

$\displaystyle\beta_{\ell-1}(v):=a_{\ell-1}^{(1)}(v)-a_{\ell}^{(1)}(v)=\frac{g^{v}_{0}({\mathcal{S}}_{\ell+d-2})}{(\ell+d-2)!}-\frac{g^{v}_{0}({\mathcal{S}}_{\ell+d-1})}{(\ell+d-1)!}.$
(6)

A proof of this inequality is presented in the Section 2.2. It is worth noting
that this inequality can be modified to hold for words. More specifically,
suppose $\ell\geq 2$ and $v\in{\mathcal{S}}_{d}$. Then, for $n>\ell+2d$ we
have

$\displaystyle 0\leq
h_{\operatorname{\mathtt{K}},n}^{(1)}(v)-h_{\operatorname{\mathtt{K}},n-1}^{(1)}(v)+\beta_{\ell-1}(v)h_{\operatorname{\mathtt{K}},n-\ell-d+1}^{(1)}(v)\leq\frac{d-1}{\operatorname{\mathtt{K}}^{d}}h_{\operatorname{\mathtt{K}},n-\ell-2d+2}^{(1)}(v),$

where

$\displaystyle\beta_{\ell-1}(v):=h_{\operatorname{\mathtt{K}},\ell-1}^{(1)}(v)-h_{\operatorname{\mathtt{K}},\ell}^{(1)}(v)=\frac{g^{v}_{0}([\operatorname{\mathtt{K}}]^{\ell+d-2})}{\operatorname{\mathtt{K}}^{\ell+d-2}}-\frac{g^{v}_{0}([\operatorname{\mathtt{K}}]^{\ell+d-1})}{\operatorname{\mathtt{K}}^{\ell+d-1}}.$

The proof is nearly identical to that of Theorem 1.7 and is therefore omitted.

Having obtained the inequality of Theorem 1.7, our attention now turns to the
growth rate of consecutive pattern avoidance in permutations.

Ehrenborg et al. [6] previously studied the growth rate of
$g_{0}^{v}({\mathcal{S}}_{n})$, proving Warlimont’s conjecture [25] on the
asymptotic behavior of the number of permutations that avoid consecutive
patterns using the spectral theory of integral operators on
$L_{2}([0,1]^{d-1})$. Specifically, they demonstrated that the asymptotic
value of $g_{0}^{v}(\mathcal{S}_{n})$ is given by
$g_{0}^{v}(\mathcal{S}_{n})=\left(b_{v}\rho_{v}^{n}+O(r_{v}^{n})\right)n!$,
where $b_{v}$, $\rho_{v}$, and $r_{v}$ are positive constants that depend
solely on $v$, with $\rho_{v}>r_{v}$. While it is not the main focus of our
investigation, it would be worthwhile to obtain a similar asymptotic statement
for $g_{r}^{v}({\mathcal{S}}_{n})$ for any other fixed value of
$r\in{\mathbb{N}}$, and to determine whether any of the constants involved in
the $r=0$ case are present in the asymptotic form of the general case for $r$.
Notably, if $r\geq n-d+2$ and all elements of ${\mathcal{A}}$ have lengths of
at most $n$, then $g_{r}^{v}({\mathcal{A}})=0$, as any word in ${\mathcal{A}}$
has at most $n-d+1$ consecutive subwords of length $d$ that could potentially
be order-isomorphic to $v$. Furthermore, for the case of
${\mathcal{A}}={\mathcal{S}}_{n}$, we have the following lemma that, to the
best of our knowledge, is new in the context of consecutive pattern
containment:

######  Lemma 1.8.

For any $v\in{\mathcal{S}}_{d}$, and any fixed $r\in{\mathbb{N}}_{0}$, the
limit
$\lim_{n}\left(\frac{g_{r}^{v}({\mathcal{S}}_{n})}{n!}\right)^{\frac{1}{n}}$
exists and is equal to $\rho_{v}$.

The proof is similar to that of Theorem B, [18] and hence it is omitted. A
similar result can be shown for the words by conducting a modified version of
Theorem 1.1-(a), [17].

In our next result, we provide further insights into the growth rate parameter
$\rho_{v}$ in permutations. One major result in consecutive pattern
containment posits that, among all patterns of fixed length $d$, the
increasing pattern $12\cdots d$ (and the decreasing pattern $d\cdots 1$) is
the one for which the number of permutations avoiding it is asymptotically the
most significant. In particular, Elizalde (see [8]) proved that, for any
pattern $v\in\mathcal{S}_{d}$,

$\displaystyle\rho_{1\cdots(d-2)d(d-1)}\leq\rho_{v}\leq\rho_{12\cdots(d-1)d},$

and for non-overlapping pattern $v\in\mathcal{S}_{d}$,

$\displaystyle\rho_{1\cdots(d-2)d(d-1)}\leq\rho_{v}\leq\rho_{134\cdots d2}.$

Furthermore, the study by Perarnau [21] employed various probabilistic
techniques to establish that for any $d\in{\mathbb{N}}$ and non-monotone
pattern $v\in\mathcal{S}_{d}$, the asymptotic growth rate of the number of
permutations in $\mathcal{S}_{n}$ avoiding the consecutive pattern $v$ is
bounded above by $1-\frac{1}{d!}+O(\frac{1}{d^{2}d!})$, while for any
$v\in\mathcal{S}_{d}$, it is bounded below by
$1-\frac{1}{d!}-O(\frac{d-1}{d!^{2}})$. Our result augments theirs.

######  Theorem 1.9.

Let $v$ be any pattern in $S_{d}$.

  * (a)

Then, for any $\alpha\geq 2$, and $\lambda:=1+d(\alpha-1),$

$\displaystyle\left|a_{\alpha
kd}^{(1)}(v)-\left(a_{\lambda}^{(1)}(v)\right)^{k}\right|\leq(k+2)\left(a_{\lambda}^{(1)}(v)\right)^{k-1},\qquad\forall
k\in{\mathbb{N}}.$ (7)

In particular, this implies

$\displaystyle\rho_{v}\leq\left(\frac{g^{v}_{0}({\mathcal{S}}_{\alpha
d})}{(\alpha d)!}\right)^{\frac{1}{\alpha d}}.$ (8)

  * (b)

For any $\ell\in{\mathbb{N}}$, larger than $1$,

$\displaystyle\rho_{v,l}\leq\rho_{v}\leq\rho_{v,u},$

where $\rho_{v,l}$ and $\rho_{v,u}$ are the dominant roots of the equations

$\displaystyle\rho^{\ell+d-1}-\rho^{\ell+d-2}+\beta_{\ell-1}(v)=0$ (9)

and

$\displaystyle\rho^{\ell+2d-2}-\rho^{\ell+2d-3}+\beta_{\ell-1}(v)\rho^{d-1}-\frac{d-1}{d!}=0,$
(10)

where $\beta_{\ell-1}(v)$ is defined by (6). In particular, choosing $\ell$
such that $\beta_{\ell-1}(v)\neq\frac{(m-1)^{m-1}}{m^{m}}$ with $m:=d+\ell-1$,
there exists $\gamma\in(1,\infty)$ such that

$\displaystyle
1-\beta_{\ell-1}(v)-\left(\beta_{\ell-1}(v)\right)^{\gamma}\leq\rho_{v}.$

One immediate consequence of part (b) is that
$\lim_{d}\min_{v\in{\mathcal{S}}_{d}}\rho_{v}=1$ as one would expect. This is
evident since the dominant roots of the equations (9) and (10) converge to $1$
as $d$ grows to infinity.

We would like to highlight the distinction between Perarnau’s approach and
ours. While Perarnau’s bounds remain same across all non-monotone patterns,
our methodology introduces a novel flexibility. By allowing the parameter
$\alpha$ and $\ell$ to vary, we offer a spectrum of upper bounds tailored to
specific patterns. This dynamic nature of our bounds empowers the reader to
adapt her analyses according to the intricacies of each pattern under
consideration. Furthermore, our approach enables a direct enumeration of (6)
or the right-hand side of equation (8), facilitating a more streamlined
process for deriving bounds.

Finally, we note that, for the sake of simplifying the presentation and proof
of our results, we restricted our consideration to permutation patterns
consistently within ${\mathcal{S}}_{d}$. We maintain that this restriction is
purely technical, and that all findings pertaining to words, notably Theorems
1.3, 1.4-(b), and 1.5, remain applicable to any $d$-ary pattern within the
framework of pattern containment in words.

##  2 Consecutive containment in permutations

In order to prove our results, we found it easier to reformulate the problem
of consecutive pattern containment within a probabilistic framework. However,
it is also possible to present combinatorial proofs of many of these results
without relying on the language of probability. Let $(Y_{n})$ be a sequence of
independently and identically distributed random variables
$(Y_{n})_{n\in{\mathbb{N}}}$, uniformly sampled from $[0,1]$. We will denote
by ${\mathbb{P}}$ the probability law in a suitable probability space that
supports all random variables considered in this section. Consider a discrete-
time Markov process $(X_{n})_{n\in{\mathbb{N}}}$ on the space $[0,1]^{d}$,
where $X_{n}:=Y_{n}\cdots Y_{n+d-1}$. The transition probability of $X_{n}$ is
defined as

$\displaystyle P(x,{\mathcal{A}})={\mathbb{L}}(\\{y\
|(x_{2},\cdots,x_{d},y)\in{\mathcal{A}}\\}),\quad x:=x_{1}\cdots
x_{d}\in[0,1]^{d},\quad{\mathcal{A}}\subset[0,1]^{d},$

where ${\mathbb{L}}$ represents the Lebesgue measure on $[0,1]$. It is well-
known that $\operatorname{\mbox{red}}(Y_{1}\cdots Y_{n})$ follows the same
distribution as a uniformly randomly sampled permutation from
${\mathcal{S}}_{n}$. This implies that

$\displaystyle
a_{n}^{(r)}(v)=\frac{g_{r-1}^{v}({\mathcal{S}}_{n+d-1})}{(n+d-1)!}={\mathbb{P}}(\operatorname{\mbox{con}}_{v}(\operatorname{\mbox{red}}(Y_{1}\cdots
Y_{n+d-1}))=r-1).$

In the rest of this section, we will use ${\mathcal{B}}_{i}(v)$ to denote the
event $\\{\operatorname{\mbox{red}}(X_{i})\neq v\\}$ and use
$\widetilde{\mathcal{B}}_{i}(v)$ to refer to its complement. We define
${\mathcal{B}}_{i}^{j}(v)$ as $\cap_{s=i}^{j}{\mathcal{B}}_{s}(v)$ for $i\leq
j$. When $i>j$, we define ${\mathcal{B}}_{i}^{j}(v)$ as the universe set with
probability measure of one. We will drop $v$ whenever the context is clear.
The following facts will be used frequently without explicit mention: For
$i\in{\mathbb{N}}$,

$\displaystyle{\mathbb{P}}(\widetilde{\mathcal{B}}_{i})=\frac{1}{d!}\quad\text{and}\quad{\mathbb{P}}({\mathcal{B}}_{i})=1-\frac{1}{d!},$

and for $i\geq 2$,

$\displaystyle{\mathbb{P}}({\mathcal{B}}_{1}^{i-1},\widetilde{\mathcal{B}}_{i})={\mathbb{P}}({\mathcal{B}}_{1}^{i-1})-{\mathbb{P}}({\mathcal{B}}_{1}^{i}).$

We commence by presenting the following observation, which although not
employed directly in our proofs, serves as a straightforward proof of the
existence of the growth rate $\rho_{v}$ and the inequality $\rho_{v}<1$. This
outcome was originally demonstrated in [7] (see Theorem 4.1 herein). It is
noteworthy to mention that Ehrenborg et al. [6] established a more refined
outcome, as mentioned in the introduction.

Let ${\mathfrak{S}}_{r}^{v}(x)$ be the exponential generating function of
$g_{r}^{v}({\mathcal{S}}_{n})$; that is,

$\displaystyle{\mathfrak{S}}_{r}^{v}(x)=\sum_{n=d}^{\infty}g_{r}^{v}({\mathcal{S}}_{n})\frac{x^{n}}{n!},\quad
r\in{\mathbb{N}}_{0}.$

######  Lemma 2.1.

Let $v\in{\mathcal{S}}_{d}$ be a given pattern. Then, there exists a constant
$\kappa_{v}>1$ such that ${\mathfrak{S}}_{0}^{v}(\kappa_{v})<\infty$. In
particular, this implies that $\rho_{v}=\lim_{n}(a_{n}^{(1)}(v))^{1/n}$ exists
and is at most $\frac{1}{\kappa_{v}}<1$.

###### Proof.

Our initial task is to verify Doeblin’s condition for $X_{n}$ (refer to [19]
for a detailed discussion). To do so, let $P^{k}(.,.)$ denote the $k$-th step
transition probability of the Markov chain $(X_{n})$. For every $a\in(0,1)$,
for any $x\in[0,1]^{d}$, and any Borel measurable subset ${\mathcal{A}}$ of
$[0,1]^{d}$, we have the following inequality:

$\displaystyle(1-a)\sum_{k=0}^{\infty}a^{k}P^{k}(x,{\mathcal{A}})$
$\displaystyle\geq$
$\displaystyle(1-a)\sum_{k=d}^{\infty}a^{k}P^{k}(x,{\mathcal{A}})\geq(1-a)\sum_{k=d}^{\infty}a^{k}{\mathbb{L}}({\mathcal{A}})$
$\displaystyle=$ $\displaystyle a^{d}{\mathbb{L}}({\mathcal{A}}).$

By Theorem 16.0.2 of [19], this implies that $X_{n}$ is irreducible and has at
most one invariant measure. In the next line, we show that this invariant
measure is, in fact, the Lebesgue measure on $[0,1]^{d}$:

$\displaystyle
P{\mathbb{L}}({\mathcal{A}}):=\int_{[0,1]^{d}}P(x,{\mathcal{A}})dx=\int_{0}^{1}\cdots\int_{0}^{1}{\mathbb{L}}({(x_{2},\cdots,x_{d},y)\in{\mathcal{A}}})dx_{2}\cdots
dx_{d}dy={\mathbb{L}}({\mathcal{A}}),$

where ${\mathbb{L}}$ is the Lebesgue measure on $[0,1]^{d}$.

Let $T$ denote the first time that $(X_{n})$ visits
${\mathcal{A}}_{v}:=\\{x\in[0,1]^{d}\ |\operatorname{\mbox{red}}(x)=v\\}.$
Since Doeblin’s condition holds for the aperiodic chain $X_{n}$, Theorem
16.0.2 of [19] also implies the existence of $\kappa_{v}>1$ such that

$\sup_{x\in[0,1]^{d}}{\mathbb{E}}(\kappa_{v}^{T}|X_{1}=x)<\infty,$ (11)

where ${\mathbb{E}}$ denotes the expectation operator with respect to the
probability measure ${\mathbb{P}}$. The inequality (11) implies that
${\mathbb{E}}(\kappa_{v}^{T})$ is finite. To proceed, we can write:

$\displaystyle{\mathbb{E}}(\kappa_{v}^{T})=\sum_{n=1}^{\infty}{\mathbb{P}}(T=n)\kappa_{v}^{n}=\sum_{n=1}^{\infty}\left({\mathbb{P}}(T>n-1)-{\mathbb{P}}(T>n)\right)\kappa_{v}^{n}$
$\displaystyle\quad=1+(\kappa_{v}-1)\sum_{n=1}^{\infty}{\mathbb{P}}(T>n)\kappa_{v}^{n}=1+(\kappa_{v}-1){\mathfrak{S}}_{0}^{v}(\kappa_{v}).$

We have now completed the proof of the first part. To prove the second part,
we can simply apply Markov’s inequality:

$\displaystyle{\mathbb{P}}(T>n\ |\
X_{1}=x)={\mathbb{P}}(\kappa_{v}^{T}>\kappa_{v}^{n}\ |\
X_{1}=x)\leq\frac{{\mathbb{E}}(\kappa_{v}^{T}\ |\ X_{1}=x)}{\kappa^{n}}.$

Therefore, we can write:

$\displaystyle
a_{n}^{(1)}(v)={\mathbb{P}}(T>n)\leq\int_{[0,1]^{d}}\frac{{\mathbb{E}}(\kappa_{v}^{T}\
|\
X_{1}=x)}{\kappa_{v}^{n}}dx\leq\left(\sup_{x\in[0,1]^{d}}{\mathbb{E}}(\kappa_{v}^{T}\
|\ X_{1}=x)\right)\kappa_{v}^{-n}.$

This implies that:

$\displaystyle\rho_{v}=\lim_{n}(a_{n}^{(1)}(v))^{\frac{1}{n}}\leq\frac{1}{\kappa_{v}}<1,$

which completes the proof of the second part. ∎

###  2.1 Linear recursions and c-Wilf-equivalence

In this section, we will utilize repetitive exclusion-inclusion arguments to
derive linear relations and deduce information about c-Wilf-equivalence among
patterns. The first main result we will present is the

###### Proof of Theorem 1.4-(a).

One key observation is that when $v$ is non-overlapping,
$\widetilde{\mathcal{B}}_{s}$ implies ${\mathcal{B}}^{s+d-2}_{s+1}$ for any
$s\in{\mathbb{N}}$. We can use this fact to express $a^{(1)}_{n}(v)$ as a
linear recursion. Specifically, for all $n\geq d$, we have:

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)={\mathbb{P}}({\mathcal{B}}_{2}^{n})-{\mathbb{P}}({\mathcal{B}}_{1}^{n})={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},{\mathcal{B}}_{d}^{n})$

If $n\geq 2d-1$, we can repeat the same argument for ${\mathcal{B}}_{d}$ to
obtain:

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},{\mathcal{B}}_{d+1}^{n})-{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},\widetilde{\mathcal{B}}_{d},{\mathcal{B}}_{2d-1}^{n})$

By applying this argument several times, we obtain:

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)=\sum_{k=0}^{m}(-1)^{k}{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},\cdots,\widetilde{\mathcal{B}}_{k(d-1)+1},{\mathcal{B}}_{k(d-1)+d+1}^{n}),$

where $m:=\lfloor\frac{n-1}{d-1}\rfloor$.

We now analyze the terms in the summation from the previous paragraph. For any
$0\leq k\leq m,$ we note that ${\mathcal{B}}_{kd-k+d+1}^{n}$ is independent of
all the other events
$\widetilde{\mathcal{B}}_{1},\cdots,\widetilde{\mathcal{B}}_{k(d-1)+1}$, so
their joint probability can be expressed as a product. Let
$\operatorname{\mathtt{A}}_{0}(v)=\frac{1}{d!}$ and recall that, by
stationarity,
${\mathbb{P}}({\mathcal{B}}_{kd-k+d+1}^{n})=a^{(1)}_{n-kd+k-d}(v)$. Therefore,
for $k\in{\mathbb{N}}$, we can write

$\displaystyle{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},\cdots,\widetilde{\mathcal{B}}_{k(d-1)+1},{\mathcal{B}}_{kd-k+d+1}^{n})=\operatorname{\mathtt{A}}_{k}(v)a^{(1)}_{n-kd+k-d}(v),$

where
$\operatorname{\mathtt{A}}_{k}(v):={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},\cdots,\widetilde{\mathcal{B}}_{k(d-1)+1})$.
This gives the recursion (4).

To compute $\operatorname{\mathtt{A}}_{k}(v)$, we can proceed as follows. Let

$z:=(z_{1}\cdots,z_{d},\cdots,z_{2d-1},\cdots,z_{kd-(k-1)},\cdots,z_{d(k+1)-k})$

be a permutation in ${\mathcal{S}}_{(k+1)d-k}$ that is obtained from the
standard reduction of an instance of the random sequence $Y_{1}\cdots
Y_{d(k+1)-k}$ satisfying
$\widetilde{\mathcal{B}}_{1}\cap\cdots\cap\widetilde{\mathcal{B}}_{k(d-1)+1}$
to a permutation. Since the number of choices for $z$ is
$((k+1)d-k)!\operatorname{\mathtt{A}}_{k}(v)$, we can obtain the closed
formula for $\operatorname{\mathtt{A}}_{k}(v)$ through an enumeration of $z$.
We set $x_{i}:=z_{id+1}$.

The condition
$\widetilde{\mathcal{B}}_{1}\cap\cdots\cap\widetilde{\mathcal{B}}_{k(d-1)+1}$
dictates the following conditions on $(x_{i})_{0\leq i\leq k+1}$ values:

  * •

Since $v_{1}<v_{d},$ we must have $x_{0}<x_{1}<\cdots<x_{k+1}$.

  * •

Out of $(k+1)d-k$ elements in the vector $z$, at least $v_{1}-1$ of them are
smaller than $x_{0}$ and at most $(d-v_{1})(k+1)$ of them are larger than
$x_{0}$. Hence,

$\displaystyle v_{1}\leq x_{0}\leq(k+1)v_{1}-k.$

  * •

Knowing $x_{0}$, the value of $x_{k+1}$ ranges between $x_{0}+(k+1)(v_{d}-1)$
and $(k+1)d-k-(d-v_{d})=k(d-1)+v_{d}$.

  * •

Knowing $x_{0}$ and $x_{k+1}$, for any fixed $1\leq i\leq k$, the value of
$x_{i}$ ranges between $x_{i-1}+v_{d}-v_{1}$ and $x_{k+1}-(k+1-i)(d-v_{1})$.

We define the $i$-th block of $z$ as $z_{(i-1)d+2}\cdots z_{id}$, where $1\leq
i\leq k+1$. To enumerate $z$ by parametrizing with respect to
$x_{0}<x_{1}<\cdots<x_{k}<x_{k+1}$, we need to count the number of choices for
each block of $z$ given that $x_{i-1}=z_{(i-1)d+1}$ and $x_{i}=z_{id+1}$ are
fixed. Then, we can use the following observations to count the number of
choices for each block:

  * •

There are exactly $v_{d}-v_{1}-1$ values in the $i$-th block that are between
$x_{i-1}$ and $x_{i}$. Therefore, the number of possible choices for the
$i$-th block is $\binom{x_{i}-x_{i-1}-1}{v_{d}-v_{1}-1}$.

  * •

There are only $(i+1)d+(k-i)v_{1}-k-x_{i}$ values that can be assigned to
$d-v_{d}-1$ elements of the $i$-th block that are larger than
$x_{i}=z_{id+1}$. Therefore, the number of choices for these elements is
$\binom{(i+1)d+(k-i)v_{1}-k-x_{i}}{d-v_{d}-1}$.

  * •

Similarly, there are only $x_{i-1}-(v_{d}-1)i-1$ values that can be assigned
to $v_{1}-1$ elements of the $i$-th block that are smaller than
$x_{i-1}=z_{(i-1)d+1}$. Therefore, the number of choices for these elements is
$\binom{x_{i-1}-(v_{d}-1)i-1}{v_{1}-1}$.

By collecting all the observations we have made so far, we obtain the
following expression:

$\displaystyle((k+1)d-k)!\operatorname{\mathtt{A}}_{k}(v)=\sum_{x_{0}=v_{1}}^{(k+1)v_{1}-k}\
\ \sum_{x_{k+1}=x_{0}+(k+1)(v_{d}-1)}^{k(d-1)+v_{d}}\ \
\sum_{x_{1}=x_{0}+v_{d}-v_{1}}^{x_{k+1}-k(d-v_{1})}\cdots$ (12)
$\displaystyle\qquad\sum_{x_{k}=x_{k-1}+v_{d}-v_{1}}^{x_{k+1}-(d-v_{1})}\prod_{i=1}^{k+1}\binom{x_{i}-x_{i-1}-1}{v_{d}-v_{1}-1}\binom{(i+1)d+(k-i)v_{1}-k-x_{i}}{d-v_{d}-1}\binom{x_{i-1}-(v_{d}-1)i-1}{v_{1}-1}.$

Hence, by combining (12) with (4), we can conclude that the proof is complete.
∎

We will continue with a similar line of argument and present the

###### Proof of Proposition 1.5.

Firstly, we observe that for any $k\in{\mathbb{N}}$ and $n\geq k$, the term
$a_{n}^{(k)}(v)$ can be expressed as

$\displaystyle a^{(k)}_{n}(v):={\mathbb{P}}(\cup_{1\leq
i_{1}<\cdots<i_{k-1}\leq
n}{\mathcal{B}}_{1}^{i_{1}-1}\cap\widetilde{\mathcal{B}}_{i_{1}}\cap{\mathcal{B}}_{i_{1}+1}^{i_{2}-1}\cap\cdots\cap\widetilde{\mathcal{B}}_{i_{k-1}}\cap{\mathcal{B}}_{i_{k-1}+1}^{n}),$

where $a_{0}^{(k)}=1.$ Next, for $n\geq 2$, we can write

$\displaystyle a^{(k)}_{n-1}(v)-a^{(k)}_{n}(v)=\sum_{1\leq
i_{1}<\cdots<i_{k-2}\leq
n-1}{\mathbb{P}}({\mathcal{B}}_{1}^{i_{1}-1},\widetilde{\mathcal{B}}_{i_{1}},{\mathcal{B}}_{i_{1}+1}^{i_{2}-1},\cdots,\widetilde{\mathcal{B}}_{i_{k-2}},{\mathcal{B}}_{i_{k-2}+1}^{n-1},\widetilde{\mathcal{B}}_{n}).$
(13)

We denote the term in the above summation by
$c_{i_{1},\cdots,i_{k-2}}^{(k-1)}$. Since $v$ is non-overlapping, i.e.
${\mathcal{O}}_{v}=\\{1\\},$ then $\widetilde{\mathcal{B}}_{j}$ implies that
the event ${\mathcal{B}}_{j+1}^{j+d-2}$ holds true for any $j$. Therefore, we
must have $i_{s}-i_{s-1}\geq d-1$ for all $2\leq s\leq k-2$. If
$i_{s}-i_{s-1}>d$ for some $2\leq s\leq k-2$, then by the independence of
events that are separated by more than $d-1$ variables, we can write
${\mathbb{P}}(\widetilde{\mathcal{B}}_{i_{1}},\cdots,\widetilde{\mathcal{B}}_{i_{k-2}})$
as
${\mathbb{P}}(\widetilde{\mathcal{B}}_{i_{1}},\cdots,\widetilde{\mathcal{B}}_{i_{s-1}}){\mathbb{P}}(\widetilde{\mathcal{B}}_{i_{s}},\cdots,\widetilde{\mathcal{B}}_{i_{k-2}})$.
The arrangement of these products is independent of the shape of $v$ and we
only used the fact that $v$ is non-overlapping. After applying the argument
repeatedly, we obtain that $c_{i_{1},\cdots,i_{k-2}}^{(k-1)}$ is a product of
$\operatorname{\mathtt{A}}_{k}(v)$ terms defined by (12).

Now, suppose that $v$ and $w$ are non-overlapping and c-Wilf-equivalent.
Therefore, by Theorem 1.4, we have
$\operatorname{\mathtt{A}}_{k}(v)=\operatorname{\mathtt{A}}_{k}(w)$ for all
$k\geq 2$, and consequently,
$c^{(k-1)}_{i_{1},\cdots,i_{k-1}}(v)=c^{(k-1)}_{i_{1},\cdots,i_{k-1}}(w)$ for
all $k\geq 2$. The proof follows from this fact and an obvious inductive
argument based on (13). ∎

We now turn to the

###### Proof of Theorem 1.6.

To prove the theorem, we will show that it holds true for $v=12\cdots d$. This
same reasoning applies to $v=d\cdots 1$ due to symmetry. It is important to
note that for any $s\in\mathbb{N}$, the event
$\widetilde{\mathcal{B}}_{s}\cap{\mathcal{B}}_{s+1}$ is equivalent to
$\widetilde{\mathcal{B}}_{s}\cap\\{Y_{s+d}<Y_{s+d-1}\\}$. Furthermore, this
event guarantees the occurrence of the event ${\mathcal{B}}_{s+2}^{s+d-1}$. By
utilizing this simple observation, we can write the following expression for
$n>d$:

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)={\mathbb{P}}({\mathcal{B}}_{2},{\mathcal{B}}_{3}^{n})-{\mathbb{P}}({\mathcal{B}}_{1},{\mathcal{B}}_{2},{\mathcal{B}}_{3}^{n})$
$\displaystyle\quad={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},{\mathcal{B}}_{2},{\mathcal{B}}_{3}^{n})={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},{\mathcal{B}}_{d+1}^{n}).$

We will now apply the same trick we used for ${\mathcal{B}}_{1}$ to
${\mathcal{B}}_{d+1}$. As a result, the right-hand side of the aforementioned
equation can be expressed as:

$\displaystyle{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},{\mathcal{B}}_{d+2}^{n})-{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},{\mathcal{B}}_{d+2},{\mathcal{B}}_{d+3}^{n})$
$\displaystyle\quad={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d}){\mathbb{P}}({\mathcal{B}}_{d+2}^{n})-{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},Y_{2d+1}<Y_{2d},{\mathcal{B}}_{2d+1}^{n})$

By repeating this line of reasoning, we can arrive at the following
expression:

$\displaystyle
a_{n-1}^{(1)}(v)-a_{n}^{(1)}(v)=\sum_{k=1}^{m}(-1)^{k-1}{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},\cdots,\widetilde{\mathcal{B}}_{(k-1)d+1},Y_{kd+1}<Y_{kd}){\mathbb{P}}({\mathcal{B}}_{kd+2}^{n})$
$\displaystyle\qquad+(-1)^{m}{\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},\cdots,Y_{md+1}<Y_{md},\widetilde{\mathcal{B}}_{md+1}),$

where $m=\lfloor\frac{n-1}{d}\rfloor$. Using stationarity, we can express the
equation as follows:

$\displaystyle
a_{n}^{(1)}(v)-a_{n-1}^{(1)}(v)+\sum_{k=1}^{m}(-1)^{k-1}M_{k}a_{n-kd-1}^{(1)}(v)+(-1)^{m}\widetilde{M}_{m}=0,$

Here, for $1\leq k\leq m$, we define $M_{k}$ as:

$\displaystyle
M_{k}:={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},\cdots,\widetilde{\mathcal{B}}_{(k-1)d+1},Y_{kd+1}<Y_{kd}).$

Additionally, we define $\widetilde{M}_{m}$ as:

$\displaystyle\widetilde{M}_{m}:={\mathbb{P}}(\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\widetilde{\mathcal{B}}_{d+1},\cdots,Y_{md+1}<Y_{md},\widetilde{\mathcal{B}}_{md+1}).$

To proceed, we will derive a closed-form expression for $M_{k}$ in terms of
$k$. Consider a permutation $z=(z_{1},\ldots,z_{kd+1})$ obtained from the
standard reduction of an instance of the random sequence
$Y_{1},\ldots,Y_{kd+1}$ satisfying
$\widetilde{\mathcal{B}}_{1},Y_{d+1}<Y_{d},\cdots,\widetilde{\mathcal{B}}_{(k-1)d+1},Y_{kd+1}<Y_{kd}$
to a permutation. Let $y_{i}=z_{id}$ and $x_{i}=z_{id+1}$, so that the pairs
$(y_{i},x_{i})$ correspond to adjacent entries in the permutation. The
conditions
$\widetilde{\mathcal{B}}_{1}\cap\\{Y_{d+1}<Y_{d}\\}\cap\cdots\cap\widetilde{\mathcal{B}}_{k(d-1)+1}\cap\\{Y_{kd+1}<Y_{kd}\\}$
impose the following constraints on the values $(z_{i})_{1\leq i\leq
k(d-1)+d}$:

  * •

$y_{i}<x_{i}$.

  * •

$x_{i}<y_{i+1}$.

With these properties in mind, we can count the number of possible sequences
$(z_{i})_{1\leq i\leq kd+1}$ by parametrizing them with respect to
$y_{1}<x_{1}<y_{2}<\cdots<y_{k}<x_{k}$. This count is equal to $(kd+1)!M_{k}.$
For $k=1$ we have

$\displaystyle(d+1)!M_{1}=\sum_{y_{1}=d}^{d+1}(y_{1}-1)\binom{y_{1}-1}{d-1}.$
(14)

For $k\geq 2$, we have

$\displaystyle(kd+1)!M_{k}=\sum_{y_{1}=d}^{d+1}\binom{y_{1}-1}{d-1}\sum_{x_{1}=1}^{y_{1}-1}\sum_{y_{2}=x_{1}+d-2}^{d+1}\binom{y_{2}-x_{1}-1}{d-2}\sum_{x_{2}=1}^{y_{2}-1}\times$
(15)
$\displaystyle\qquad\times\cdots\sum_{y_{k}=x_{k-1}+d-2}^{d+1}\binom{y_{k}-x_{k-1}-1}{d-2}\sum_{x_{k}=1}^{y_{k}-1}1.$

Similarly,

$\displaystyle(md+1)!\widetilde{M}_{m}=\sum_{y_{1}=d}^{d+1}\binom{y_{1}-1}{d-1}\sum_{x_{1}=1}^{y_{1}-1}\sum_{y_{2}=x_{1}+d-2}^{d+1}\binom{y_{2}-x_{1}-1}{d-2}\sum_{x_{2}=1}^{y_{2}-1}\times$
(16)
$\displaystyle\qquad\times\cdots\sum_{x_{m}=1}^{y_{m}-1}\sum_{y_{m}=x_{m-1}+d-2}^{d+1}\binom{y_{m}-x_{m-1}-1}{d-2}.$

This completes the proof. ∎

###  2.2 Bounds on the growth

As mentioned in the introduction, obtaining a linear recursion for the general
pattern $v$ appears to be challenging, if not impossible. However, we can
still derive linear recursion inequalities to obtain bounds.

###### Proof of Theorem 1.7-(a).

Let $a_{n}:={\mathbb{P}}({\mathcal{B}}_{1}^{n})$ and
$\beta_{n-1}:={\mathbb{P}}({\mathcal{B}}_{1}^{n-1},\widetilde{\mathcal{B}}_{n})$.
We can write the following equation:

$\displaystyle
a_{n}={\mathbb{P}}({\mathcal{B}}_{1}^{n})={\mathbb{P}}({\mathcal{B}}_{1}^{n-1})-{\mathbb{P}}({\mathcal{B}}_{1}^{n-1},\widetilde{\mathcal{B}}_{n})=a_{n-1}-\beta_{n-1},\qquad
n\geq 2.$ (17)

The initial condition is $a_{1}=1-\frac{1}{d!}.$ To turn this equation into an
inequality with homogeneous linear recurrence relations, we aim to bound the
term $\beta_{n-1}$ with a linear sum of terms $a_{i}$s. In pursuit of this
objective, for any $\ell\geq 2$ and any $n\geq\ell+d$, we write

$\displaystyle\beta_{n-1}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}({\mathcal{B}}_{1}^{n-1},\widetilde{\mathcal{B}}_{n})={\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1}\right){\mathbb{P}}\left({\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle=$ $\displaystyle a_{n-d-\ell+1}\beta_{\ell-1},$

where we utilize the independence property of ${\mathcal{B}}_{1}^{n-\ell-d+1}$
and ${\mathcal{B}}_{j}$ with $j\geq n-\ell+1$ for the third line. The
incorporation of this expression into equation (17) establishes the lower
bound.

In order to obtain the upper bound, we further assume $n>\ell+2d$. Then, we
can express $\beta_{n-1}$ as follows:

$\displaystyle\beta_{n-1}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
(19) $\displaystyle=$
$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle-{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1},\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right).$

We note that (19) can be further expressed as

$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1},{\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1}\right){\mathbb{P}}\left({\mathcal{B}}_{n-\ell+1}^{n-1},\widetilde{\mathcal{B}}_{n}\right)$
(20) $\displaystyle=$ $\displaystyle a_{n-\ell-d+1}\beta_{\ell-1}.$

For the term (19), we observe that

$\displaystyle{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-d+1},\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}},{\mathcal{B}}_{n-\ell+1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle\quad\leq{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-2d+2},\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}},{\mathcal{B}}_{n-\ell+1},\widetilde{\mathcal{B}}_{n}\right)$
$\displaystyle\quad={\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-2d+2}\right){\mathbb{P}}\left(\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}}\right){\mathbb{P}}\left({\mathcal{B}}_{n-\ell+1},\widetilde{\mathcal{B}}_{n},\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}}\right)$
$\displaystyle\quad\leq\frac{d-1}{d!}{\mathbb{P}}\left({\mathcal{B}}_{1}^{n-\ell-2d+2}\right)=\frac{d-1}{d!}a_{n-\ell-2d+2},$
(21)

where for the last inequality we applied

$\displaystyle{\mathbb{P}}\left(\widetilde{{\mathcal{B}}_{n-\ell-d+2}^{n-\ell}}\right)={\mathbb{P}}\left(\cup_{i=n-\ell-d+2}^{n-\ell}\widetilde{\mathcal{B}}_{i}\right)\leq\sum_{i=n-\ell-d+2}^{n-\ell}{\mathbb{P}}(\widetilde{\mathcal{B}}_{i})=\frac{d-1}{d!}.$

We utilize the inequalities (21) and (20) to arrive at the following
inequality:

$\displaystyle\beta_{n-1}\geq\beta_{\ell-1}a_{n-\ell-d+1}-\frac{d-1}{d!}a_{n-\ell-2d+2}.$

By inserting the above inequality back into (17), we have successfully
completed the proof of the upper bound. ∎

Next, we will derive an additional bound by presenting the

###### Proof of Theorem 1.9-(a).

We fix $\alpha\in\mathbb{N}$ and decompose the sequence $(Z_{n})$ into equal
blocks of length $\alpha d$. In what follows, we repeatedly utilize the
stationarity of the sequence $({\mathcal{B}}_{n})_{n\in{\mathbb{N}}}$ and the
independence of the blocks ${\mathcal{B}}_{n}$ and
$({\mathcal{B}}_{n+d+i})_{i\in{\mathbb{N}}_{0}}$, for all $n\in{\mathbb{N}}$.
Let $\lambda:=1+d(\alpha-1)$. We first express

$\displaystyle\left|{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
kd})-{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k}\right|=$
$\displaystyle=\left|\sum_{j=0}^{k-1}{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{j}\left({\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j)})-{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda}){\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j-1)})\right)\right|$
$\displaystyle=\sum_{j=0}^{k-2}{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{j}\left|{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j)})-{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j-1)},{\mathcal{B}}_{\alpha d(k-j)-\lambda+1}^{\alpha d(k-j)})\right|$
(22)
$\displaystyle\quad+{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k-1}\left|{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d})-{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})\right|,$ (23)

where (22) is obtained by using the independence of ${\mathcal{B}}_{1}^{\alpha
d(k-j-1)}$ and ${\mathcal{B}}_{\alpha d(k-j)-\lambda+1}^{\alpha d(k-j)+1}$ for
each $0\leq j\leq k-2$ and the stationarity.

The above expression in equation (22) can be bounded as follows:

$\displaystyle\left|{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j)})-{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
d(k-j-1)},{\mathcal{B}}_{\alpha d(k-j)-\lambda+1}^{\alpha d(k-j)})\right|$
$\displaystyle\quad={\mathbb{P}}\left({\mathcal{B}}_{1}^{\alpha
d(k-j-1)},\widetilde{{\mathcal{B}}_{\alpha d(k-j-1)+1}^{\alpha
d(k-j)-\lambda}},{\mathcal{B}}_{\alpha d(k-j)-\lambda+1}^{\alpha
d(k-j)}\right)$
$\displaystyle\quad\leq{\mathbb{P}}\left(\cap_{s=0}^{k-j-2}\\{{\mathcal{B}}_{\alpha
ds+d}^{\alpha ds+\alpha d}\\},\widetilde{{\mathcal{B}}_{\alpha
d(k-j-1)+1}^{\alpha d(k-j)-\lambda}},{\mathcal{B}}_{\alpha
d(k-j)-\lambda+1}^{\alpha d(k-j)}\right)$
$\displaystyle\quad\leq{\mathbb{P}}\left(\cap_{s=0}^{k-j-2}\\{{\mathcal{B}}_{\alpha
ds+d}^{\alpha ds+\alpha d}\\},{\mathcal{B}}_{\alpha d(k-j)-\beta+1}^{\alpha
d(k-j)}\right)$
$\displaystyle\quad={\mathbb{P}}\left({\mathcal{B}}_{1}^{\lambda}\right)^{k-j-1}{\mathbb{P}}\left({\mathcal{B}}_{\alpha
d(k-j)-\lambda+1}^{\alpha d(k-j)}\right)$
$\displaystyle\quad={\mathbb{P}}\left({\mathcal{B}}_{1}^{\lambda}\right)^{k-j}.$

This shows that the summation in equation (22) is bounded by
$k{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k}.$ The rightmost factor of
equation (23) can be bounded above by two. Combining these bounds yields

$\displaystyle\left|{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
kd})-{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k}\right|$ $\displaystyle\leq$
$\displaystyle
k{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k}+2{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k-1}$
$\displaystyle\leq$
$\displaystyle(k+2){\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{k-1}.$

This establishes the validity of (7). Finally, as the limit
$(a_{n}^{(1)})^{\frac{1}{n}}$ exists as $n$ approaches infinity, we can pass
the limit to a subsequence and obtain

$\displaystyle\rho_{v}:=\lim_{n}(a^{(1)}_{n}(v))^{\frac{1}{n}}=\lim_{k}{\mathbb{P}}({\mathcal{B}}_{1}^{\alpha
kd})^{\frac{1}{\alpha kd}}$
$\displaystyle\quad\leq\lim_{k}\left(k+2+{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})\right)^{\frac{1}{\alpha
kd}}{\mathbb{P}}({\mathcal{B}}_{1}^{\lambda})^{\frac{k-2}{\alpha kd}}$
$\displaystyle\quad=a^{(1)}_{\lambda}(v)^{\frac{1}{\alpha
d}}=\left(\frac{g^{v}_{0}({\mathcal{S}}_{\alpha d})}{(\alpha
d)!}\right)^{\frac{1}{\alpha d}}.$

This concludes the proof of the inequality (8). ∎

Lastly, we present another set of bounds on the growth rate by providing the

###### Proof of Theorem 1.9-(b).

The first part of this result follows directly from Theorem 1.7. However, to
establish the lower bound, we must determine a lower bound for the dominant
root of the equation (9). To this end, we define $m=d+\ell-1$ and consider the
function $f(x)=x^{m}-x^{m-1}-\beta_{\ell-1}$. The roots of the derivative of
$f$ are $0$ with multiplicity $m-2$ and $\frac{m-1}{m}$ with multiplicity $1$.
Since $\beta_{\ell-1}>0$, $0$ cannot be a root of $f$ and we have

$\displaystyle
f\left(\frac{m-1}{m}\right)=-\frac{(m-1)^{m-1}}{m^{m}}+\beta_{\ell-1}.$

Therefore, $\frac{m-1}{m}$ is a root of $f$ with multiplicity $2$ if and only
if $\beta_{\ell-1}=\frac{(m-1)^{m-1}}{m^{m}}$.

Since $\ell$ is chosen such that
$\beta_{\ell-1}\neq\frac{(m-1)^{m-1}}{m^{m}}$, then $f(.)$ has $m$ roots
$\lambda_{1},\cdots\lambda_{m}$ each with multiplicity one. Thus, by (8) we
can find constants $q_{i}$s independent of $n$ so that $a_{n}^{(1)}(v)$ is
bounded below by

$\displaystyle a_{n}^{(1)}(v)\geq\sum_{i=1}^{m}q_{i}\lambda_{i}^{n}.$

We refer to the dominant root by $\rho_{v,\ell}$. Suppose $g(x)=x^{m}-x^{m-1}$
and observe that $f(x)-g(x)=\beta_{\ell-1}$ for all $x\in{\mathbb{C}}.$ We
apply Rouché’s Theorem (See [24], page 262) to locate the roots of $f(x)$ by
understanding the roots of $g(x).$

We need to find a simple closed contour, denoted by $C$, such that the
inequality

$\displaystyle|g(x)|>|f(x)-g(x)|$ (24)

holds for all $x$ on $C$. According to Rouché’s Theorem, if such a contour $C$
exists, then $f(x)$ and $g(x)$ must have the same number of roots (counting
multiplicities) inside $C$. To satisfy the condition in equation (24) on the
boundary of $C$, we choose $C$ to be a circle with an appropriate radius
$\delta$ centered at the origin. We need to ensure that $\delta<1$ so that the
following inequality holds true:

$\displaystyle|g(x)|$ $\displaystyle=$
$\displaystyle|x^{m}-x^{m-1}|\geq||x|^{m}-|x|^{m-1}|=|\delta^{m}-\delta^{m-1}|$
$\displaystyle=$
$\displaystyle\delta^{m-1}-\delta^{m}>\beta_{\ell-1}=|f(x)-g(x)|.$

We can find such $\delta<1$ by choosing
$\delta=\left(\beta_{\ell-1}\right)^{\frac{1}{(m-1)(1+\alpha)}}$ for some
$\alpha>0$. Substituting this into the inequality above, we get:

$\displaystyle
1<\left(1-\left(\beta_{\ell-1}\right)^{\frac{1}{(m-1)(1+\alpha)}}\right)\left(\frac{1}{\beta_{\ell-1}}\right)^{\frac{\alpha}{1+\alpha}}.$

A straightforward calculation shows that there exists $\gamma>1$ such that

$\displaystyle
1-\beta_{\ell-1}-\left(\beta_{\ell-1}\right)^{\gamma}\leq\delta=\left(\beta_{\ell-1}\right)^{\frac{1}{(m-1)(1+\alpha)}}.$

Since $0$ is a root of $g(x)$ with a multiplicity of $m-1$, $f(x)$ also has
$m-1$ roots inside $C$, and the remaining root is not inside $C$. This root
must be real, since otherwise, its conjugate would also be a root of $f(x)$
outside of $C$, which would be a contradiction. Moreover, this root is also
the dominant root $\rho_{v,l}$ since it is farthest from the origin.
Therefore, we have
$1-\beta_{\ell-1}-\beta_{\ell-1}^{\gamma}\leq\delta\leq\rho_{v,l}$, as
intended. ∎

##  3 Consecutive containment in words

We will now begin our analysis concerning consecutive containment in words. At
the outset, we leverage analogous argument with the same essence as of those
in the previous section. To that goal, fix the integer number
$\operatorname{\mathtt{K}}>d$, and define an i.i.d sequence of experiments
$W:=(W_{n})_{n\in{\mathbb{N}}}$ with each $W_{n}$ sampled independently and
uniformly from $[\operatorname{\mathtt{K}}].$ We will denote by ${\mathbb{P}}$
the probability law in a suitable probability space that supports all random
variables considered in this section. Consider a discrete-time Markov process
$(Z_{n})_{n\in{\mathbb{N}}}$ on the space $[\operatorname{\mathtt{K}}]^{d}$,
where $Z_{n}:=W_{n}\cdots W_{n+d-1}$. The transition probability of the
process $Z_{n}$ is defined as

$\displaystyle P(w,{\mathcal{A}})=\frac{1}{\operatorname{\mathtt{K}}}\\#\\{y\
|w_{2}\cdots w_{d}y\in{\mathcal{A}}\\},\quad w:=w_{1}\cdots
w_{d}\in[\operatorname{\mathtt{K}}]^{d},\quad{\mathcal{A}}\subset[\operatorname{\mathtt{K}}]^{d}.$

Recall (3). Since $W_{1}\cdots W_{n}$ is a uniformly randomly sampled word
from $[\operatorname{\mathtt{K}}]^{n}$, then

$\displaystyle
h_{\operatorname{\mathtt{K}},n}^{(r+1)}(v)=\frac{g_{r}^{v}([\operatorname{\mathtt{K}}]^{n+d-1})}{\operatorname{\mathtt{K}}^{n+d-1}}={\mathbb{P}}(\operatorname{\mbox{con}}_{v}(W_{1}\cdots
W_{n+d-1})=r).$

In the rest of this section, we will use ${\mathcal{D}}_{i}(v)$ to denote the
event $\\{\operatorname{\mbox{red}}(Z_{i})\neq v\\}$. We define
${\mathcal{D}}_{i}^{j}(v)$ as $\cap_{s=i}^{j}{\mathcal{D}}_{s}(v)$ for $i\leq
j$. When $i>j$, we define ${\mathcal{D}}_{i}^{j}(v)$ as the entire set. We
will drop the subscript $v$ whenever the context is clear.

We now present the

###### Proof of Theorem 1.4-(b).

The proof shares many similarities with that of Theorem 1.4-(a), but also
includes several differences. Therefore, our focus will be on highlighting
these differences while omitting the parts that are similar. Since $v$ is non-
overlapping, we can write

$\displaystyle
h_{\operatorname{\mathtt{K}},n}^{(1)}(v)=h_{\operatorname{\mathtt{K}},n-1}^{(1)}(v)-\sum_{k=0}^{m}(-1)^{k}\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},k}(v)h^{(1)}_{\operatorname{\mathtt{K}},n-kd+k-d}(v),$

where
$\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},k}(v):={\mathbb{P}}(\widetilde{\mathcal{D}}_{1},\cdots,\widetilde{\mathcal{D}}_{k(d-1)+1})$
and $m:=\lceil\frac{n-1}{d-1}\rceil$. To compute
$\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},k}(v)$ we proceed as
follows. Let

$w:=(w_{1}\cdots,w_{d},\cdots,w_{2d-1},\cdots,w_{kd-(k-1)},\cdots,w_{d(k+1)-k})$

be a word in $[\operatorname{\mathtt{K}}]^{(k+1)d-k}$ sampled by the random
sequence $W_{1}\cdots W_{d(k+1)-k}$ satisfying
$\widetilde{\mathcal{D}}_{1}\cap\cdots\cap\widetilde{\mathcal{D}}_{k(d-1)+1}$.
Since the number of choices for $w$ equals to
$\operatorname{\mathtt{K}}^{(k+1)d-k}\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},k}(v),$
we obtain the formula for $\operatorname{\mathtt{H}}_{k}(v)$ through an
enumeration of $w$. Set $x_{i}:=w_{id+1}$ and assume without loss of
generality $v_{1}<v_{d}$. The assumption
$\widetilde{\mathcal{D}}_{1}\cap\cdots\cap\widetilde{\mathcal{D}}_{k(d-1)+1}$
dictates the following conditions on $(x_{i})_{0\leq i\leq k+1}$ values:

  * •

We must have $x_{0}<x_{1}<\cdots<x_{k+1}$. This immediately implies that
$\operatorname{\mathtt{H}}_{k}(v)=0$ for all $k>\operatorname{\mathtt{K}}$.

  * •

Out of $(k+1)d-k$ elements in the vector $w$, at least $v_{1}-1$ of them are
smaller than $x_{0}$ and at most $(d-v_{1})(k+1)$ of them are larger than
$x_{0}$. Hence,

$\displaystyle v_{1}\leq x_{0}\leq\operatorname{\mathtt{K}}-(d-v_{1})(k+1).$

  * •

Knowning $x_{0}$, the value of $x_{k+1}$ ranges between $x_{0}+(k+1)(v_{d}-1)$
and $\operatorname{\mathtt{K}}-(d-v_{d})=\operatorname{\mathtt{K}}+v_{d}-d$.

  * •

Knowning $x_{0}$ and $x_{k+1}$, for any fixed $1\leq i\leq k$, the value of
$x_{i}$ ranges between $x_{i-1}+v_{d}-v_{1}$ and $x_{k+1}-(k+1-i)(d-v_{1})$.

Next, we enumerate $w$ by parametrizing with respect to
$x_{0}<x_{1}<\cdots<x_{k}<x_{k+1}$. To that end, for any $1\leq i\leq k+1$,
let us define $i$-th blocks of $w$ as $w_{(i-1)d+2}\cdots w_{id}$. For a fixed
$1\leq i\leq k+1,$ we are interested in finding the number of choices for the
$i$-th block when $x_{i}=w_{id+1}$ and $x_{i-1}=w_{(i-1)d+1}$ values are
given. Observe that

  * •

There are exactly $v_{d}-v_{1}-1$ values in the $i$-th block that are between
$x_{i-1}$ and $x_{i}$. The number possible choices for $i$-th block is
therefore

$\displaystyle\binom{x_{i}-x_{i-1}-1}{v_{d}-v_{1}-1}.$

  * •

There are only $(\operatorname{\mathtt{K}}-x_{i-1})-(k-i)(d-v_{1}-1)-1$ values
that can be assigned to $d-v_{d}-1$ elements of the $i$-th block that are
larger than $x_{i}=z_{id+1}$. The number choices are

$\displaystyle\binom{(\operatorname{\mathtt{K}}-x_{i-1})-(k-i)(d-v_{1}-1)-1}{d-v_{d}-1}.$

  * •

Similarly, there are only $x_{i}-1-(i-1)(v_{d}-2)-(i-1)=x_{i-1}-(v_{d}-1)i-1$
values that can be assigned to $v_{1}-1$ elements of the $i$-th block that are
smaller than $x_{i-1}=z_{(i-1)d+1}.$ The number of choices are

$\displaystyle\binom{x_{i-1}-(v_{d}-1)i-1}{v_{1}-1}.$

By collecting all the observations we have made so far, using the convention
that $\sum_{i}^{j}.=0$ for $j<i$, we arrive at the following expression:

$\displaystyle\operatorname{\mathtt{K}}^{(k+1)d-k}\operatorname{\mathtt{H}}_{\operatorname{\mathtt{K}},k}(v)=\sum_{x_{0}=v_{1}}^{(k+1)v_{1}-k}\
\ \sum_{x_{k+1}=x_{0}+(k+1)(v_{d}-1)}^{k(d-1)+v_{d}}\ \
\sum_{x_{1}=x_{0}+v_{d}-v_{1}}^{x_{k+1}-k(d-v_{1})}\cdots\sum_{x_{k}=x_{k-1}+v_{d}-v_{1}}^{x_{k+1}-(d-v_{1})}$
(25)
$\displaystyle\qquad\quad\prod_{i=1}^{k+1}\binom{x_{i}-x_{i-1}-1}{v_{d}-v_{1}-1}\binom{(\operatorname{\mathtt{K}}-x_{i-1})-(k-i)(d-v_{1}-1)-1}{d-v_{d}-1}\binom{x_{i-1}-(v_{d}-1)i-1}{v_{1}-1}.$

Therefore, (5) together with (25) completes the proof. ∎

###  3.1 Connection with a classical probability problem

In this section, our focus is on proving Theorem 1.3. To achieve this goal, we
will draw a connection to a classical probability problem that has been
extensively studied. However, before we do so, we need to define the framework
and review some relevant existing results. In [16], Li proposed a martingale
method for studying the occurrence of a set of predefined sequences of
observations (patterns) in a sequence of independently repeated experiments.
This method involves describing a gambling game among multiple teams and
forming a system of equations that relate the expected waiting time until any
consecutive observation sequence appears to the probability that one of the
patterns precedes the remaining ones. Gerber and Li [12] extended this work by
using a Markov chain embedding technique to calculate the generating functions
of waiting time distributions for patterns. The martingale method was further
refined by Pozdnyakov et al. [23] and by Zajkowski [26]. It should be noted
that the concept of a pattern in these papers differs slightly from our
definition of a pattern in this paper; Li’s “pattern” refers to what we refer
to as a “pattern instance.” Here, we present the framework in the style used
in [26]. We remark that the original framework is more general; however, for
simplicity, we simplify the framework to suit our purposes.

To establish context, let us define a correlation value between two words of
equal length that is crucial to our analysis. Specifically, for any $\alpha$
in the interval $(0,1)$ and any two words $u$ and $s$ in
$[\operatorname{\mathtt{K}}]^{d}$, the $\alpha$-correlation of $u$ and $s$ is
defined as:

$\displaystyle(u*s)_{\alpha,\operatorname{\mathtt{K}}}=\sum_{i=1}^{d}\left(\frac{\operatorname{\mathtt{K}}}{\alpha}\right)^{i}\mbox{\bf
1}_{\\{u[d-i+1,d]=s[1,i]\\}},$ (26)

where we use the notation $s[i,j]:=s_{i}\cdots s_{j}$ to denote any substring
of the word $s:=s_{1}\cdots s_{d}$, where $1\leq i\leq j\leq d$.

Suppose ${\mathcal{I}}$ be a set of words in
$[\operatorname{\mathtt{K}}]^{d}$. We define various notions of hitting times
for the set ${\mathcal{I}}$. Throughout our proofs, we may use different
values for ${\mathcal{I}}$ and may adopt different subscripts or postscripts
in the notations to maintain focus on the context or simplify the notation.
For any two words $t$ and $s$, we define

$\displaystyle\tau(t,s):=\inf\\{n\in{\mathbb{N}}\ |\ s\mbox{ suffixes the
sequence }t_{1}\cdots t_{d}W_{1}\cdots W_{n}\\}$

to be the first time that the sequence $u_{1}\cdots u_{\ell}W_{1}\cdots W_{n}$
ends with the word $s$ as a postfix. Then, for any given word $t$, we define

$\displaystyle T^{(1)}(t):=\inf_{s\in{\mathcal{I}}}\tau(t,s).$

At $T^{(1)}(.)$, the visited word can be any of the words in $\mathcal{I}$.
Thus, we introduce $Q(.,s)$ to denote the probability that $s$ is the specific
instance. More formally, we set $Q(t,s)$ as the probability that
$T^{(1)}(t)=\tau(t,s)$, that is:

$\displaystyle Q(t,s):={\mathbb{P}}(T^{(1)}(t)=\tau(t,s)).$

We will now explain how to obtain information about the hitting time and
hitting probability. For this purpose, we will follow the framework of [26],
but interested readers can find more detailed discussions in [12, 16, 22, 23].
Recall the definition of $\alpha$-correlation from (26). Using Proposition 4.1
from [26], we obtain the following equation:

$\displaystyle{\mathbb{E}}(\alpha^{T^{(1)}(t)})+\sum_{s\in{\mathcal{I}}}(s*q)_{\alpha}{\mathbb{E}}\left(\alpha^{T^{(1)}(t)}\mbox{\bf
1}_{\\{T^{(1)}(t)=\tau(t,s)\\}}\right)=(t*q)_{\alpha,k},\qquad\forall
q\in{\mathcal{I}}.$ (27)

We also have the trivial equation

$\displaystyle{\mathbb{E}}(\alpha^{T^{(1)}(t)})=\sum_{s\in{\mathcal{I}}_{v}(k)}{\mathbb{E}}\left(\alpha^{T^{(1)}(t)}\mbox{\bf
1}_{\\{T^{(1)}(t)=\tau(t,s)\\}}\right).$ (28)

To express the solution of the system (27) and (28), we construct a
correlation matrix $R(\alpha)$ for $\mathcal{I}$, which contains
$\alpha$-correlation values among the words in ${\mathcal{I}}$. For any pair
$(u,s)\in{\mathcal{I}}\times{\mathcal{I}}$, the $(u,s)$-entry of the matrix,
denoted by $[R(\alpha)]_{u,s}$, is defined as follows:

$\displaystyle[R(\alpha)]_{u,s}:=(u*s)_{\alpha,k}.$ (29)

Suppose $u,s\in{\mathcal{I}}$ and $t\in[\operatorname{\mathtt{K}}]^{d}$. We
define $R_{u,t}(\alpha)$ (resp. $R^{u}(\alpha)$) to be the matrix attained by
replacing the column (resp. the row) corresponding to $u$ in $R(\alpha)$ with
the column (resp. the row vector) $((t*u)_{\alpha})_{s\in{\mathcal{I}}}$
(resp. $(1)_{s\in{\mathcal{I}}}$). $R_{s,t}^{u}(\alpha)$ is obtained by
replacing the $u$-th column of $R_{s,t}(\alpha)$ with the column vector of
units $(1)_{u\in{\mathcal{I}}}$. The solution of the system (27) and (28) can
be described in terms of $R(\alpha)$ as defined by (29), $R^{u}(\alpha)$, and
$R_{u,t}(\alpha)$. More specifically, Proposition 4.1, [26] states

$\displaystyle{\mathbb{E}}(\alpha^{T^{(1)}(t)})=1-(1-\alpha)\frac{\det
R(\alpha)-\sum_{u\in{\mathcal{I}}}\det R_{u,t}(\alpha)}{(1-\alpha)\det
R(\alpha)+\sum_{u\in{\mathcal{I}}}\det R^{u}(\alpha)},$ (30)

and

$\displaystyle{\mathbb{E}}\left(\alpha^{T^{(1)}(t)}\mbox{\bf
1}_{\\{T^{(1)}(t)=\tau(t,s)\\}}\right)=\frac{(1-\alpha)\det
R^{s}(\alpha)+\sum_{u\in{\mathcal{I}}}\det R_{s,t}^{u}(\alpha)}{(1-\alpha)\det
R(\alpha)+\sum_{u\in{\mathcal{I}}}\det R^{u}(\alpha)}.$ (31)

As discussed in Remark 4.2 of [26], we can greatly simplify these solutions by
substituting $t=\epsilon$ and using the identity $(\epsilon*s)_{\alpha}=0$.
Let us define $\tau(u)$ to be $\tau(\epsilon,u)$ and set
$T^{(1)}:=T^{(1)}(\epsilon)$. Then,

$\displaystyle{\mathbb{E}}(\alpha^{T^{(1)}})=1-(1-\alpha)\frac{\det
R(\alpha)}{(1-\alpha)\det R(\alpha)+\sum_{u\in{\mathcal{I}}}\det
R^{u}(\alpha)}$

and

$\displaystyle{\mathbb{E}}\left(\alpha^{T^{(1)}}\mbox{\bf
1}_{\\{T^{(1)}=\tau(u)\\}}\right)=\frac{\det R^{u}(\alpha)}{(1-\alpha)\det
R(\alpha)+\sum_{s\in{\mathcal{I}}}\det R^{s}(\alpha)}.$

Next, we define the sequences of random variables $(T^{(r)})_{r\geq 1}$ and
$(T^{(r)}(u))_{r\geq 1}$ as follows. For $r\geq 2$, we set

$\displaystyle T^{(r)}:=\inf\\{n>T^{(r-1)}\ |\ W_{n-d+1}\cdots
W_{n}\in{\mathcal{I}}\\},$ (32)

and

$\displaystyle T^{(r)}(u):=\inf\\{n>T^{(r-1)}(u)\ |\ W_{n-d+1}\cdots
W_{n}\in{\mathcal{I}}\\}.$

A straightforward calculation yields the following lemma, which is the main
ingredient in the proof of Theorem 1.3.

######  Lemma 3.1.

For any $r\in{\mathbb{N}},$ ${\mathbb{E}}(\alpha^{T^{(r)}})$ depends only on
the matrix $R(\alpha)$s, $R^{u}(\alpha)$s, $R_{s,t}(\alpha)$s, and
$R_{s,t}^{u}(\alpha)$s.

###### Proof.

Suppose $r\geq 2$. We use the definition (32) to write

$\displaystyle{\mathbb{E}}(\alpha^{T^{(r)}(s)})$ $\displaystyle=$
$\displaystyle\sum_{u\in{\mathcal{I}}}{\mathbb{E}}\left(\alpha^{T^{(r)}(s)}\mbox{\bf
1}_{\\{T^{(1)}(s)=\tau(s,u)\\}}\right)$ $\displaystyle=$
$\displaystyle\sum_{u\in{\mathcal{I}}}{\mathbb{E}}\left(\alpha^{\tau(s,u)+T^{(r-1)}(u)}\mbox{\bf
1}_{\\{T^{(1)}(s)=\tau(s,u)\\}}\right)$ $\displaystyle=$
$\displaystyle\sum_{u\in{\mathcal{I}}}{\mathbb{E}}\left(\alpha^{T^{(1)}(s)}\mbox{\bf
1}_{\\{T^{(1)}(s)=\tau(s,u))\\}}\right){\mathbb{E}}\left(\alpha^{T^{(r-1)}(u)}\right).$

An inductive argument, based on this recursive relation, along with (30) and
(31) for $T^{(r-1)}(s)$, provides us with the proof. However, we will not
provide an explicit description of them since they are not necessary for our
purposes. ∎

We now have the necessary tools to prove Theorem 1.3. To this end, we will
briefly discuss the correlation matrix of a pattern and how it can aid in
computing the generating function of
$g_{r}^{v}([\operatorname{\mathtt{K}}]^{n})$, denoted by
${\mathfrak{W}}_{r,\operatorname{\mathtt{K}}}^{v}$:

$\displaystyle{\mathfrak{W}}_{r,\operatorname{\mathtt{K}}}^{v}(x)=\sum_{n=d}^{\infty}g_{r}^{v}([\operatorname{\mathtt{K}}]^{n})x^{n},\quad\operatorname{\mathtt{K}}\in{\mathbb{N}},\
r\in{\mathbb{N}}_{0}.$

Take $\operatorname{\mathtt{K}}\geq d$ fixed, and consider any pattern
$v\in{\mathcal{S}}_{d}$. For any subset
${\mathcal{A}}\subseteq[\operatorname{\mathtt{K}}]^{d}$, let $v_{\mathcal{A}}$
be the instance of the pattern $v$ formed by using only the letters in
${\mathcal{A}}$. For example, $231_{\\{1,3,9\\}}=391$. Define
${\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$ to be the set of all instances
of $v$ in the alphabet $[\operatorname{\mathtt{K}}]$, that is,

$\displaystyle{\mathcal{I}}_{v}(\operatorname{\mathtt{K}}):=\\{v_{\mathcal{A}}\
|{\mathcal{A}}\in[\operatorname{\mathtt{K}}]_{d}\\}.$ (33)

For instance, if $v=132$ and $k=4$, then

$\displaystyle{\mathcal{I}}_{v}(\operatorname{\mathtt{K}})=\\{132,142,143,243\\}.$

We create a correlation matrix, denoted by
$R(\alpha,v,\operatorname{\mathtt{K}})$, for ${\mathcal{I}}_{v}(k)$, which is
composed of $\alpha$-correlation values among the words in
${\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$. For any pair
$(u,s)\in{\mathcal{I}}_{v}(\operatorname{\mathtt{K}})\times{\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$,
the entry of the matrix corresponding to $(u,s)$, denoted by
$[R(\alpha,v,\operatorname{\mathtt{K}})]_{u,s}$, is defined as
$(u*s)_{\alpha,\operatorname{\mathtt{K}}}$.

Recall the definition of ${\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$ from
(33). To simplify the notation, we replace the superscript and subscript $u$,
$s$, $t$ in the correlation matrices by the corresponding $d$-sets
${\mathcal{A}}$, ${\mathcal{B}}$, and so on. Thus, when we use ${\mathcal{A}}$
as the subscript or superscript, it should be replaced by $v_{\mathcal{A}}$.
For a fixed pattern $v\in{\mathcal{S}}_{d}$ and alphabet size
$\operatorname{\mathtt{K}}$, the matrix
$R(\alpha,v,\operatorname{\mathtt{K}})$ is a
$\binom{\operatorname{\mathtt{K}}}{d}\times\binom{\operatorname{\mathtt{K}}}{d}$
matrix, and for any pair
$({\mathcal{A}},{\mathcal{B}})\in[\operatorname{\mathtt{K}}]_{d}\times[\operatorname{\mathtt{K}}]_{d}$,
the $({\mathcal{A}},{\mathcal{B}})$-entry of
$R(\alpha,v,\operatorname{\mathtt{K}})$, denoted by
$[R(\alpha,v,\operatorname{\mathtt{K}})]_{{\mathcal{A}},{\mathcal{B}}}$, can
be expressed as follows:

$\displaystyle[R(\alpha,v,\operatorname{\mathtt{K}})]_{{\mathcal{A}},{\mathcal{B}}}$
$\displaystyle=$
$\displaystyle(v_{\mathcal{A}}*v_{\mathcal{B}})_{\alpha,k}=\frac{1}{\alpha^{d}}\sum_{i=1}^{d}\operatorname{\mathtt{K}}^{i}\alpha^{d-i}\mbox{\bf
1}_{\\{v_{\mathcal{A}}[d-i+1,d]=v_{\mathcal{B}}[1,i]\\}}$ $\displaystyle=$
$\displaystyle\mbox{\bf
1}_{\\{{\mathcal{A}}={\mathcal{B}}\\}}\left(\frac{\operatorname{\mathtt{K}}}{\alpha}\right)^{d}+\sum_{i\in{\mathcal{O}}_{v}}\left(\frac{\operatorname{\mathtt{K}}}{\alpha}\right)^{i}\mbox{\bf
1}_{\\{v_{\mathcal{A}}[d-i+1,d]=v_{\mathcal{B}}[1,i]\\}}.$

For example, if $v\in{\mathcal{S}}_{d}$ is a non-overlapping pattern, then for
$\operatorname{\mathtt{K}}\geq d$, the $({\mathcal{A}},{\mathcal{B}})$-entry
of the correlation matrix $R(\alpha,v,\operatorname{\mathtt{K}})$ is given by
(34):

$\displaystyle[R(\alpha,v,\operatorname{\mathtt{K}})]_{{\mathcal{A}},{\mathcal{B}}}=\begin{cases}\left(\frac{\operatorname{\mathtt{K}}}{\alpha}\right)^{d}&\text{if
}{\mathcal{A}}={\mathcal{B}}\\\
\frac{\operatorname{\mathtt{K}}}{\alpha}&\text{if
}(v_{\mathcal{A}})_{d}=(v_{\mathcal{B}})_{1}\\\
0&\text{otherwise}\end{cases}.$ (34)

Note that for $({\mathcal{A}},{\mathcal{B}})$ to satisfy the condition
$(v_{\mathcal{A}})_{d}=(v_{\mathcal{B}})_{1}$, the $v_{d}$-th smallest element
of the set ${\mathcal{A}}$ must be the $v_{1}$-th smallest element of the set
${\mathcal{B}}$.

Recall equation (32). We substitute ${\mathcal{I}}$ with
${\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$ in (32) and denote the
resulting functions and values by $T_{v}^{(1)}(.)$ and $T_{v}^{(1)}$,
respectively. Using this notation, we can state that the equation
$\operatorname{\mbox{red}}(W_{n-d+1}\cdots W_{n})=v$ is equivalent to
$W_{n-d+1}\cdots W_{n}\in{\mathcal{I}}_{v}(\operatorname{\mathtt{K}})$.
Moreover, for any $r\in{\mathbb{N}}_{0},$ we have

$\displaystyle\cup_{j=0}^{r}\\{\operatorname{\mbox{con}}_{v}(W_{1}\cdots
W_{n})=j\\}=\cup_{j=0}^{r}\\{W_{1}\cdots W_{n}\in
G_{j}^{v}([\operatorname{\mathtt{K}}]^{n})\\}=\\{T^{(r+1)}_{v}>n\\}.$

Let $f_{r}^{v}([\operatorname{\mathtt{K}}]^{n})$ denote the number of words in
$[\operatorname{\mathtt{K}}]^{n}$ containing at most $r$ order-isomorphic
copies of $v$. We can express this number as the sum of
$g_{j}^{v}([\operatorname{\mathtt{K}}]^{n})$. Hence, we will write

$\displaystyle
f_{r}^{v}([\operatorname{\mathtt{K}}]^{n})=\sum_{j=0}^{r}g_{j}^{v}([\operatorname{\mathtt{K}}]^{n})=\operatorname{\mathtt{K}}^{n}\sum_{j=0}^{r}{\mathbb{P}}(W_{1}\cdots
W_{n}\in
G_{j}^{v}([\operatorname{\mathtt{K}}]^{n}))=\operatorname{\mathtt{K}}^{n}{\mathbb{P}}(T^{(r+1)}_{v}>n).$

Lastly, we present the

###### Proof of Theorem 1.3.

Let us begin by recalling that it is well known that if
$\operatorname{\mathtt{K}}\geq d$, then $T_{v}^{(r)}<\infty$ almost surely and
hence ${\mathbb{E}}(\alpha^{T_{v}^{(r)}})<\infty$. This is due to the fact
that $(W_{n-d+1}\cdots W_{n})_{n\geq d}$ is an irreducible finite Markov chain
on $[\operatorname{\mathtt{K}}]^{d}$, which means that the hitting time of any
nonempty subset of $[\operatorname{\mathtt{K}}]^{d}$ has an exponential tail
and is almost surely finite.

Now, let us inspect the generating functions of the random variables
$T_{r}(v,k)$. To that end, observe that Fubini’s theorem can be utilized to
write

$\displaystyle{\mathbb{E}}(\alpha^{T_{v}^{(r)}})$ $\displaystyle=$
$\displaystyle\int_{0}^{1}{\mathbb{P}}(\alpha^{T_{v}^{(r)}}\geq
x)dx=\sum_{\ell=0}^{\infty}\int_{\alpha^{\ell+1}}^{\alpha^{\ell}}{\mathbb{P}}(\alpha^{T_{v}^{(r)}}\geq
x)dx$ $\displaystyle=$
$\displaystyle\sum_{\ell=0}^{\infty}{\mathbb{P}}(\alpha^{T_{v}^{(r)}}\geq\alpha^{\ell+1})\int_{\alpha^{\ell+1}}^{\alpha^{\ell}}dx=\sum_{\ell=0}^{\infty}{\mathbb{P}}(\alpha^{T_{v}^{(r)}}\geq\alpha^{\ell+1})(\alpha^{\ell}-\alpha^{\ell+1})$
$\displaystyle=$
$\displaystyle\sum_{\ell=0}^{\infty}{\mathbb{P}}(T_{v}^{(r)}\leq\ell+1)(\alpha^{\ell}-\alpha^{\ell+1})=\sum_{\ell=0}^{\infty}\left(1-{\mathbb{P}}(T_{v}^{(r)}>\ell+1)\right)(\alpha^{\ell}-\alpha^{\ell+1})$
$\displaystyle=$ $\displaystyle
1-\frac{1-\alpha}{\alpha}\sum_{\ell=1}^{\infty}{\mathbb{P}}(T_{v}^{(r)}>\ell)\alpha^{\ell}=1-\frac{1-\alpha}{\alpha}\sum_{\ell=1}^{\infty}f_{r-1}^{v}([\operatorname{\mathtt{K}}]^{\ell})\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right)^{\ell}.$

Let us continue by noting that for $\operatorname{\mathtt{K}}\geq d$, we can
express

$\displaystyle{\mathfrak{W}}_{r,k}^{v}\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right)$
$\displaystyle=$
$\displaystyle\sum_{\ell=1}^{\infty}f_{r}^{v}([\operatorname{\mathtt{K}}]^{\ell})\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right)^{\ell}-\sum_{\ell=1}^{\infty}f_{r-1}^{v}([\operatorname{\mathtt{K}}]^{\ell})\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right)^{\ell}$
(35) $\displaystyle=$
$\displaystyle\frac{\alpha}{1-\alpha}\left({\mathbb{E}}(\alpha^{T_{v}^{(r)}})-{\mathbb{E}}(\alpha^{T_{v}^{(r+1)}})\right).$

To complete the argument, we observe that Equation (1) implies that
$R(\alpha,w,k)=R(\alpha,v,k)$ holds true, and this same fact also applies to
all the modified matrices described in the paragraph following Equation (29),
for both the patterns $v$ and $w$. Therefore, by equation (35) and Lemma 3.1,
we have

$\displaystyle{\mathfrak{W}}_{r,\operatorname{\mathtt{K}}}^{v}\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right)$
$\displaystyle=$
$\displaystyle\frac{\alpha}{1-\alpha}\left({\mathbb{E}}(\alpha^{T_{v}^{(r)}})-{\mathbb{E}}(\alpha^{T_{v}^{(r+1)}})\right)$
$\displaystyle=$
$\displaystyle\frac{\alpha}{1-\alpha}\left({\mathbb{E}}(\alpha^{T_{w}^{(r)}})-{\mathbb{E}}(\alpha^{T_{w}^{(r+1)}})\right)={\mathfrak{W}}_{r,\operatorname{\mathtt{K}}}^{w}\left(\frac{\alpha}{\operatorname{\mathtt{K}}}\right),$

which completes the proof. ∎

###  3.2 From words to permutations

This section is devoted to proving that for any two patterns $v$ and $w$ in
${\mathcal{S}}_{d}$, (1) implies that $v$ and $w$ are strongly c-Wilf-
equivalent in permutations. To accomplish this, we rely on a lemma that allows
us to extend the result of Theorem 1.3 to permutations. This lemma was
previously presented in [17] within the context of classical pattern
containment. However, we include it here for completeness, even though the
proof is identical.

######  Lemma 3.2.

Let $v$ be any pattern. Then, for $r\in{\mathbb{N}}_{0},$

$\displaystyle
g_{r}^{v}({\mathcal{S}}_{n})=\sum_{\operatorname{\mathtt{K}}=1}^{n}(-1)^{n-\operatorname{\mathtt{K}}}\binom{n}{\operatorname{\mathtt{K}}}g_{r}^{v}([\operatorname{\mathtt{K}}]^{n}).$
(36)

###### Proof of Theorem 3.2-(a).

We define ${\mathcal{Y}}_{n}({\mathcal{A}})$ as the set of all words of length
$n$ whose distinct set of letters is exactly ${\mathcal{A}}$. Formally,

$\displaystyle{\mathcal{Y}}_{n}({\mathcal{A}}):={\mathcal{A}}^{n}\setminus\left(\cup_{e\in{\mathcal{A}}}{\mathcal{A}}_{e}^{n}\right)\quad\mbox{where}\quad{\mathcal{A}}_{e}:={\mathcal{A}}\setminus\\{e\\}.$

Recall equation (1) and express it using the notation introduced above as
follows:

$\displaystyle{\mathcal{G}}_{r}^{v}({\mathcal{Y}}_{n}({\mathcal{A}}))={\mathcal{G}}_{r}^{v}({\mathcal{A}}^{n})\setminus\left(\cup_{e\in{\mathcal{A}}}{\mathcal{G}}_{r}^{v}({\mathcal{A}}_{e}^{n})\right).$
(37)

Furthermore, for any non-empty subset ${\mathcal{J}}\subset{\mathcal{A}}$, we
have

$\displaystyle\cup_{e\in{\mathcal{J}}}{\mathcal{G}}_{r}^{v}({\mathcal{A}}_{e}^{n})={\mathcal{G}}_{r}^{v}(\cup_{e\in{\mathcal{J}}}{\mathcal{A}}_{e}^{n}),\quad\mbox{and}\quad\cap_{e\in{\mathcal{J}}}{\mathcal{G}}_{r}^{v}({\mathcal{A}}_{e}^{n})=\cap_{e\in{\mathcal{J}}}{\mathcal{G}}_{r}^{v}({\mathcal{A}}_{e}^{n}).$

Using the inclusion-exclusion principle on equation (37), we get:

$\displaystyle
g_{r}^{v}({\mathcal{Y}}_{n}({\mathcal{A}}))=g_{r}^{v}({\mathcal{A}}^{n})-\sum_{{\mathcal{J}}\subset{\mathcal{A}}}(-1)^{n-\\#{\mathcal{J}}}g_{r}^{v}(\cap_{e\in{\mathcal{J}}}{\mathcal{A}}_{e}^{n})$
$\displaystyle=\sum_{{\mathcal{J}}\subset{\mathcal{A}}}(-1)^{\\#{\mathcal{J}}}g_{r}^{v}(({\mathcal{A}}\setminus{\mathcal{J}})^{n}).$

Since $g_{0}^{v}({\mathcal{A}}^{n})=g_{0}^{v}({\mathcal{B}}^{n})$ for any
${\mathcal{A}},{\mathcal{B}}\subset[n]$ where ${\mathcal{A}}$ and
${\mathcal{B}}$ have the same size, we have

$\displaystyle
g_{r}^{v}({\mathcal{Y}}_{n}([a]))=g_{r}^{v}([a]^{n})+\sum_{\operatorname{\mathtt{K}}=1}^{a-1}(-1)^{\operatorname{\mathtt{K}}}\binom{a}{\operatorname{\mathtt{K}}}g_{r}^{v}([a-\operatorname{\mathtt{K}}]^{n}),$

for each $a\in{\mathbb{N}}$. Finally, note that
${\mathcal{Y}}_{n}([n])={\mathcal{S}}_{n}$. This completes the proof of (36).
∎

An immediate consequence of this lemma is the following corollary.

######  Corollary 3.3.

(strongly) c-Wilf-equivalence in words implies (strongly) c-Wilf-equivalence
in permutations.

The result follows from combining Theorem 1.3 with Corollary 3.3.

## Acknowledgement

I would like to express my gratitude to Sergi Elizalde for providing feedback
on an initial draft, and to Ashwin Sah for bringing to my attention the proof
of Elizalde’s conjecture for non-overlapping patterns as presented in [15].

## References

  * [1] M. Bóna, _Combinatorics of Permutations_ , Chapman & Hall/CRC, Boca Raton, Second Edition, 2012.
  * [2] M. Bóna, _Non-overlapping permutation patterns_ , Pure Math. Appl. 22:2 (2011) 99–105.
  * [3] V. Dotsenko, A. Khoroshkin, _Shuﬄe algebras, homology, and consecutive pattern avoidance_ , Algebraic Number Theory 7:3 (2013) 673–700.
  * [4] A. Duane, J. Remmel, _Minimal overlapping patterns in colored permutations_ , Electron. J. Combin. 18:2 (2011) #25.
  * [5] T. Dwyer, S. Elizalde _Wilf equivalence relations for consecutive patterns_ , Adv. in Appl. Math. 99 (2018) 134–157.
  * [6] R. Ehrenborg, S. Kitaev, P. Perry, _A Spectral Approach to Consecutive Pattern-Avoiding Permutations_ , J. of Combinatorics 2:3 (2011) 305–353.
  * [7] S. Elizalde, _Asymptotic enumeration of permutations avoiding generalized patterns_ , Adv. in Appl. Math. 36 (2006) 138–155.
  * [8] S. Elizalde, _The most and the least avoided consecutive patterns_ , Proc. Lond. Math. Soc. 106: 5 (2013) 957–979.
  * [9] S. Elizalde, _A survey of consecutive patterns in permutations_ , in: Recent Trends in Combinatorics, in: IMA Vol. Math. Appl., 159 (2016) 601–618.
  * [10] S. Elizalde, M. Noy, Consecutive patterns in permutations, Adv. in Appl. Math. 30:1–2 (2003) 110–125.
  * [11] S. Elizalde, M. Noy, Clusters, generating functions and asymptotics for consecutive patterns in permutations, Adv. in Appl. Math. 49:3–5 (2012) 351–374.
  * [12] H. Gerber, S. Li, _The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain_ , Stoch. Proc. and their App. 11 (1981) 101–108.
  * [13] S. Kitaev, _Patterns in Permutations and Words_ , Springer, 2011.
  * [14] A. Khoroshkin, B. Shapiro, _Using homological duality in consecutive pattern avoidance_ , Electron. J. Combin. 18:2 (2011) #9.
  * [15] M. Lee, A. Sah, _Constraining strong c-Wilf equivalence using cluster poset asymptotics_ , Adv. in Appl. Math. 103 (2019) 43–57.
  * [16] S. Li, _A martingale approach to the study of occurrence of sequence patterns in repeated experiments_ , The Ann. of Prob. 8 (1980) 1171–1176.
  * [17] T. Mansour, R. Rastegar, _Pattern occurrences in k-ary words revisited: A few new and old observations_ , J. of Comb. Theory, Series A 188 (2022), #105596.
  * [18] T. Mansour, R. Rastegar, A. Roitershtein, _Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations_ , SIAM Journal on Discrete Mathematics 34:2 (2020) 1011–1038.
  * [19] S. Meyn, R. L. Tweedie, _Markov Chains and Stochastic Stability_ , Cambridge University Press, Second Edition, 2009.
  * [20] B. Nakamura, Computational Approaches to Consecutive Pattern Avoidance in Permutations, Pure Math. Appl. (PU.M.A.) 22 (2011) 253–268.
  * [21] G. Perarnau, _A probabilistic approach to consecutive pattern avoiding in permutations_ , J. of Comb. Theory, Series A 120:5 (2013) 998–1011.
  * [22] V. Pozdnyakov, _On Occurrence of Patterns in Markov Chains: Method of Gambling Teams_ , Statistics & Probability Letters 78:16 (2008) 2762–2767.
  * [23] V. Pozdnyakov, J. Steele, _Martingale Methods for Patterns and Scan Statistics_ , In Scan Statistics Methods and Applications (2009) 289–317.
  * [24] R. A. Silverman, _Introductory Complex Analysis_ , Dover Publications, 1972.
  * [25] R. Warlimont, Permutations avoiding consecutive patterns, Ann. Univ. Sci. Budapest. Sect. Comput. 22 (2003) 373–393.
  * [26] K. Zajkowski, _A note on the gambling team method_ , Statistics & Probability Letters 85 (2014) 45–50.