# Asymptotics of self-overlapping permutations

Sergey Kirgizov, Khaydar Nurligareev

► To cite this version:

Sergey Kirgizov, Khaydar Nurligareev. Asymptotics of self-overlapping permutations. Discrete Mathematics, 2025, 348 (5), pp.114400. 10.1016/j.disc.2025.114400. hal-04297210v2

HAL Id: hal-04297210

https://hal.science/hal-04297210v2

Submitted on 27 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Asymptotics of self-overlapping permutations

Sergey KIRGIZOV and Khaydar NURLIGAREEV

LIB, Université de Bourgogne, France

**Abstract**

In this work, we study the concept of self-overlapping permutations, which is related to the larger study of consecutive patterns in permutations. We show that this concept admits a simple and clear geometrical meaning, and prove that a permutation can be represented as a sequence of non-self-overlapping ones. The above structural decomposition allows us to obtain equations for the corresponding generating functions, as well as the complete asymptotic expansions for the probability that a large random permutation is (non-)self-overlapping. In particular, we show that almost all permutations are non-self-overlapping, and that the corresponding asymptotic expansion has the self-reference property: the involved coefficients count non-self-overlapping permutations once again. We also establish complete asymptotic expansions of the distributions of very tight non-self-overlapping patterns, and discuss the similarities of the non-self-overlapping permutations to other permutation building blocks, such as indecomposable and simple permutations, as well as their associated asymptotics.

**Keywords:** asymptotics, permutations, consecutive patterns, overlapping.

# 1 Introduction

The study of *pattern-avoiding permutations* is a dynamically developing area of mathematics that has been exciting scientists since the mid-1980s. The center concept of this study is containment: a permutation $\sigma = \sigma_1\sigma_2\dots\sigma_n$ contains another permutation $\pi = \pi_1\pi_2\dots\pi_k$ as a *pattern* if there exists a subsequence $1 \le i_1 < i_2 < \dots < i_k \le n$ such that for all indices $j$ and $l$ the inequalities $\pi_j < \pi_l$ and $\sigma_{i_j} < \sigma_{i_l}$ are equivalent. If $\sigma$ does not contain $\pi$, then it is said that $\sigma$ *avoids* $\pi$. Since the first systematic enumeration by Simion and Schmidt [28], the interest in permutation patterns has grown steadily, which can be explained by the presence of extensive connections with other mathematical fields. For instance, the theorem of Marcus and Tardos [21] stating that the growth rate of every permutation class avoiding a given pattern is singly exponential relates to words and 0-1 matrices as well.

One of the important variations of the above study concerns the notion of *consecutive patterns*, first systematically treated by Elizalde and Noy [18]. In terms of Bóna [6], we say that a permutation $\sigma = \sigma_1\sigma_2\dots\sigma_n$ *tightly contains* a permutation $\pi = \pi_1\pi_2\dots\pi_k$ if there exists an integer $0 \le i \le n-k$ such that for all indices $j$ and $l$ the inequalities $\pi_j < \pi_l$ and $\sigma_{i_j} < \sigma_{i+l}$ are equivalent. A good overview of the state of this topic for 2016 was provided by Elizalde [17]. To obtain generating functions and distributions of tight pattern occurrences in various combinatorial objects, one can employ the *cluster method* of Goulden and Jackson [19, 20, 25]. As a particular example, we would like to cite the proofs of Elizalde–Noy and Nakamura conjectures [16].

Consecutive patterns can be thought as a restricted version of permutation patterns, where the entries of $\sigma$ that form a pattern must be in consecutive positions. It is natural to take one step further
by forcing these entries to be consecutive themselves. Following Bóna [6], we say that a permutation $\sigma = \sigma_1\sigma_2\dots\sigma_n$ very tightly contains a permutation $\pi = \pi_1\pi_2\dots\pi_k$ if there exist two integers $0 \le i, h \le n-k$ such that $\sigma_{i+j} = \pi_j + h$ for all $1 \le j \le k$. For the first time, these and more general patterns were considered by Myers [23] who called the corresponding type of containment *rigid*. Myers established distributions of non-self-overlapping patterns (see Definition 1.1). With the help of the cluster method, her result was completed by Claesson [9] who also provided joint distributions for any patterns of the same size. Note that Claesson called the patterns under consideration *Hertzsprung*. In the following, we will use the term *very tight pattern* to refer to them.

Understanding the overlaps of combinatorial sub-structures is of core importance in the cluster method. In the case of consecutive patterns, this need is reflected in the concept of non-overlapping permutations [7], also known as minimally overlapping [14, 27]: a permutation of length $k$ is non-overlapping if it is not contained at the same time as a prefix and suffix in any permutation of size $n$ satisfying $k < n < 2k - 1$. In other words, if the intersecting prefix and suffix of a permutation are isomorphic, then they represent an example of overlapping permutation. Here, we call two sequences of distinct integers $\pi = \pi_1\pi_2\dots\pi_k$ and $\tau = \tau_1\tau_2\dots\tau_k$ isomorphic if $\pi_i > \pi_j \Leftrightarrow \tau_i > \tau_j$ for all possible indices $i$ and $j$. For instance, the permutation 132 is non-overlapping, but 1324 is overlapping, since the prefix and suffix of size four of the permutation 132546 form a 1324-pattern. The counting sequence of non-overlapping permutations starts with

$$1, 2, 4, 12, 48, 280, 1864, 14840, 132276, 1323504, \dots,$$

see A263867 entry in Sloane's Encyclopedia [24].

Applying the notion of very tight containment to overlapping permutations, we come to the main object of our interest. This is about the concept of self-overlapping permutations (called *extendible* by Myers [23] and Bóna [6]), which is given by the following definition.

**Definition 1.1.** A permutation $\sigma \in S_n$ is self-overlapping, if there is an integer $1 \le k < n$ called overlapping range such that the following three conditions hold:

1. the interval $\{1, \dots, k\}$ is invariant under $\sigma$,

2. the interval $\{n-k+1, \dots, n\}$ is invariant under $\sigma$,

3. the first and last $k$ consecutive positions of $\sigma$ form isomorphic patterns.

Otherwise, we call $\sigma$ non-self-overlapping. We designate by $\mathfrak{s}_n$ and $\mathfrak{n}_n$, respectively, the numbers of self-overlapping and non-self-overlapping permutations of size $n$.

Here, we use the definition given by Bóna [6]. It has a particular property: if $\sigma = \sigma_1\sigma_2\dots\sigma_n$ is self-overlapping, then $\sigma_1 < \sigma_n$. Sometimes this property is too restrictive, since the reverse $\bar{\sigma} = \sigma_n\sigma_{n-1}\dots\sigma_1$ behaves similarly to $\sigma$ in many senses. This is why both Myers [23] and Claesson [9] understood $\bar{\sigma}$ as a self-overlapping permutation as well.

From a geometric point of view, if a permutation $\sigma \in S_n$ is self-overlapping with an overlapping range $k$, then its plot possesses two congruent blocks of size $k \times k$: one of them is located at the lower left corner, while the other is in the upper right one. For example, the permutation $\sigma = 214365$ is self-overlapping with overlapping ranges $k=2$ and $k=4$ (Figure 1).

Figure 2 illustrates all self-overlapping permutation of size $n \le 4$. Observing these and other examples, the reader may give a guess that a self-overlapping permutation possesses an overlapping range of no more than half its size. In Section 2, we show that this is, indeed, the case (Lemma 2.1). This observation gives rise to a structural decomposition of permutations into direct sums of non-self-overlapping ones (Theorem 2.4). In its turn, the decomposition leads to relations on generating functions (Theorem 2.5), that allows us to establish counting sequences ($\mathfrak{s}_n$) and ($\mathfrak{n}_n$).
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /><figcaption>Figure 1: Overlapping blocks in the permutation 214365.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2: Self-overlapping permutations of size at most 4.</figcaption></figure>

The first few values of the sequence ($\mathfrak{s}_n$) are

$$ \mathfrak{s}_n = 0, 1, 1, 3, 7, 31, 131, 775, 5211, 41315, \dots $$

while the complementary sequence ($\mathfrak{n}_n$) begins with

$$ \mathfrak{n}_n = 1, 1, 5, 21, 113, 689, 4909, 39545, 357669, 3587485, \dots $$

A single glance at these numbers is enough to conjecture that with high probability a typical large permutation is non-self-overlapping. We prove this conjecture at Section 3. Moreover, we establish a complete asymptotic expansion of the probability that a uniform random permutation is self-overlapping (Theorem 3.1). It turns out that the coefficients involved into the expansion admit combinatorial interpretation: they are $\mathfrak{n}_n$ again. Remarkably, this result does not need the advanced techniques typically used to establish combinatorial meaning of asymptotic expansions [22, 26]. The proof follows directly from the above mentioned structural decomposition, supplemented by estimates on the asymptotic behavior of the tails.

In Section 4, we discuss very tight patterns. As we have already mentioned, for the non-self-overlapping case, the distributions of such patterns were established by Myers [23]. Here, based on her results, we present complete asymptotic expansions of these distributions. For the self-overlapping case, the distributions were given by Claesson [9]. Evaluating asymptotics requires advanced methods in this case, such as Borinsky's approach [8], which is beyond the scope of this work. We will provide the full result in our next paper [5].

The established asymptotics raise several questions that we discuss in Section 5.

# 2 Structure and enumeration

**Lemma 2.1.** Any self-overlapping permutation of size $n$ admits an overlapping range of size at most $n/2$.

*Proof.* Suppose that an overlapping range $k$ of a self-overlapping permutation $\sigma \in S_n$ is greater than $n/2$. In this case, the lower left and upper right blocks of size $k \times k$ are congruent and have non-empty intersection. The intersection is a $(2k-n) \times (2k-n)$ block, which is congruent to the lower
left and upper right blocks of the same size. Therefore, $\sigma$ admits overlapping range $(2k - n) < k$. If $(2k - n) < n/2$, we are done. Otherwise, repeat the procedure until the overlapping block sizes are less than $n/2$ (Figure 3). $\square$

<figure><img src="image_5.png" /><figcaption>Figure 3: Schema for reducing an overlapping range. If overlapping blocks have a non-empty intersection (gray areas on the figure), then this intersection can be slid to get smaller overlapping blocks (blue and violet areas).</figcaption></figure>

Recall that the direct sum of permutations $\pi \in S_m$ and $\tau \in S_n$ is the permutation $\pi \oplus \tau$ of length $(m + n)$ defined by

$$ (\pi \oplus \tau)(i) = \begin{cases} \pi(i) & \text{for } 1 \le i \le m, \\ \tau(i - m) + m & \text{for } m + 1 \le i \le n. \end{cases} $$

Lemma 2.1 allows us to decompose self-overlapping permutations into a direct sum of smaller permutations (schematically, the summands are represented by consecutive non-intersecting blocks, see the right part of Figure 3). More precisely, we get the following structural result.

**Lemma 2.2.** Any self-overlapping permutation $\sigma$ can be uniquely decomposed into a direct sum

$$ \sigma = \pi \oplus \tau \oplus \pi, $$

where $\pi$ is non-self-overlapping permutation and $\tau$ is arbitrary (possibly, empty) permutation.

*Proof.* Let $k$ be the minimal overlapping range of $\sigma$. According Lemma 2.1, $k \le n/2$. Hence, $\sigma$ possesses three consecutive invariant intervals: $\{1, \dots, k\}$, $\{k+1, \dots, n-k\}$ and $\{n-k+1, \dots, n\}$ (it may happen that the second of them is empty). This gives us the above decomposition $\sigma = \pi \oplus \tau \oplus \pi$. Note that the permutation $\pi \in S_k$ is non-self-overlapping due to minimality of the overlapping range $k$. Indeed, if $\pi$ is self-overlapping with an overlapping range $l$, then $l < k$ is the overlapping range of $\sigma$ too, which leads to a contradiction (see Figure 4). $\square$

<figure><img src="image_6.png" /><figcaption>Figure 4: Structure of self-overlapping permutations. If the overlapping block $\pi$ is a self-overlapping permutation itself, then its size is not the minimal overlapping range of the permutation $\sigma = \pi \oplus \tau \oplus \pi$.</figcaption></figure>
**Corollary 2.3.** The counting sequence ($\mathfrak{s}_n$) of self-overlapping permutations satisfies

$$ \mathfrak{s}_n = \sum_{k=1}^{\lfloor n/2 \rfloor} \mathfrak{n}_k \cdot (n-2k)! $$

**Theorem 2.4.** Any permutation $\sigma$ can be uniquely decomposed into a direct sum of non-self-overlapping permutations,

$$ \sigma = \pi_1 \oplus \dots \oplus \pi_m \oplus \tau \oplus \pi_m \oplus \dots \oplus \pi_1, \qquad (1) $$

where the permutation $\tau$ is, possibly, empty.

*Proof.* If $\sigma$ is non-self-overlapping, then decomposition (1) is done with $m = 0$ and $\tau = \sigma$. Otherwise, let us apply Lemma 2.2 iteratively. In other words, express $\sigma$ as $\pi_1 \oplus \tau_1 \oplus \pi_1$. If $\tau_1$ is self-overlapping, then express it as $\pi_2 \oplus \tau_2 \oplus \pi_2$, etc. Thus, after a finite number of iterations, we obtain decomposition (1).

Now, let us show the uniqueness of the above decomposition. Suppose the contrary, that is, suppose that we have two different decompositions of form (1):

$$ \pi_1 \oplus \dots \oplus \pi_m \oplus \tau \oplus \pi_m \oplus \dots \oplus \pi_1 = \pi'_1 \oplus \dots \oplus \pi'_{m'} \oplus \tau' \oplus \pi'_{m'} \oplus \dots \oplus \pi'_1. $$

Without loss of generality, we can assume that $\pi_1 \neq \pi'_1$, which means that they are of different sizes, say, $l$ and $l'$. However, if $l < l'$, then $\pi'_1$ is self-overlapping with the overlapping range $l$ (see Figure 5). The case $l' < l$ leads to a similar contradiction. Thus, $\pi_1 = \pi'_1$, and decomposition (1) is unique. $\square$

<figure><img src="image_7.png" /><figcaption>Figure 5: Uniqueness of decomposition (1).</figcaption></figure>

Let us consider the generating functions $S(z)$ and $N(z)$ of self-overlapping and non-self-overlapping permutations, respectively:

$$ S(z) = \sum_{n=1}^{\infty} \mathfrak{s}_n z^n \quad \text{and} \quad N(z) = \sum_{n=1}^{\infty} \mathfrak{n}_n z^n. $$

We formally assume that an empty permutation is neither self-overlapping nor non-self-overlapping. Hence, the generating function $P(z)$ of all permutations can be represented as the following sum:

$$ P(z) = 1 + S(z) + N(z) = \sum_{n=0}^{\infty} n! z^n. \qquad (2) $$

This observation, together with Lemma 2.2, helps us establish relations that determine the behavior of $S(z)$ and $N(z)$.
**Theorem 2.5.** The generating functions $S(z)$ and $N(z)$ satisfy the following relations:

$$N(z) = P(z)(1 - N(z^2)) - 1 \qquad (3)$$

and

$$S(z) = \frac{1 + N(z)}{1 - N(z^2)} \cdot N(z^2). \qquad (4)$$

*Proof.* In terms of generating functions, Lemma 2.2 can be interpreted as the following relation:

$$S(z) = P(z) \cdot N(z^2).$$

At the same time, it follows from (2) that

$$S(z) = P(z) - N(z) - 1.$$

Equating the right-hand sides of these two identities, we obtain relation (3). Meanwhile, to get (4), it is sufficient to take the first of the identities and replace $P(z)$ with the expression obtained via relation (3). □

**Remark 2.6.** Relation (3) rewritten as

$$P(z) = \frac{1 + N(z)}{1 - N(z^2)} \qquad (5)$$

is another face of Theorem 2.4. Indeed, the factor $1+N(z)$ corresponds to the central block of decomposition (1), while $(1-N(z^2))^{-1}$ represents the sequence of non-self-overlapping permutations. Note that the argument $z^2$ reflects the fact that each element of the sequence is taken twice. Relation (4) carries a similar meaning. The only difference is the presence of the additional factor $N(z^2)$ that guarantees that the decomposition consists of at least two blocks.

# 3 Asymptotics

**Theorem 3.1.** For any positive integer $r$, the probability that a uniform random permutation $\sigma \in S_n$ is self-overlapping, as $n \to \infty$, satisfies

$$\mathbb{P}(\sigma \text{ is self-overlapping}) = \sum_{k=1}^{r-1} \frac{\mathfrak{n}_k}{n^{2k}} + O\left(\frac{1}{n^{2r}}\right), \qquad (6)$$

where $n^k = n(n-1)\dots(n-k+1)$ are the falling factorials.

*Proof.* It follows from Corollary 2.3, that the counting sequence of self-overlapping permutations satisfies

$$\mathfrak{s}_n \le \sum_{k=1}^{r-1} \mathfrak{n}_k \cdot (n-2k)! + \sum_{k=r}^{\lfloor n/2 \rfloor} k! \cdot (n-2k)!.$$

Let us estimate the second summand. For $n$ large enough and $r < k \le n/2$, we have

$$k! \cdot (n-2k)! \le (r+1)! \cdot (n-2r-2)!.$$

As a consequence,

$$\sum_{k=r}^{\lfloor n/2 \rfloor} k! \cdot (n-2k)! \le r! \cdot (n-2r)! + (n-r) \cdot (r+1)! \cdot (n-2r-2)! = O((n-2r)!)$$
which leads us to

$$ \mathfrak{s}_n = \sum_{k=1}^{r-1} \mathfrak{n}_k \cdot (n-2k)! + O((n-2r)!) $$

Now, since $P(\sigma$ is self-overlapping) = $\mathfrak{s}_n/n!$, it is sufficient to divide the obtained inequality by $n!$. $\square$

Let $\mathfrak{s}_n^{(m)}$ be the number of permutations of size $n$ whose decomposition (1) consists of $(2m+1)$ summands (in particular, $\mathfrak{s}_n^{(0)} = \mathfrak{n}_n$). Define also $\mathfrak{n}_n^{(m)}$ to be the number of permutations that can be represented as a direct sum of $m$ non-self-overlapping permutations (in particular, $\mathfrak{n}_0^{(0)} = 1$, $\mathfrak{n}_n^{(0)} = 0$ for $n > 0$, and $\mathfrak{n}_n^{(1)} = \mathfrak{n}_n$).

**Theorem 3.2.** For any positive integer $r$, the probability that decomposition (1) of a uniform random permutation $\sigma \in S_n$ consists of $(2m+1)$ summands, as $n \to \infty$, satisfies

$$ P(\sigma \text{ consists of } 2m+1 \text{ blocks}) = \sum_{k=1}^{r-1} \frac{\mathfrak{n}_k^{(m)} - \mathfrak{n}_k^{(m+1)}}{n^{2k}} + O\left(\frac{1}{n^{2r}}\right), \quad (7) $$

where $n^k = n(n-1)\dots(n-k+1)$ are the falling factorials.

*Proof.* Due to Lemma 2.2 and Theorem 2.4, the number of permutations whose decomposition (1) consists of at least $(2m+1)$ summands is equal to

$$ \sum_{k=1}^{\lfloor n/2 \rfloor} \mathfrak{n}_k^{(m)} \cdot (n-2k)! $$

Therefore, the sequence $(\mathfrak{s}_n^{(m)})$ satisfies

$$ \mathfrak{s}_n^{(m)} = \sum_{k=1}^{\lfloor n/2 \rfloor} (\mathfrak{n}_k^{(m)} - \mathfrak{n}_k^{(m+1)}) \cdot (n-2k)! $$

Similarly to the previous theorem, for any tail of this sum, we have an estimation

$$ \sum_{k=r}^{\lfloor n/2 \rfloor} (\mathfrak{n}_k^{(m)} - \mathfrak{n}_k^{(m+1)}) \cdot (n-2k)! = O((n-2r)!) $$

Thus, dividing the above relation by $n!$, we obtain asymptotic expression (7). $\square$

# 4 Asymptotics of pattern distributions

Let $\pi$ be a permutation of size $p$. Denote by $a_{n,m}(\pi)$ the number of permutations of size $n$ with exactly $m$ very tight occurrences of the pattern $\pi$. Assume that both $\pi$ and its reverse $\bar{\pi}$ are non-self-overlapping. In this case, as it was showed by Myers [23], we have

$$ a_{n,m}(\pi) = \sum_{k=m}^{\lfloor n/(p-1) \rfloor} (-1)^{m-k} \binom{k}{m} \binom{n-(p-1)k}{k} (n-(p-1)k)! \quad (8) $$

The goal of this section is to answer the following Myers' question: for a fixed constant $m$, what is the asymptotics of the probability that a pattern $\pi$ very tightly occurs exactly $m$ times in a permutation of size $n$, as $n \to \infty$? A possible answer is given by the following theorem.
**Theorem 4.1.** If $\pi \in S_p$ is such a permutation that both $\pi$ and $\bar{\pi}$ are non-self-overlapping, then for any positive integer $r$, the probability that a uniform random permutation $\sigma \in S_n$ has exactly $m$ very tight occurrences of $\pi$, as $n \to \infty$, satisfies

$$ \mathbb{P}(\pi \text{ very tightly occurs in } \sigma \text{ m times}) = \frac{1}{m!} \sum_{k=m}^{r-1} \frac{(-1)^{k-m}}{(k-m)!} \cdot \frac{(n-(p-1)k)^k}{n^{(p-1)k}} + O\left(\frac{1}{n^{(p-2)r}}\right), \quad (9) $$

where $n^k = n(n-1)\dots(n-k+1)$ are the falling factorials. In particular,

$$ \mathbb{P}(\pi \text{ very tightly occurs in } \sigma \text{ m times}) = \frac{1}{m!} \cdot \frac{1}{n^{(p-2)m}} + O\left(\frac{1}{n^{(p-2)m+1}}\right). $$

*Proof.* Relation (8) implies that

$$ a_{n,m}(\pi) = \frac{1}{m!} \left( \sum_{k=m}^{r-1} \frac{(-1)^{k-m}}{(k-m)!} \cdot d_k(n) + \sum_{k=r}^{\lfloor n/(p-1) \rfloor} \frac{(-1)^{k-m}}{(k-m)!} \cdot d_k(n) \right), $$

where $d_k(n) = (n-(p-1)k)^k \cdot (n-(p-1)k)!$. Clearly, $d_k(n) \le d_{r+1}(n)$ for any $k > r+1$. Therefore,

$$ \sum_{k=r}^{\lfloor n/(p-1) \rfloor} \frac{1}{(k-m)!} \cdot d_k(n) \le \frac{d_r(n)}{(r-m)!} + \frac{d_{r+1}(n)}{(r-m)!} \cdot n = O(d_r(n)). $$

Thus, we obtain

$$ a_{n,m}(\pi) = \frac{1}{m!} \sum_{k=m}^{r-1} \frac{(-1)^{k-m}}{(k-m)!} \cdot d_k(n) + O(d_r(n)), $$

which is sufficient to be divided by $n!$ to get relation (9). $\square$

<figure><img src="image_8.png" /></figure>

In some sense, it would be more natural to have a complete asymptotic expansion of $a_{n,m}(\pi)/n!$ over the basis $1/n^k$, as it is the case for self-overlapping permutations (see relations (6) and (7)). This is indeed possible, which is reflected by the following theorem.

**Theorem 4.2.** If $\pi \in S_p$ is such a permutation that both $\pi$ and $\bar{\pi}$ are non-self-overlapping, then for any positive integer $r$, the probability that a uniform random permutation $\sigma \in S_n$ has exactly $m$ very tight occurrences of $\pi$, as $n \to \infty$, satisfies

$$ \mathbb{P}(\pi \text{ very tightly occurs in } \sigma \text{ m times}) = \sum_{k=(p-2)m}^{r-1} \frac{c_k}{n^k} + O\left(\frac{1}{n^r}\right), \quad (10) $$

where $n^k = n(n-1)\dots(n-k+1)$ are the falling factorials and

$$ c_k = (-1)^m \sum_{i=\lceil k/(p-1) \rceil}^{\lfloor k/(p-2) \rfloor} \binom{i}{m} \frac{(-1)^{(p-1)i-k}}{((p-1)i-k)!} \binom{i}{k-(p-2)i}. $$

**Example 4.3.** If $m=0$, then relation (10) corresponds to the probability that a uniform permutation $\sigma \in S_n$ very tightly avoids a pattern $\pi$. For instance, for $\pi = 132$ this relation reads

$$ \mathbb{P}(\sigma \text{ very tightly avoids } \pi) = 1 - \frac{1}{n} + \frac{3}{2n^2} - \frac{13}{6n^3} + \frac{61}{24n^4} - \frac{441}{120n^5} + \frac{3031}{720n^6} - \frac{28813}{5040n^7} + O\left(\frac{1}{n^8}\right). $$
Before passing to the proof of Theorem 4.2, we need to establish one technical lemma related to the rising and falling factorials, that is

$$n^{\overline{k}} = n(n+1)\dots(n+k-1) \quad \text{and} \quad n^{\underline{k}} = n(n-1)\dots(n-k+1),$$

respectively.

**Lemma 4.4.** For any non-negative integers $n, k$ and $l$,

$$(n-k)^{\overline{l}} = \sum_{i=0}^{l} \frac{(-1)^i}{i!} k^i l^i n^{\overline{l-i}}.$$

*Proof.* Let us apply induction on $l$. The base case holds, since $(n-k)^{\overline{0}} = 1 = n^{\overline{0}}$. Suppose that the statement holds for some arbitrary $l$. Therefore,

$$ \begin{aligned} (n-k)^{\overline{l+1}} &= (n-(k-1))^{\overline{l+1}} - (l+1)(n-(k-1))^{\overline{l}} \\ &= n^{\overline{l+1}} - (l+1) \sum_{s=0}^{k-1} (n-s)^{\overline{l}} \\ &= n^{\overline{l+1}} - (l+1) \sum_{s=0}^{k-1} \sum_{i=0}^{l} \frac{(-1)^i}{i!} s^i l^i n^{\overline{l-i}} \\ &= n^{\overline{l+1}} + \sum_{i=0}^{l} \frac{(-1)^{i+1}}{i!} (l+1)^{\overline{i+1}} n^{\overline{(l+1)-(i+1)}} \sum_{s=0}^{k-1} s^i. \end{aligned} $$

To finish the proof, it is sufficient to note that

$$\sum_{s=0}^{k-1} s^i = \sum_{s=0}^{k-1} \frac{(s+1)^{\overline{i+1}} - s^{\overline{i+1}}}{i+1} = \frac{k^{\overline{i+1}}}{i+1}.$$

<figure><img src="image_9.png" /></figure>

*Proof of Theorem 4.2.* The main idea is to take expression (9) and rewrite it with the help of Lemma 4.4. For simplicity, let us denote $N = n - (p-1)k + 1$. Thus, Lemma 4.4 applied to $l=k$ gives us

$$\frac{(n - (p-1)k)^{\underline{k}}}{n^{\overline{(p-1)k}}} = \frac{(N - k)^{\overline{k}}}{N^{\overline{(p-1)k}}} = \sum_{i=0}^{k} \frac{(-1)^i (k^i)^2 N^{\overline{k-i}}}{i! \cdot N^{\overline{(p-1)k}}} = \sum_{i=0}^{k} \binom{k}{i} \frac{(-1)^i k^i}{(N + k - i)^{\overline{(p-2)k+i}}}.$$

Taking into account that $(N + k - i)^{\overline{(p-2)k+i}} = n^{\overline{(p-2)k+i}}$, we can rewrite expression (9) as

$$\mathbb{P}(\pi \text{ very tightly occurs in } \sigma \text{ m times}) = \sum_{k=m}^{r-1} a_k \sum_{i=0}^{k} b_{k,i} e_{(p-2)k+i} + O\left(\frac{1}{n^{(p-2)r}}\right), \quad (11)$$

where

$$a_k = (-1)^m \binom{k}{m}, \quad b_{k,i} = \frac{(-1)^{k-i}}{(k-i)!} \binom{k}{i}, \quad e_k = \frac{1}{n^{\underline{k}}}.$$
Now, reverse the summation order in the right hand side of relation (11). Designating $s = (p-2)k+i$, we have

$$ \begin{aligned} \sum_{k=m}^{\infty} a_k \sum_{i=0}^{\infty} b_{k,i} \mathbf{1}_{i \le k} e_{(p-2)k+i} &= \sum_{k=m}^{\infty} a_k \sum_{s=(p-2)k}^{\infty} b_{k,s-(p-2)k} \mathbf{1}_{s \le (p-1)k} e_s \\ &= \sum_{s=(p-2)m}^{\infty} e_s \sum_{k=\lceil s/(p-1) \rceil}^{\lfloor s/(p-2) \rfloor} a_k b_{k,s-(p-2)k}, \end{aligned} $$

where $\mathbf{1}$ is the indicator function. Substituting $e_s$, $a_k$ and $b_{k,s-(p-2)k}$ leads to the desired form of the asymptotics. $\square$

# 5 Conclusion

As we have seen in Section 2, each permutation can be represented as a direct sum of non-self-overlapping ones. Therefore, we can consider non-self-overlapping permutations as a sort of basic irreducible blocks that can serve for constructing the whole class of permutations. There are other examples of this kind in the literature related to permutations. One of them concerns so called indecomposable permutations, that is, permutations with no proper invariant interval of the form $\{1, \dots, k\}$ (see, for example, the paper of Cori [11]). It is known that each permutation can be represented as a sequence of indecomposable ones. In particular, the generating function $I(z)$ of indecomposable permutations satisfies

$$ I(z) = 1 - \frac{1}{P(z)}. $$

In the class of permutations, the non-self-overlapping ones form the majority. In other words, almost all permutations are non-self-overlapping. The same is true for indecomposable permutations. Moreover, this analogy can be extended to complete asymptotic expansions. It was Comtet [10] who first studied the probability that a large permutation is indecomposable, and established its expansion over the basis $1/n^k$. Later, it turned out that the involved coefficients have combinatorial meaning. More precisely, the following result was recently shown [26]: for any positive integer $r$, the probability that a uniform random permutation $\sigma \in S_n$ is indecomposable satisfies

$$ \mathbb{P}(\sigma \text{ is indecomposable}) = 1 - \sum_{k=1}^{r-1} \frac{2\mathbf{i}_k - \mathbf{i}_k^{(2)}}{n^k} + O\left(\frac{1}{n^r}\right), \quad (12) $$

where $(\mathbf{i}_k)$ is the counting sequence of indecomposable permutations, and $(\mathbf{i}_k^{(2)})$ counts permutations with exactly two indecomposable parts. From Theorem 3.1, we can see that the asymptotic expansion of the probability that a uniform random permutation is non-self-overlapping has the same spirit:

$$ \mathbb{P}(\sigma \text{ is non-self-overlapping}) = 1 - \sum_{k=1}^{r-1} \frac{\mathfrak{n}_k}{n^{2k}} + O\left(\frac{1}{n^{2r}}\right). \quad (13) $$

Another example of irreducibilities involves simple permutations that do not map non-trivial intervals onto intervals (see [2]). The generating function $M(z)$ of simple permutations of size at least 4 can be found iteratively from the equation

$$ \frac{P(z) - P^2(z)}{1 + P(z)} = z + M(P(z)). $$
The asymptotic expansion of the probability that a uniform random permutation $\sigma \in S_n$ is simple was established by Borinsky [8]:

$$ \mathbb{P}(\sigma \text{ is simple}) = \frac{1}{e^2} \left( 1 - \frac{4}{n} + \frac{2}{n^2} - \frac{40}{3n^3} - \frac{182}{3n^4} - \dots \right). \qquad (14) $$

Again, we observe the role of the basis $1/n^k$. However, compared to the cases related to non-self-overlapping and indecomposable permutations, this expansion has two important differences. First, the leading term is not 1 anymore: the proportion of simple permutations tends to $e^{-2}$. Second, the involved coefficients are not integers anymore.

These observations raise a number of questions. First of all, it would be of interest to unite the three above discussed permutation classes under the same theory that could explain both the similarities and differences. Relations (7) and (10) could also fit into this theory if we added the ability to account for various statistics. A priori, this question is quite complicated. It would be natural to try employing the *wreath product* introduced by Atkinson and Stitt [3] for studying restricted permutations. Indeed, constructing the class of permutations from the simple ones admits description in terms of the wreath product [1]; that is true for indecomposable permutations as well. However, it looks like the non-self-overlapping permutations do not allow such a description.

Another question is the following: is it possible to naturally modify the basis in asymptotics (14), so that the coefficients become integers? At first glance, it seems that it could be sufficient to divide the basis vectors $1/n^k$ by $k!$. This change suggests switching from the ordinary generating functions to the exponential ones. That trick works well for establishing complete asymptotic expansions of indecomposable permutations and indecomposable perfect matchings, see [26, Chapter 9]. The potential of its applicability for simple permutations needs to be verified.

Finally, if we get a positive answer to the previous question, what is the combinatorial interpretation of these coefficients? Unfortunately, there is no clue in the OEIS [24]. The only thing one can be sure of is that the coefficients cannot be interpreted as a counting sequence of combinatorial class: some of them are negative. Thus, we would rather expect linear combinations of different counting sequences, as is the case for indecomposable permutations (12).

In addition, there are various questions about patterns in permutations and other structures. Thus, one may wonder if it is possible to extend Theorems 4.1 and 4.2 to any very tight pattern. We will address this problem and propose a solution in our next paper [5]. We will also show that this kind of permutation patterns can be treated similarly to the special family of matching patterns that we call *endhered*. Studying endhered patterns in matchings were originally motivated by their relations to distributions of special kind of patterns in RNA secondary structures with allowed pseudoknots, modelled as fixed-point free involutions [4]. However, it turns out that endhered patterns are also of independent interest, since their asymptotic behavior is somewhat similar to that of very tight permutation patterns.

A much more ambitious goal would be to study patterns and their asymptotics in graphs. This problem is very hard in its generality. A possible approach would be to start with so-called *ordered graphs* [15]. On the one hand, they can be considered as a generalization of matchings, which potentially allows to employ ideas that are useful for treating matchings. On the other hand, we anticipate the need for advances techniques for both enumeration and asymptotic analysis. This may include, but is not limited to, tools such as graphic generating functions for enumeration [12] and coefficient generating functions for asymptotics [13].

# 6 Acknowledgements

Authors were partially supported by the grant ANR-22-CE48-0002 funded by l'Agence Nationale de la Recherche and the project ANER ARTICO funded by Bourgogne-Franche-Comté region (France).
References

[1] M. H. Albert and M. D. Atkinson. Simple permutations and pattern restricted permutations. *Discrete Math.*, 300(1-3):1-15, 2005.

[2] M. H. Albert, M. D. Atkinson, and M. Klazar. The enumeration of simple permutations. *J. Integer Seq.*, 6(4):art. 03.4.4, 18, 2003.

[3] M. D. Atkinson and T. Stitt. Restricted permutations and the wreath product. *Discrete Math.*, 259(1-3):19-36, 2002.

[4] C. Biane, G. Hampikian, S. Kirgizov, and K. Nurligareev. Endhered patterns in matchings and RNA, 2024. arXiv preprint https://arxiv.org/abs/2404.18802.

[5] C. Biane, S. Kirgizov, and K. Nurligareev. Clusters of endhered patterns in permutations and matchings. In preparation.

[6] M. Bóna. On three different notions of monotone subsequences. In *Permutation patterns. Proceedings of the 5th conference held at the University of St. Andrews, Scotland, June 11-15, 2007*, pages 89-114. Cambridge: Cambridge University Press, 2010.

[7] M. Bóna. Non-overlapping permutation patterns. *Pure Math. Appl. (PU.M.A.)*, 22(2):99-105, 2011.

[8] M. Borinsky. Generating asymptotics for factorially divergent sequences. *Electron. J. Comb.*, 25(4):p4.1, 32, 2018.

[9] A. Claesson. From Hertzsprung's problem to pattern-rewriting systems. *Algebr. Comb.*, 5(6):1257-1277, 2022.

[10] L. Comtet. Sur les coefficients de l'inverse de la série formelle $\sum n!t^n$. *C. R. Acad. Sci., Paris, Sér. A*, 275:569-572, 1972.

[11] R. Cori. Indecomposable permutations, hypermaps and labeled Dyck paths. *J. Comb. Theory, Ser. A*, 116(8):1326-1343, 2009.

[12] S. Dovgal and É. de Panafieu. Symbolic method and directed graph enumeration. *Acta Math. Univ. Comenian. (N.S.)*, 88(3):989-996, 2019.

[13] S. Dovgal and K. Nurligareev. Asymptotics for graphically divergent series: dense digraphs and 2-sat formulae, 2023. arXiv preprint https://arxiv.org/abs/2310.05282.

[14] A. Duane and J. Remmel. Minimal overlapping patterns in colored permutations. *Electron. J. Comb.*, 18(2):research paper p25, 38, 2011.

[15] G. Ducoffe, L. Feuilloley, M. Habib, and F. Pitois. Pattern detection in ordered graphs, 2023. arXiv preprint https://arxiv.org/abs/2302.11619.

[16] S. Elizalde. The most and the least avoided consecutive patterns. *Proc. Lond. Math. Soc.*, 106(5):957-979, 2013.

[17] S. Elizalde. A survey of consecutive patterns in permutations. In *Recent trends in combinatorics*, pages 601-618. Cham: Springer, 2016.
[18] S. Elizalde and M. Noy. Consecutive patterns in permutations. *Adv. Appl. Math.*, 30(1-2):110-125, 2003.

[19] I. P. Goulden and D. M. Jackson. An inversion theorem for cluster decompositions of sequences with distinguished subsequences. *J. Lond. Math. Soc., II. Ser.*, pages 567-576, 1979.

[20] I. P. Goulden and D. M. Jackson. *Combinatorial enumeration*. Courier Corporation, 2004.

[21] A. Marcus and G. Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. *J. Comb. Theory, Ser. A*, 107(1):153-160, 2004.

[22] T. Monteil and K. Nurligareev. Asymptotic probability for connectedness, 2024. arXiv preprint https://arxiv.org/abs/2401.00818.

[23] A. N. Myers. Counting permutations by their rigid patterns. *J. Comb. Theory, Ser. A*, 99(2):345-357, 2002.

[24] N. J. A. Sloane and The OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2024. Published electronically at https://oeis.org.

[25] J. Noonan and D. Zeilberger. The Goulden-Jackson cluster method: extensions, applications and implementations. *J. Difference Equ. Appl.*, 5(4-5):355-377, 1999.

[26] K. Nurligareev. *Irreducibility of combinatorial objects: asymptotic probability and interpretation*. PhD thesis, University Paris 13, 2022. Thèse de doctorat dirigée par Thierry Monteil et Lionel Pournin, Informatique, Université Paris 13.

[27] R. Pan and J. B. Remmel. Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays. *Discrete Math. Theor. Comput. Sci.*, 18(2):13, 2016. Id/No 6.

[28] R. Simion and F. W. Schmidt. Restricted permutations. *Eur. J. Comb.*, 6(4):383-406, 1985.