2. Preliminaries

Let n be a positive integer and let $[n] = \{1,2,\ldots,n\}$. An endofunction of size n is a map $x:[n]\mapsto [n]$, which is represented as the word $x = x_1x_2\cdots x_n$ with $x_i = x(i)$. In this paper, given a set E with elements equipped with a notion of size, we will denote E_n the set of elements in E that have size n. Conversely, given a definition of E_n (elements of size n), we let $E = \bigcup_{n\geq 0}E_n$. For example, let $\text{End}_n$ be the set of endofunctions of size n and let $\text{End} = \bigcup_{n\geq 0}\text{End}_n$.

Given an endofunction $x = x_1x_2\cdots x_n$, we call i ( $2\leq i\leq n$) an ascent (resp., a descent) of x if $x_{i-1} \lt x_i $ (resp., $x_{i-1} \gt x_i$). We always designate 1 as an ascent of x if x is non-empty. Let $\text{Asc}(x)$ denote the set of ascents and let $\text{asc}(x) = |\text{Asc}(x)|$. We call an endofunction x an ascent sequence if $1 \leq x_i \leq \mathrm{asc}(x_1x_2\cdots x_{i-1})+1$ for all $1 \leq i \leq n$. Let $\mathcal{A}_n$ denote the set of ascent sequences of length n. For example, we have $\mathcal{A}_3=\{111,112,121,122,123\}$.

Let x be an ascent sequence in $\mathcal{A}_n$. Suppose that $\text{Asc}(x)=\{a_1,a_2,\ldots,a_k\}$ with $a_1 \lt a_2 \lt \cdots \lt a_k$. The modified ascent sequence of x, denoted by $\hat{x}$, is defined by the following procedure:

for $i=a_1,a_2,\ldots,a_k$ do

for $j=1,2,\ldots, i-1$ do

if $x_j\geq x_{i}$ then $x_j:=x_j+1$.

This map is commonly referred to as the hat map. For example, let x = 123112313. We have $\text{Asc}(x)=\{1,2,3,6,7,9\}$ and $\hat{x}=156112413$. Let $\hat{\mathcal{A}}_n$ denote the set of modified ascent sequences of length n. That is, $\hat{\mathcal{A}}_n = \{\hat{x} \mid x \in \mathcal{A}_n\}$. Note that the construction of the hat map can be easily inverted since $\text{Asc}(x) = \text{Asc}(\hat{x})$. Hence, the hat map is a bijection between $\mathcal{A}_n$ and $\hat{\mathcal{A}}_n$.

Let $x = x_1x_2\cdots x_n$ be an endofunction and let $1\leq \ell\leq 1+ \text{max}\, x$. Define $y = \text{Add}(x,\ell)$ to be the endofunction of length n + 1 depending on whether $\ell \gt x_n$:

• • If $1\leq \ell \leq x_n$, we have $y = x\ell$. Here $x\ell$ is the concatenation of x and $\ell$.

• • If $x_n \lt \ell\leq 1+ \text{max}\, x$, we have $y(n+1) = \ell$ and for $1\leq i \leq n$,

  \begin{equation*}y(i)= \begin{cases} x_i, \quad &\text{if } x_i \lt \ell, \\ x_i +1, \quad&\text{if } x_i \geq \ell. \end{cases}\end{equation*}

Note that any prefix of an ascent sequence is also an ascent sequence. This leads to a recursive definition [Reference Bousquet-Mélou, Claesson, Dukes and Kitaev1] of modified ascent sequences from the hat map as follows. There is exactly one modified ascent sequence of length zero and one, that is, $\hat{\mathcal{A}}_0 = \{\epsilon\}$ and $\hat{\mathcal{A}}_1 = \{1\}$. For $n\geq 1$, every $y = y_1y_2\cdots y_{n+1} \in \hat{\mathcal{A}}_{n+1}$ can be constructed uniquely from some $x \in \hat{\mathcal{A}}_{n}$ by letting $y = \text{Add}(x,y_{n+1})$. Conversely, given $x\in \hat{\mathcal{A}}_{n}$ and $1\leq \ell \leq 1+\max x$, we can construct a unique modified ascent sequence y by letting $y = \text{Add}(x,\ell)$. Therefore, each modified ascent sequence $x \in \hat{\mathcal{A}}_n$ can generate $1+ \text{max} \, x$ modified ascent sequences of length n + 1.

A Cayley permutation is an endofunction $x:[n]\mapsto [n]$ such that $\text{Im}(x) = [k]$ for some $k\leq n$. Here $\text{Im}(x):=\{x_i:1\leq i\leq n\}$ is the set of all images of x. Let $\text{Cay}_n$ denote the set of Cayler permutations of length n. Very recently, Claesson and Cerbai [Reference Cerbai and Claesson5] showed that

\begin{equation*}\hat{\mathcal{A}}_n = \{x\in \text{Cay}_n \mid \text{Asc}(x) = \text{nub}(x)\},\end{equation*}

where

\begin{equation*}\text{nub}(x) = \{\text{min} \,x^{-1}(i) \mid i \in \mathrm{Im}(x)\}. \end{equation*}

For example, for x = 156112413, we have $\text{Asc}(x) = \text{nub}(x) = \{1,2,3,6,7,9\}$, thereby x is a modified ascent sequence. This alternative description takes the mystery out of modified ascent sequences, which we shall use frequently in the paper. From the definition of modified ascent sequence, it is straightforward to verify that each non-empty modified ascent sequence starts with 1.

Let $x = x_1x_2\cdots x_n$ and $\sigma= \sigma_1\sigma_2\cdots \sigma_k$ be two endofunctions with $k\leq n$. An occurrence of σ in x is a subsequence $x_{i_1}x_{i_2}\cdots x_{i_k}$ which is order isomorphic to σ. Here, order isomorphic means $x_{i_s} \lt x_{i_t}$ if and only if $\sigma_s \lt \sigma_t$ and $x_{i_s} = x_{i_t}$ if and only if $\sigma_s = \sigma_t$. We say x contains the pattern σ if x contains an occurrence of σ. Otherwise, we say x avoids the pattern σ or x is σ-avoiding. For example, the modified ascent sequence x = 156112413 contains three occurrences of the pattern 1342, namely, the subsequences 1562, 1564, and 1563, but avoids the pattern 1234. Let $\text{End}_n(\sigma)$ denote the set of endofunctions in $\text{End}_n$ that avoid the pattern σ. We will keep this notation when $\text{End}_n$ is replaced by its subsets such as $\mathcal{A}_n$ and $\hat{\mathcal{A}}_n$, etc.

Given an endofunction $x = x_1x_2\cdots x_n$, we say x is primitive if it contains no flat steps, where a flat step means two consecutive equal entries $x_i = x_{i+1}$. For instance, the endofunction x = 156112413 is not primitive since it contains a flat step 11 while 15612413 which is obtained from x by removing one copy of 1 in the flat step 11 is primitive. More generally, given any endofunction x, it corresponds to a unique primitive endofunction which is obtained from x by merging each the consecutive flat step of x into one single copy. Conversely, any endofunction can be uniquely obtained from a primitive one by inserting flat steps. If σ is a primitive pattern and x avoids σ, then any insertion of flat steps in x does not create any new occurrence of σ. Let $\text{End}_n^{\text{pr}}$ denote the set of primitive endofunctions of length n. We will also keep this notation when $\text{End}_n$ is replaced by its subsets. For example, $\hat{\mathcal{A}}_n^{\text{pr}}$ is the set of primitive modified ascent sequences of length n. Let

\begin{equation*}\hat{\mathcal{A}}_{\sigma}(t) = \sum_{n\geq 0}|\hat{\mathcal{A}}_n(\sigma)|t^n \quad \text{and}\quad \hat{\mathcal{A}}^{\text{pr}}_{\sigma}(t) = \sum_{n\geq 0}|\hat{\mathcal{A}}^{\text{pr}}_n(\sigma)|t^n\end{equation*}

be the generating functions of $\hat{\mathcal{A}}_n(\sigma)$ and $\hat{\mathcal{A}}^{\mathrm{pr}}_n(\sigma)$, respectively. Based on the above reasoning, Cerbai [Reference Cerbai2] obtained the following relation between $\hat{\mathcal{A}}_n(\sigma)$ and $\hat{\mathcal{A}}^{\mathrm{pr}}_n(\sigma)$.

Proposition 2.1. Cerbai

Let σ be a primitive Cayley permutation. Then for $n\geq 0$,

\begin{equation*}|\hat{\mathcal{A}}_{n+1}(\sigma)| = \sum_{i=0}^{n}\binom{n}{i}|\hat{\mathcal{A}}^{\mathrm{pr}}_{i+1}(\sigma)|.\end{equation*}

Equivalently,

\begin{equation*}\hat{\mathcal{A}}_{\sigma}(t) = \hat{\mathcal{A}}^{\mathrm{pr}}_{\sigma}\left(\frac{t}{1-t}\right).\end{equation*}

Let x be a sequence of positive integers. The standardization of x, denoted by $\mathrm{st}(x)$, is defined to be the sequence which is obtained from x by relabeling the sequence according to their relative order. More specifically, the smallest integers in x are replaced with 1, the next smallest with 2, and so forth. For example, given x = 1681981353, we have $\mathrm{st}(x) = 1451651232$. We end this section with some obvious but useful observations, which we omit the proofs.

3. Patterns 1324 and 1342

In this section, we concentrate on the enumeration of modified ascent sequences that avoid the pattern 1324 or 1342. Since both the patterns 1324 and 1342 are primitive, owing to proposition 2.1, it is sufficient to consider their primitive cases.

3.1. Pattern 1324

Let $\hat{\mathcal{A}}_{n,=2}^{\mathrm{pr}}(1324)$ and $\hat{\mathcal{A}}_{n,\neq 2}^{\mathrm{pr}}(1324)$ denote the set of primitive modified ascent sequences in $\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)$ that end in a 2 and that do not end in a 2, respectively. Then we have the following lemma.

Lemma 3.1. For $n \geq 1$, we have

\begin{equation*} |\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)| = |\hat{\mathcal{A}}_{n,=2}^{\mathrm{pr}}(1324)| + |\hat{\mathcal{A}}_{n+1,=2}^{\mathrm{pr}}(1324)|. \end{equation*}

Proof. Each modified ascent sequence either ends in a 2 or does not end in a 2, which leads to $|\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)| = |\hat{\mathcal{A}}_{n,=2}^{\mathrm{pr}}(1324)| + |\hat{\mathcal{A}}_{n,\neq 2}^{\mathrm{pr}}(1324)|$. To complete the proof, it suffices to show that $|\hat{\mathcal{A}}_{n,\neq 2}^{\mathrm{pr}}(1324)| = |\hat{\mathcal{A}}_{n+1,= 2}^{\mathrm{pr}}(1324)|$. Given a modified ascent sequence $x \in \hat{\mathcal{A}}_{n}$ with $x(n) \neq 2$, It is easily seen that x is primitive if and only if $\mathrm{Add}(x,2)$ is primitive. On the other hand, by the construction of Add, $\mathrm{Add}(x,2)$ avoids 1324 if and only if x avoids 1324. Hence the map $\mathrm{Add}(x,2)$ induces a bijection between $\hat{\mathcal{A}}_{n,\neq 2}^{\mathrm{pr}}(1324)$ and $\hat{\mathcal{A}}_{n+1,= 2}^{\mathrm{pr}}(1324)$. It yields that $|\hat{\mathcal{A}}_{n,\neq 2}^{\mathrm{pr}}(1324)| = |\hat{\mathcal{A}}_{n+1,= 2}^{\mathrm{pr}}(1324)|$, as desired.

Let $n \geq 2$ and $x \in \hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)$. It is obvious that x contains at least one copy of 2. Then x can be decomposed uniquely as $x = 1L2R$ according to the rightmost 2 of x.

Lemma 3.2. Given $n\geq 2$, let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)$ with the above decomposition as $x = 1L2R$. Then for any entry a > 2 in L and b > 2 in R, we have a > b.

Proof. If there is some a > 2 in L and some b > 2 in R such that $a \leq b$, we consider two cases. If a < b, then $1a2b$ is an occurrence of the pattern 1324, a contradiction to the fact that x is 1324-avoiding. If a = b, then by lemma 2.2, b is preceded by a larger entry in x, say c. Thus $1a2c$ is an occurrence of the pattern 1324 in x, a contradiction. This completes the proof.

Given $n\geq 0$, let $f_n = |\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)|$. We have the following recurrence for f_n.

Lemma 3.3. For $n \geq 2$, we have

(3.1)\begin{equation} f_n = \sum_{k\geq 1}^{n-1}f_kf_{n-k}, \end{equation}

with the initial value $f_1 = 1$.

Proof. It is clear that $f_1 = 1$. Given $n\geq 2$, let x be a primitive modified ascent sequence in $\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)$ with the above decomposition as $x = 1L2R$. Let $L' = \mathrm{st}(1L2)$ and let $R' = \mathrm{st}(R)$ if R starts with the entry 1 or else let $R' = \mathrm{st}(1R)$. Let k be the length of Lʹ. From lemma 2.4 we immediately obtain that $L' \in \hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)$.

Next we consider Rʹ. If k = n, then $R = \epsilon$ and $R' = 1$. If k < n, we claim that $R' \in \hat{\mathcal{A}}^{\mathrm{pr}}(1324)$. Indeed, by lemma 3.2, we have $\mathrm{Asc}(R) = \mathrm{nub}(R)$ if R starts with 1. Then by lemma 2.3, we have $R' \in \hat{\mathcal{A}}_{n-k}^{\mathrm{pr}}(1324)$. If R does not start with 1, then $\mathrm{Asc}(1R) = \mathrm{nub}(1R)$. The insertion of 1 will not create a new 1324 occurrence $x_{i_1}x_{i_2}x_{i_3}x_{i_4}$ in R. Otherwise, replacing $x_{i_1}$ with the leftmost 1 of x in $x_{i_1}x_{i_2}x_{i_3}x_{i_4}$ will form an occurrence of 1324 in x, a contradiction. Hence, We obtain $R' \in \hat{\mathcal{A}}_{n+1-k}^{\mathrm{pr}}(1324)$ from lemma 2.3. This proves the claim.

To conclude, we have $|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)|$ ways to choose Lʹ and $f_{n-k} + f_{n+1-k}$ ways to choose Rʹ if k < n. Conversely, given $L' \in \hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)$ and $R' \in \hat{\mathcal{A}}_{n-k}^{\mathrm{pr}}(1324)$ or $R' \in \hat{\mathcal{A}}_{n+1-k}^{\mathrm{pr}}(1324)|$ with k < n, one can easily recover the unique primitive modified ascent sequence $x \in \hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)$ from lemma 3.2. Therefore,

\begin{equation*} \begin{array}{llll} f_n &= \sum\limits_{k \geq 2}^{n-1}|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)|(f_{n-k}+f_{n+1-k}) + |\hat{\mathcal{A}}_{n,=2}^{\mathrm{pr}}(1324)|\\ &= \sum\limits_{k \geq 2}^{n-1}|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)|f_{n-k}+ \sum\limits_{k \geq 2}^{n-1}|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)|f_{n+1-k} + |\hat{\mathcal{A}}_{n,=2}^{\mathrm{pr}}(1324)| \\ &= \sum\limits_{k \geq 1}^{n-1}|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)|f_{n-k}+ \sum\limits_{k \geq 1}^{n-1}|\hat{\mathcal{A}}_{k+1,=2}^{\mathrm{pr}}(1324)|f_{n-k}\\ &\quad \quad (\mbox{by the fact } |\hat{\mathcal{A}}_{1,=2}^{\mathrm{pr}}(1324)| = 0 \mbox{and } f_1= 1)\\ &= \sum\limits_{k \geq 1}^{n-1}(|\hat{\mathcal{A}}_{k,=2}^{\mathrm{pr}}(1324)| +|\hat{\mathcal{A}}_{k+1,=2}^{\mathrm{pr}}(1324)| )f_{n-k}\\ &= \sum\limits_{k\geq 1}^{n-1}f_kf_{n-k} \quad (\mbox{by lemma 3.1}), \end{array} \end{equation*}

as desired.

The following theorem follows easily from lemma 3.3 and proposition 2.1.

Theorem 3.4. Let $c(t) := \sum_{n\geq0}c_nt^n=\frac{1 - \sqrt{1 - 4t}}{2t}$ be the generating function for the Catalan numbers c_n. Then,

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1324}(t) = \sum_{n\geq 0}f_nt^n = 1 + tc(t).\end{equation*}

Therefore, $|\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)|=c_{n-1}$ and

\begin{equation*}|\hat{\mathcal{A}}_{n+1}(1324)| = \sum_{i=0}^{n}\binom{n}{i}c_i,\end{equation*}

which is the binomial transformation of Catalan numbers.

Theorem 3.4 confirms a conjecture posed by Cerbai [Reference Cerbai2]. Let

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1324,=2}(t) = \sum\limits_{n\geq 1}|\hat{\mathcal{A}}^{\mathrm{pr}}_{n,=2}(1324)|t^n.\end{equation*}

By lemma 3.1, we obtain

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1324}(t) = 1+(1+\frac{1}{t})\hat{\mathcal{A}}^{\mathrm{pr}}_{1324,=2}(t), \end{equation*}

which implies

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1324,=2}(t) = \frac{t^2}{1+t}c(t) = t^2+2t^4+3t^5+11t^6+31t^7+101t^8+\cdots.\end{equation*}

This indeed represents the absolute value of the alternating sum of the Catalan numbers; see [18, A032357].

3.2. Pattern 1342

Given a primitive modified ascent sequence x with $\mathrm{max}\, x = m$, we assert that m occurs exactly once in x. Otherwise, if m appears more than once, then by lemma 2.2, the second copy of m would be preceded by a number greater than m in x, thereby conflicting with the assertion that m is the maximum value. This enables us to decompose x uniquely as $x = 1LmR$.

Lemma 3.5. Given $n\geq 2$, let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$ with the above decomposition as $x = 1LmR$. Then for any entry $a\geq 2$ in L and $b\geq 2$ in R, we have $a\leq b$.

Proof. If there is some $a\geq 2$ in L and some $b\geq 2$ in R such that a > b, we have a < m and b < m since m is the unique maximum value in x. Hence 1amb is an occurrence of 1342 in x, a contradiction to the fact that x is 1342-avoiding.

Let $g_n = |\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)|$. The following lemma shows that g_n shares the same recurrence (3.1) as $|\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1324)|$.

Lemma 3.6. For $n \geq 2$, we have

(3.2)\begin{equation} g_n = \sum_{k\geq 1}^{n-1}g_kg_{n-k}, \end{equation}

with the initial value $ g_1 = 1$.

Proof. Given $n\geq 3$, let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$ with the decomposition $x = 1LmR$, where m is the unique maximum value in x. Let k be the length of L. From lemma 3.5 we see that $1L \in \hat{\mathcal{A}}_{k+1}^{\mathrm{pr}}(1342)$. Now, there are exactly three possibilities to be considered.

Case 1. k = 0. In this case, L is empty and R is non-empty as $n \geq 3$. Recall that $\mathrm{Asc}(x) = \mathrm{nub}(x)$ since x is a modified ascent sequence. This implies that the first entry of R is 1. Moreover, one can check that $\mathrm{Asc}(R) = \mathrm{nub}(R)$. Then by lemma 2.3, we have $R\in\hat{\mathcal{A}}_{n-2}^{\mathrm{pr}}(1342)$, namely, there are $g_{n-2}$ such primitive modified ascent sequences in $\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$ satisfying that L is empty.

Case 2. $k = n-2$. In this case, we have R is empty and L is non-empty. Notice that $1L \in \hat{\mathcal{A}}_{n-1}^{\mathrm{pr}}(1342)$. There are $g_{n-1}$ such primitive modified ascent sequences in $\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$ satisfying tht R is empty.

Case 3. $1\leq k\leq n-3$. Both L and R are non-empty in this case. It is known that there are $g_{k+1}$ choices for L. Now we consider R. There are two cases depending on whether R contains the number mʹ, where $m'= \mathrm{max}\,L$.

• • If R does not contain mʹ, let $R' = \mathrm{st}(R)$. By lemma 3.5 and the fact $\mathrm{Asc}(x) = \mathrm{nub}(x)$, we deduce that R starts with 1 and furthermore $\mathrm{Asc}(R) = \mathrm{nub}(R)$. Then $R' \in \hat{\mathcal{A}}_{n-2-k}^{\mathrm{pr}}(1342)$ follows directly from lemma 2.3. Conversely, given $1L \in \hat{\mathcal{A}}_{k+1}^{\mathrm{pr}}(1342)$ and $R'\in \hat{\mathcal{A}}_{n-2-k}^{\mathrm{pr}}(1342)$, by lemma 3.5, one can recover a unique $x\in \hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$. Hence, there are $g_{k+1}g_{n-2-k}$ such $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$ in this case.

• • If R contains at least one copy of mʹ, a 1 is inserted immediately before the first occurrence of mʹ in R, followed by standardization to derive a new sequence, denoted by Rʹʹ. We proceed to show that $R^{\prime\prime}\in \hat{\mathcal{A}}_{n-1-k}^{\mathrm{pr}}(1342)$. First, again by lemma 3.5 and the fact $\mathrm{Asc}(x) = \mathrm{nub}(x)$, we deduce that R starts with 1 or mʹ. By the construction of Rʹʹ, in either case, we have Rʹʹ starts with 1 and furthermore $\mathrm{Asc}(R^{\prime\prime}) = \mathrm{nub}(R^{\prime\prime})$. Since mʹ is preceded by a number larger that mʹ in R, the insertion of 1 will not result in two consecutive occurrences of 1. Thus, Rʹʹ is primitive from lemma 2.3. Note that the insertion of 1 and standardization will not create any occurrence of 1342. In conclusion, $R^{\prime\prime}\in \hat{\mathcal{A}}_{n-1-k}^{\mathrm{pr}}(1342)$. Conversely, given $1L \in \hat{\mathcal{A}}_{k+1}^{\mathrm{pr}}(1342)$ and $R^{\prime\prime}\in \hat{\mathcal{A}}_{n-1-k}^{\mathrm{pr}}(1342)$, by lemma 3.5, one can recover a unique $x\in \hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)$. Hence there are $g_{k+1}g_{n-1-k}$ such x in this case.

Combining the above three cases, we derive that for $n\geq 3$,

(3.3)\begin{align} g_n &= g_{n-2} + g_{n-1} + \sum\limits_{k\geq 1}^{n-3}g_{k+1}(g_{n-2-k}+g_{n-1-k}) \nonumber \\ & = g_{n-2} + g_{n-1} + \sum\limits_{k\geq 2}^{n-2}g_{k}(g_{n-1-k}+g_{n-k})\nonumber \\ & = \sum\limits_{k\geq 1}^{n-2}g_{k}(g_{n-1-k}+g_{n-k}), \end{align}

where the last step is obtained by using the simple fact $g_1 = 1$. Let $g_1'=1$ and for $n \geq 2$, let $g_n' = \sum\limits_{k\geq 1}^{n-1}g_{k}g_{n-k}$. Eq. (3.3) tells us that $g_n +g_{n-1} = g'_n+g'_{n-1}$ for $n\geq 3$. It is routine to check that $g_2 = g'_2 = 1$, which yields that $g_n = g'_n$ for $n\geq 0$. Hence, $g_n = \sum\limits_{k\geq 1}^{n-1}g_{k}g_{n-k}$ for $n\geq 2$, as desired.

Analogous to theorem 3.4, the following theorem can be derived directly from lemma 3.6 and proposition 2.1.

Theorem 3.7. We have

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1342}(t) = \sum_{n\geq 0}g_nt^n = 1 + tc(t).\end{equation*}

Therefore, $|\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1342)|=c_{n-1}$ and

\begin{equation*}|\hat{\mathcal{A}}_{n+1}(1342)| = \sum_{i=0}^{n}\binom{n}{i}c_i.\end{equation*}

Theorem 3.7 confirms a conjecture of Cerbai [Reference Cerbai2] concerning the pattern 1342.

4. Patterns 1243 and 1423

This section is devoted to the enumeration for patterns 1243 and 1423, employing the same decompositions as those used for patterns 1342 and 1324, respectively. Based on proposition 2.1, we only need to consider the primitive cases.

4.1. Pattern 1243

Let $x\in \hat{\mathcal{A}}_n^{\mathrm{pr}}(1243)$ with $\mathrm{max}\, x = m$. Recall that every primitive modified ascent sequence contains exactly one copy of the maximum value. We can decompose x uniquely as $x = 1LmR$. The following lemma is analogous to lemma 3.5, and hence we omit the proof.

Lemma 4.1. Given $n\geq 2$, let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1243)$ with the above decomposition as $x = 1LmR$. Then for any entry $a\geq 2$ in L and $b\geq 2$ in R, we have $a \geq b$.

Let $h_n = |\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1243)|$. We have the following recurrence for h_n.

Lemma 4.2. For $n\geq 1$, we have

(4.1)\begin{equation} h_{n}=h_{n-1}+\sum_{\mathrm{k}=2}^{n-1}h_kh_{n-1-k}, \end{equation}

with the initial value $h_0=1$.

Proof. Let $n \geq 1$ and $x\in \hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$ with the above decomposition $x = 1LmR$, where m is the unique maximum value in x. Let k be the length of 1L and let mʹ be the minimum value of L such that $m' \geq 2$. We distinguish two cases depending on whether L is empty.

Case 1. k = 1. That is, L is empty. By a similar argument as Case 1 of lemma 3.6, we have $R \in \hat{\mathcal{A}}_{n-1}^{\mathrm{pr}}(1243)$. Hence, there are $h_{n-1}$ such sequences in $\hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$ satisfying that L is empty.

Case 2. $2\leq k \leq n$. In this case, L is non-empty. Let $L' = \mathrm{st}(1L)$. By lemma 2.4, $L' \in \hat{\mathcal{A}}_{k}^{\mathrm{pr}}(1243)$. Now we consider R. By lemma 4.1 and the fact that $\mathrm{Asc}(x) = \mathrm{nub}(x)$, R either starts with 1 or mʹ.

• • If R starts with 1, R cannot contain mʹ. Otherwise, the mʹ contained in R will be preceded by a larger number, a contradiction to lemma 4.1. Since x is a Cayley permutation, again by lemma 4.1, we derive that R contains all the numbers between 1 and $m'-1$. It is easily seen that $\mathrm{Asc}(R) = \mathrm{nub}(R)$. By lemma 2.3, $R \in \hat{\mathcal{A}}_{n-k}^{\mathrm{pr}}(1243)$. Conversely, given any $L' \in \hat{\mathcal{A}}_{k}^{\mathrm{pr}}(1243)$ and $R \in \hat{\mathcal{A}}_{n-k}^{\mathrm{pr}}(1243)$, by lemma 4.1, we can recover a unique primitive modified ascent sequence $x \in \hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$. Hence there are $h_kh_{n-k}$ such $x \in \hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$ in this case.

• • If R starts with mʹ, let Rʹ be the sequence obtained from R by deleting the first entry mʹ. By a similar reasoning as the case R starts with 1, we obtain that $R' \in \hat{\mathcal{A}}_{n-1-k}^{\mathrm{pr}}(1243)$. Conversely, given any $L' \in \hat{\mathcal{A}}_{k}^{\mathrm{pr}}(1243)$ and $R' \in \hat{\mathcal{A}}_{n-1-k}^{\mathrm{pr}}(1243)$, we can recover a unique sequence $x \in \hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$. Hence there are $h_kh_{n-1-k}$ such $x \in \hat{\mathcal{A}}_{n+1}^{\mathrm{pr}}(1243)$ in this case.

Combining the above two cases gives

(4.2)\begin{equation} h_{n+1} = h_{n-1} + \sum_{k=2}^{n} h_k(h_{n-k}+ h_{n-1-k}), \end{equation}

for $n\geq 1$. Let $h'_0 =1$ and $h'_n = h_{n-1} + \sum\limits_{k=2}^{n-1} h_kh_{n-1-k}$ for $n \geq 1$. Then by adding h_n to both sides of equation (4.2), we have $h_{n+1}+h_n = h'_{n+1}+h'_n$ for $n\geq 1$. It is routine to check that $h_1 = h'_1 = 1$, which yields that $h_n = h'_n$ for $n\geq 0$. Therefore, $h_n = h_{n-1} + \sum\limits_{k=2}^{n-1} h_kh_{n-1-k}$ for $n \geq 1$, as desired.

Theorem 4.3. We have

(4.3)\begin{equation} \hat{\mathcal{A}}_{1243}^{\mathrm{pr}}(t)=\frac{1+t^2-\sqrt{1-4t+2t^2+t^4}}{2t} \end{equation}

and

(4.4)\begin{equation} \hat{\mathcal{A}}_{1243}(t)=\frac{1+2t^2-2t-\sqrt{1-8t+20t^2-20t^3+8t^4}}{2t-2t^2}. \end{equation}

Proof. Turning the recurrence relation (4.1) into generating function yields

\begin{equation*}\hat{\mathcal{A}}_{1243}^{\mathrm{pr}}(t)-1=t\hat{\mathcal{A}}_{1243}^{\mathrm{pr}}(t)^2-t^2\hat{\mathcal{A}}_{1243}^{\mathrm{pr}}(t). \end{equation*}

Solving the above equation, we obtain (4.3). It then follows from proposition 2.1 that (4.4) holds.

Eq. (4.3) gives the sequence

\begin{equation*} (|\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1243)|)_{n\geq 0} = (1,1,1,2,5,13,35,97,275,794, 2327,\cdots), \end{equation*}

which appears as A082582 in OEIS [18]. This sequence also counts the Dyck paths of semilength n with no uudd (or with no dduu).

4.2. Pattern 1423

For $n\geq 1$, let $d_n = |\hat{\mathcal{A}}^{\mathrm{pr}}_n(1423)|$. Let $e_n = |\{x\in \hat{\mathcal{A}}^{\mathrm{pr}}_n(1423) \mid x_n = 2\}|$. With a similar proof as lemma 3.1, we have the following relation for d_n and e_n.

Lemma 4.4. For $n\geq 1$, we have

(4.5)\begin{align} d_n = e_n + e_{n+1}. \end{align}

For $n\geq 2$, let

\begin{equation*}r_n = |\{x\in \hat{\mathcal{A}}^{\mathrm{pr}}_n(1423) \mid x_2 = 2\}| \quad\text{and}\quad s_n = |\{x\in \hat{\mathcal{A}}^{\mathrm{pr}}_n(1423) \mid x_2 \gt 2\}|.\end{equation*}

For convenience, we set $d_0 = 0$ and $e_n = r_n = s_n = 0$ if n < 2. Obviously, for $n\geq 2$, we have

(4.6)\begin{align} d_n = r_n + s_n. \end{align}

Lemma 4.5. For $n \geq 2$, we have

(4.7)\begin{align} r_n = d_{n-1} + d_{n-2} +s_n+s_{n-1}. \end{align}

Proof. It is routine to check the conclusion for $n\leq 4$. Now we assume that n > 4. Let $x\in\hat{\mathcal{A}}^{\mathrm{pr}}_n(1423)$ with $x_2 = 2$. We consider the following four cases.

Case 1. If $x_3 =1$ and there is exactly one copy of 2 in x, deleting the first two entries in x and standardizing, gives a sequence in $\hat{\mathcal{A}}^{\mathrm{pr}}_{n-2}(1423)$. Hence there are $d_{n-2}$ such x in this case.

Case 2. If $x_3=1$ and there are at least two copies of 2 in x, let xʹ be the sequence obtained from x by deleting the first two entries of x and inserting a 1 directly before the second 2 of x. One can check that $x' \in \hat{\mathcal{A}}^{\mathrm{pr}}_{n-1}(1423)$. Note that $x_4 \gt 2$ as $x_2 = 2$ and $x_3= 1$. It follows that $x'_2 \gt 2$. Hence there are $s_{n-1}$ such x in this case.

Case 3. If $x_3 \gt 1$ and there is exactly one copy of 2 in x, deleting the unique 2 in x and standardizing, gives a sequence in $\hat{\mathcal{A}}^{\mathrm{pr}}_{n-1}(1423)$, Thus, there are $d_{n-1}$ such x in this case.

Case 4. If $x_3 \gt 1$ and there are at least two copies of 2 in x, let xʹ be the sequence obtained from x by deleting the first 2 in x and inserting a 1 directly before the second 2 in x. By a similar argument as in Case 2, we deduce that $x' \in \hat{\mathcal{A}}^{\mathrm{pr}}_{n}(1423)$ with $x'_2 \gt 2$. Thus, there are s_n such x in this case.

Combining the above four cases gives (4.7), as desired.

Given $n\geq 2$, let $x \in \hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1423)$. There is at least one copy of 2 in x. It yields that x can be decomposed uniquely as $x = 1L2R$ according to the rightmost 2 of x. The following lemma is analogous to lemma 3.2, which we omit the proof here.

Lemma 4.6. Given $n\geq 2$, let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1423)$ with the above decomposition as $x = 1L2R$. Then for any entry $a\geq 2$ in L and $b\geq 2$ in R, we have $a\leq b$.

Lemma 4.7. For $n\geq 2$, we have

(4.8)\begin{align} d_n = d_{n-1}+d_{n-2}- r_n+ \sum_{2\leq k\leq n}e_kr_{n+2-k}. \end{align}

Proof. It is routine to verify (4.8) for $2\leq n\leq 4$. Now we assume that n > 4. Let $x\in\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1423)$ with the above decomposition as $x = 1L2R$. Let k be the length of $L' = 1L2$. There are three cases.

Case 1. k = 2. That is L is empty. Note that x ₂ is the unique 2 in x. From Case 1 and Case 3 of lemma 4.5, we have $d_{n-1} + d_{n-2}$ such x.

Case 2. k = n. That is R is empty. Then x is a sequence in $\hat{\mathcal{A}}_{n}^{\mathrm{pr}}(1423)$ that ends with 2, and so there are e_n such x.

Case 3. $3\leq k\leq n-1$. From lemma 4.6, Lʹ is a Cayley permutation. Furthermore, we have $L' \in \hat{\mathcal{A}}_{k}^{\mathrm{pr}}(1423)$ which ends in a 2. Hence, there are e_k choices for Lʹ. Let $m = \mathrm{max}\,L'$. We need to consider four cases for R.

1. (i) If R does not contain m and starts with 1, let $R' = \mathrm{st}(R)$. Then $R' \in \hat{\mathcal{A}}_{n-k}^{\mathrm{pr}}(1423)$ and so there are $d_{n-k}$ such Rʹ.

2. (ii) If R contains no m and does not start with 1, let $R' = \mathrm{st}(1R)$. Then $R' \in \hat{\mathcal{A}}_{n+1-k}^{\mathrm{pr}}(1423)$ and so there are $d_{n+1-k}$ such Rʹ.

3. (iii) If R contains m and starts with 1, let Rʹ be the sequence obtained from R by inserting a 1 directly before the leftmost m of R and then standardizing. Note that m is preceded by a larger number in R and the number m in R corresponds to 2 in Rʹ. Thus, the second entry of Rʹ is greater than 2, thereby there are $s_{n+1-k}$ such Rʹ in this case.

4. (iv) If R contains m and does not start with 1, let Rʹ be the sequence obtained from R by inserting a 1 before R and inserting a 1 directly before the leftmost m in R and then standardizing. Similarly, one can verify that Rʹ is a primitive modified ascent sequence in $\hat{\mathcal{A}}_{n+2-k}^{\mathrm{pr}}(1423)$ with $R'(2) \gt 2$. It follows that there are $s_{n+2-k}$ such Rʹ.

To conclude, there are $d_{n-k}+d_{n+1-k}+s_{n+1-k}+s_{n+2-k}$ choices for Rʹ.

Combining the above three cases gives

\begin{align*} d_n &= d_{n-1}+d_{n-2}+e_n + \sum_{3\leq k\leq n-1}e_k(d_{n-k}+d_{n+1-k}+s_{n+1-k}+s_{n+2-k}) \\ &= d_{n-1}+d_{n-2}+e_n + \sum_{3\leq k\leq n-1}e_kr_{n+2-k} \quad\text{(by (4.7))} \\ &= d_{n-1}+d_{n-2}- r_n+ \sum_{2\leq k\leq n}e_kr_{n+2-k}, \quad(\text{by the fact}\,\, e_2=r_2 = 1), \end{align*}

as desired.

Theorem 4.8. We have

\begin{equation*} \hat{\mathcal{A}}_{1423}^{\mathrm{pr}}(t) = \frac{-t^{4} - 2 \, t^{3} + t^{2} + 6 \, t+2-(t^2+2t)\sqrt{t^{4} - 2 \, t^{2} - 4 \, t + 1} }{2(t + 1)} \end{equation*}

and

\begin{equation*}\hat{\mathcal{A}}_{1423}(t)=\frac{2 \, t^{4} - 6 \, t^{3} + 5\, t^{2}+ 2 \, t -2- (t^2-2t)\sqrt{4 \, t^{4} - 12 \, t^{3} + 16 \, t^{2} - 8 \, t + 1} }{2{(t^{3} - 3 \, t^{2} + 3 \, t - 1)}} .\end{equation*}

Proof. Let $D(t),E(t),R(t)$, and S(t) be the generating functions of $d_n,e_n,r_n$, and s_n, respectively. Note that $D(t) = \hat{\mathcal{A}}_{1423}^{\mathrm{pr}}(t)-1$. Multiplying both sides of equalities (4.5)–(4.8) by tⁿ and summing over all possible n yields

\begin{equation*} \left\{ \begin{aligned} \; D(t) &= E(t) + \frac{E(t)}{t}, \\ \; D(t) &= t+ R(t) + S(t),\\ R(t) &= tD(t)+t^2D(t) +S(t) + tS(t),\\ D(t) &= t+ tD(t) +t^2D(t)-R(t) +\frac{E(t)R(t)}{t^2}. \end{aligned} \right. \end{equation*}

Solving the above equations for D(t) gives the desired expression for $\hat{\mathcal{A}}_{1423}^{\mathrm{pr}}(t)$. The expression for $\hat{\mathcal{A}}_{1423}(t)$ then follows from proposition 2.1.

5. Pattern 1223

This section focuses on the enumeration of the pattern 1223, including both general and primitive cases, and solves a conjecture posed by Cerbai [Reference Cerbai2]. For the general case, we construct a bijection ϕ between $\hat{\mathcal{A}}_n(1223)$ and $\hat{\mathcal{A}}_n(1232)$. For the primitive case, by restricting the map ϕ to $\hat{\mathcal{A}}^{\text{pr}}_n(1223)$ and characterizing their images, we obtain the generating function of $\hat{\mathcal{A}}^{\text{pr}}_n(1223)$. The following lemma is needed for the construction of ϕ.

Given $x\in \hat{\mathcal{A}}_n$, let $\alpha(x) = (a_1,a_2,\ldots , a_k)$ be the list of integers that are greater than 1 and occur at least twice in x. We list them based on the positions of their leftmost occurrences in x, proceeding from left to right. That is, the leftmost a_i is to the left of the leftmost $a_{i+1}$ in x for $1\leq i\leq k-1$. Let x be a modified ascent sequence in $\hat{\mathcal{A}}_n(1223)$ with $\alpha(x) = (a_1,a_2,\ldots , a_k)$. Now we proceed to define $\phi(x)$. For $1\leq i\leq k$, from lemma 5.1, we have two cases for a_i:

• • If all occurrences of a_i are consecutive in x, do nothing.

• • If there are other numbers between the first and the second occurrence of a_i, move all consecutive occurrences of a_i from the second to the last one behind the first a_i, while preserving the relative positions of all other entries.

Let $\phi(x)$ be the resulting sequence.

Example 5.2. Let $x = 13124155443332211\in \hat{\mathcal{A}}_n(1223)$. Then we have $\alpha(x) = (3,2,4,5)$ and $\phi(x) = 13333122244415511$ with the following detailed procedure, where the entries coloured in red indicate the entries that are moved at current stage.

\begin{align*} x = 13124155&443332211 \\ &\downarrow \\ 13{\color{red}{333}}124&155442211 \\ &\downarrow \\ 1333312{\color{red}{2}}&{\color{red}{2}}41554411 \\ &\downarrow \\ 13333122&24{\color{red}{44}}15511=\phi(x). \end{align*}

It should be mentioned that the definition of ϕ is actually independent of the choice of the order of $a_1,a_2,\ldots, a_k$. We define it this way primarily to facilitate the construction of its inverse map.

From the proof of lemma 5.3, we see that there are some entries larger than a ₁ to the right of the rightmost a ₁ in y. Furthermore, the entry b is the last entry larger than a ₁ in y. Hence we can recover x from y by moving all consecutive occurrences of a ₁ from the second to the last one behind the entry b. This enables us to define the inverse map ψ of ϕ. Let y be a modified ascent sequence in $\hat{\mathcal{A}}_n(1232)$ with $\alpha(y) = (a_1,a_2,\ldots , a_k)$. Since y avoids 1232, it is obvious that all occurrences of a_i are consecutive in y. We define $\psi(y)$ as follows. For $i = k,k-1,\ldots, 1$, we consider two cases in each step.

• • If there is no entry larger than a_i to the right of a_i, do nothing.

• • If there is some entry larger than a_i to the right of a_i, let b be the rightmost such entry. Move all consecutive occurrences of a_i from the second to the last one behind the entry b, while preserving the relative positions of all other entries.

For example, let $y = 13333122244415511\in \hat{\mathcal{A}}_n(1232)$. Then we have $\psi(y) = 13124155443332211$. See the procedure in example 5.2 backward for an illustration.

The following theorem follows directly from [Reference Cerbai2, proposition 5.2] and theorem 5.4.

Theorem 5.5. For $n\geq 1$,

\begin{equation*}|\hat{\mathcal{A}}_n(1223)| = \sum_{k=1}^{n}\binom{n-1}{k-1}\sum_{j=1}^{k}(j-1)!S(k-j+1,j),\end{equation*}

where $S(n,k)$ denotes the (n, k)-th Stirling number of the second kind. Furthermore,

\begin{equation*}\hat{\mathcal{A}}_{1223}(t) = \sum_{i\geq0}\frac{t^i(1-t)}{1-(i+1)t}. \end{equation*}

The rest of this section is devoted to the enumeration of $\hat{\mathcal{A}}^{\text{pr}}_n(1223)$. We will accomplish this by restricting the map ϕ to $\hat{\mathcal{A}}^{\text{pr}}_n(1223)$ and characterizing their images.

Let $y \in \phi(\hat{\mathcal{A}}^{\text{pr}}_n(1223))$ with $\alpha(y) = (a_1,a_2,\ldots, a_k)$. We associate y with a permutation by removing all occurrences of 1 in y, removing one copy of each a_i for $1\leq i\leq k$ in y and decreasing each remaining entry by 1. Let $\theta(y)$ denote the resulting permutation. For example, let $y = 13312244151\in \phi(\hat{\mathcal{A}}^{\text{pr}}_{12}(1223))$. We have $\theta(y) = 2134$.

Let $\mathcal{S}_n$ denote the set of permutations of $[n]$. Given a permutation $\pi = \pi_1\pi_2\cdots \pi_n \in \mathcal{S}_n$, we say π_i is a right-to-left maximum if $\pi_i \gt \pi_j$ for all $ i \lt j\leq n$. Let $\text{rlmax}(\pi)$ denote the number of right-to-left maxima in π and let $p_{n,a,r}$ denote the number of permutations in $\mathcal{S}_n$ with a + 1 ascents and r right-to-left maxima. We need the following continued fraction expression due to Zeng [Reference Zeng21, theorem 3].

Theorem 5.7 (Zeng)

The generating function for $p_{n,a,r}$ is

\begin{align*} P(t,u,v) &\mathrel{:=} \sum_{n\geq 0}\sum_{0\leq a\leq n-1}\sum_{0\leq r\leq n-a}p_{n,a,r}t^nu^av^r \\ & = \cfrac{1}{1-vt - \cfrac{vut^2}{1-(v+u+1)t - \cfrac{2(v+1)ut^2}{\cfrac{\ddots}{1-(v+n(u+1))t-\cfrac{(n+1)(v+n)ut^2}{\ddots} }}}}. \end{align*}

In fact, Zeng [Reference Zeng21] obtained a stronger version of theorem 5.7 which contains five classic permutation statistics.

Let $q_{n,a,r}$ denote the number of modified ascent sequences y in $\phi(\hat{\mathcal{A}}^{\text{pr}}_n(1223))$ such that $\theta(y)$ have a + 1 ascents and r right-to-left maxima.

Theorem 5.8. We have

(5.1)\begin{equation} Q(t,u,v) \mathrel{:=} \sum_{n\geq 0}\sum_{0\leq a\leq n-1}\sum_{0\leq r\leq n-a}q_{n,a,r}t^nu^av^r = (1+t)P\left((1+t)t^2,\frac{u(1+t)}{t},\frac{v}{1+t}\right). \end{equation}

Proof. Let π be a permutation in $\mathcal{S}_n$ with a + 1 ascents and r right-to-left maxima. To obtain a modified ascent sequence y in $\phi(\hat{\mathcal{A}}^{\text{pr}}_n(1223))$ such that $\theta(y)= \pi$, by the definition of θ, we first increase each entry in π by one, resulting in a permutation $\pi'$. By lemma 5.6, we can choose to replace each entry a in $\pi'$, where a is not a right-to-left maximum, by aa. It is obvious that there are n − r entries which are not right-to-left maxima in $\pi'$. Let $\pi^{\prime\prime}$ be the resulting permutation. Then, add one copy of 1 before each descent bottom of $\pi^{\prime\prime}$ and add one copy of 1 before $\pi^{\prime\prime}$. This operation ensures that the leftmost copy of each entry in the resulting sequence is an ascent top. There are $n-1-a$ descents in $\pi^{\prime\prime}$. Hence, we must add n − a copies of 1 to $\pi^{\prime\prime}$. As for the positions before each ascent top (excluding the position before $\pi^{\prime\prime}$) and the position after $\pi^{\prime\prime}$, we can choose to add one copy of 1 or not to add. There are a + 1 such positions. To conclude, we have

\begin{align*} Q(t,u,v) &= \sum_{n\geq 0}\sum_{0\leq a\leq n-1}\sum_{0\leq r\leq n-a}p_{n,a,r}t^nu^av^r(1+t)^{n-r}t^{n-a}(1+t)^{a+1} \\ &= (1+t)\sum_{n\geq 0}\sum_{0\leq a\leq n-1}\sum_{0\leq r\leq n-a}p_{n,a,r}((1+t)t^2)^n \left(\frac{u(1+t)}{t}\right)^a\left(\frac{v}{1+t}\right)^r \\ &= (1+t)P\left((1+t)t^2,\frac{u(1+t)}{t},\frac{v}{1+t}\right), \end{align*}

as desired.

Setting $u = v = 1$ in equation (5.1), we immediately obtain the generating function for $\hat{\mathcal{A}}^{\text{pr}}_n(1223)$.

Theorem 5.9. We have

\begin{equation*}\hat{\mathcal{A}}^{\mathrm{pr}}_{1223}(t) = (1+t)P\left((1+t)t^2,\frac{1+t}{t},\frac{1}{1+t}\right). \end{equation*}

6. Pattern 1123

In this section, we prove that $\hat{\mathcal{A}}^{\text{pr}}_n(1123)$ and $\hat{\mathcal{A}}^{\text{pr}}_n(1243)$ are equinumerous by showing that they share the same generating function as shown in theorem 4.3. In fact, we obtain the generating function of $\hat{\mathcal{A}}^{\text{pr}}_n(1123)$ with respect to several statistics by using kernel method. Incidentally, we reprove that $\hat{\mathcal{A}}_n(1123)$ is counted by the Catalan numbers and find a new Narayana statistic on $\hat{\mathcal{A}}_n(1123)$.

Cerbai [Reference Cerbai and Claesson5] showed that the hat map is a bijection between $\mathcal{A}_n(1123)$ and $\hat{\mathcal{A}}_n(1123)$. By the definition of the hat map, it is easily seen that an ascent sequence is primitive if and only if $\hat{x}$ is primitive. Hence, the hat map also induces a bijection between $\mathcal{A}^{\text{pr}}_n(1123)$ and $\hat{\mathcal{A}}^{\text{pr}}_n(1123)$. This motivates us to consider ascent sequences and primitive ascent sequences that avoid the pattern 1123 in this section. Mansour and Shattuck [Reference Mansour and Shattuck16] proved that $|\mathcal{A}_n(1123)| = c_n$, confirming a conjecture of Duncan and Steingrímsson [Reference Duncan and Steingrímsson9]. We will adapt their method to the enumeration of primitive counterpart.

Let us introduce some statistics first. Given an endofunction x, let $\mathrm{fwd}(x)$ be the length of the maximal final weakly decreasing sequence in x and let $\mathrm{one}(x)$ be the number of copies of 1 in x. If x is primitive, let $\text{NS}(x)$ be the set of entries which cannot play the role “1” in any pattern 123 and let $\text{ns}(x) = |\text{NS}(x)|$. For general x, define $\text{ns}(x) = \text{ns}(\tilde{x})$, where $\tilde{x}$ is the primitive sequence obtained from x by merging each the consecutive flat step of x into one single copy. For example, let x = 135224155126643321. We have $\text{fwd}(x) = 7$ since 6643321 has length 7 and $\text{ns}(x) = 8$ since the entries colored by red in its corresponding primitive sequence $13{\bf5}241{\bf5}1{\bf264321}$ cannot play the role “1” in any pattern 123.

Given $n\geq 1$ and $1\leq r,l,k \leq n$, let

\begin{equation*}A_{n,r,l,k}:=\{x\in\mathcal{A}^{\text{pr}}_n(1123): \mathrm{one}(x)=r, \mathrm{fwd}(x)=l, \mathrm{ns}(x)=k\}.\end{equation*}

and let $a_{n,r,l,k} = |A_{n,r,l,k}|$. Let $B_{n,r,l,k}:=\{x\in A_{n,r,l,k}: x_n\neq1\}$ and let $b_{n,r,l,k} = |B_{n,r,l,k}|$.

Lemma 6.1. For $n\geq 2$ and $1\leq r,l,k \leq n$, we have

\begin{equation*}a_{n,r,l,k} = b_{n,r,l,k} + b_{n-1,r-1,l-1,k-1}.\end{equation*}

The array $b_{n,r,l,k}$ is determined by the recurrences as showed in the following lemma.

Lemma 6.2. The array $b_{n,r,l,k}$ may be non-zero only when $n\geq 2$, $1\leq r \leq \lfloor \frac{n}{2} \rfloor$, $1\leq l\leq n+1-2r$, and $1\leq k \leq n$. Furthermore, $b_{n,r,l,k}$ is determined by the following recurrences:

(6.1)\begin{align} b_{n,1,l,k} &= \sum_{i\geq 1}(b_{n-1,i,l,k} + b_{n-2,i-1,l-1,k-1}), \quad n\geq 3, \end{align}

(6.2)\begin{align} b_{n,2,l,k} &= \sum_{i\geq 1}\sum_{j\geq l}(b_{n-2,i,j,k-1} +b_{n-3,i-1,j-1,k-2} +b_{n-3,i,j,k-2} + b_{n-4,i-1,j-1,k-3}), \nonumber\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad n\geq 5, \end{align}

(6.3)\begin{align} b_{n,r,l,k} &= \sum_{j\geq l+1}b_{n-1,r-1,j,k-1} + \sum_{j\geq l}b_{n-2,r-1,j,k-2}, \quad n\geq 2, r\geq 3, \end{align}

and the initial values

\begin{equation*}b_{2,1,l,k} = \begin{cases} 1, \quad \text{if } l=1 \text{and } k = 2;\\ 0, \quad \text{otherwise,} \end{cases}\end{equation*}

and

\begin{equation*}b_{4,2,l,k} = \begin{cases} 1, \quad \text{if } l=1, k=3 \text{or } l=1, k = 4 ;\\ 0, \quad \text{otherwise.} \end{cases}\end{equation*}

Let $B(t,u,v,w) = \sum_{n,r,l,k}b_{n,r,l,k}t^nu^rv^lw^k$, where $n,r,l,k$ range over all possible values such that $b_{n,r,l,k} \gt 0$. In what follows, for convenience, we always assume the summation variables take over all possible values unless specifically stated otherwise. Given $r\geq 1$, let $B_r(t,v,w) = \sum_{n,l,k}b_{n,r,l,k}t^nv^lw^k$. The polynomial $B_r(t,v,w)$ satisfies the following relations.

Lemma 6.3. We have

(6.4)\begin{align} B_1(t,v,w) &= t^2vw^2 + (t +t^2vw)B(t,1,v,w), \end{align}

(6.5)\begin{align} B_2(t,v,w) &= t^4vw^4 + \frac{t^2vw}{1-v}(1+2tw+t^2w^2)B(t,1,1,w) \notag\\ &-\frac{t^2vw}{1-v}(1+tvw+tw + t^2vw^2)B(t,1,v,w), \end{align}

and for $r\geq 3$,

(6.6)\begin{equation} B_r(t,v,w) = \frac{tvw+t^2vw^2}{1-v}B_{r-1}(t,1,w) - \frac{tw+t^2vw^2}{1-v}B_{r-1}(t,v,w). \end{equation}

Proof. If r = 1, we have

\begin{align*} B_1(t,v,w) &= \sum_{n,l,k}b_{n,1,l,k}t^nv^lw^k \\ &= t^2vw^2 + \sum_{n\geq 3,l,k}b_{n,1,l,k}t^nv^lw^k \quad(\text{by the initial values in lemma 6.2})\\ &= t^2vw^2 + \sum_{n\geq 3,i,l,k}(b_{n-1,i,l,k} + b_{n-2,i-1,l-1,k-1})t^nv^lw^k \quad\quad(\text{by } (6.1)) \\ &= t^2vw^2 + (t +t^2vw)B(t,1,v,w), \end{align*}

which gives (6.4).

If r = 2, we have

\begin{align*} B_2(t,v,w) &= \sum_{n,l,k} b_{n,2,l,k} t^n v^l w^k \\ &= t^4vw^3 + t^4vw^4 + \sum_{\substack{n \geq 5, l, k}} b_{n,2,l,k} t^n v^l w^k \quad (\text{by the initial values in lemma 6.2}) \\ &= t^4vw^3(1 + w) + \sum_{\substack{n \geq 5, i, l, k}} \sum_{j \geq l} \Big( b_{n-2,i,j,k-1} + b_{n-3,i-1,j-1,k-2} \\ &\qquad\qquad\qquad\qquad + b_{n-3,i,j,k-2} + b_{n-4,i-1,j-1,k-3} \Big) t^n v^l w^k \quad (\text{by } (6.2)) \\ &= t^4vw^3(1 + w) + \sum_{\substack{n \geq 5,i, j, k}} \Big( b_{n-2,i,j,k-1} + b_{n-3,i-1,j-1,k-2} \\ &\qquad\qquad\qquad\qquad + b_{n-3,i,j,k-2} + b_{n-4,i-1,j-1,k-3} \Big) t^n w^k \sum_{1 \leq l \leq j} v^l \\ &= t^4vw^3(1 + w) + \frac{v}{1-v} \sum_{\substack{n \geq 5, i, j, k}} \Big( b_{n-2,i,j,k-1} + b_{n-3,i-1,j-1,k-2} \\ &\qquad\qquad\qquad\qquad + b_{n-3,i,j,k-2} + b_{n-4,i-1,j-1,k-3} \Big) t^n (1 - v^j) w^k \\ &= t^4vw^3(1 + w) + \frac{v}{1-v} \biggl( t^2w \big[ B(t,1,1,w) - t^2w^2 - B(t,1,v,w) + t^2vw^2 \big] \\ &\qquad\qquad + t^3w^2 \big[ B(t,1,1,w) - vB(t,1,v,w) \big] \\ &\qquad\qquad + t^3w^2 \big[ B(t,1,1,w) - B(t,1,v,w) \big] \\ &\qquad\qquad + t^4w^3 \big[ B(t,1,1,w) - vB(t,1,v,w) \big] \biggl) \\ &= t^4vw^4 + \frac{t^2vw}{1-v} \big( 1 + 2tw + t^2w^2 \big) B(t,1,1,w) \\ &\qquad\qquad - \frac{t^2vw}{1-v} \big( 1 + tvw + tw + t^2vw^2 \big) B(t,1,v,w), \end{align*}

where the last step is obtained by careful calculation and simplification. Hence (6.5) follows.

If $r \geq 3$, we have

\begin{align*} B_r(t,v,w) &= \sum_{n,l,k} b_{n,r,l,k} t^n v^l w^k \\ &= \sum_{n,l,k} \left( \sum_{j \geq l+1} b_{n-1,r-1,j,k-1} + \sum_{j \geq l} b_{n-2,r-1,j,k-2} \right) t^n v^l w^k \\ &= \sum_{\substack{n,j \geq 2,k}} b_{n-1,r-1,j,k-1} t^n w^k \sum_{1 \leq l \leq j-1} v^l+ \sum_{\substack{n, j, k}} b_{n-2,r-1,j,k-2} t^n w^k \sum_{1 \leq l \leq j} v^l \\ &= \frac{v}{1-v} \sum_{\substack{n, j, k}} b_{n-1,r-1,j,k-1} t^n w^k (1 - v^{j-1})+ \frac{v}{1-v} \sum_{\substack{n, j, k}} b_{n-2,r-1,j,k-2} t^n w^k\\ &\quad\times (1 - v^{j}) \\ &= \frac{tw}{1-v} \big( vB_{r-1}(t,1,w) - B_{r-1}(t,v,w) \big)+ \frac{t^2vw^2}{1-v} \big( B_{r-1}(t,1,w)\\ &\quad - B_{r-1}(t,v,w) \big) \\ &= \frac{tvw + t^2vw^2}{1-v} B_{r-1}(t,1,w) - \frac{tw + t^2vw^2}{1-v} B_{r-1}(t,v,w), \end{align*}

which gives (6.6).

The polynomial $B(t,u,v,w)$ satisfies the following functional equation.

Lemma 6.4. We have

(6.7)\begin{align} &(1-v+tuw+t^2uvw^2)B(t,u,v,w) \notag \\ =& (1-v)t^2uvw^2 + tu(1-v)(tuw+1)(tvw+1)B(t,1,v,w) \notag \\ & + tuvw(1+tw)B(t,u,1,w). \end{align}

Proof. Note that

\begin{equation*}B(t,u,v,w) = \sum_{r\geq 1} B_r(t,v,w)u^r.\end{equation*}

Then by lemma 6.3, we have

(6.8)\begin{align} B(t,u,v,w) &= t^2uvw^2 + tu(1 + tvw)B(t,1,v,w) \notag \\ &\quad + t^4u^2vw^4 + \frac{t^2u^2vw}{1-v} \big( 1 + 2tw + t^2w^2 \big) B(t,1,1,w) \notag \\ &\quad - \frac{t^2u^2vw}{1-v} \big( 1 + tvw + tw + t^2vw^2 \big) B(t,1,v,w) \notag \\ &\quad + \frac{tvw + t^2vw^2}{1-v} \sum_{r \geq 3} B_{r-1}(t,1,w) u^r \notag \\ &\quad - \frac{tw + t^2vw^2}{1-v} \sum_{r \geq 3} B_{r-1}(t,v,w) u^r \notag \\ &= t^2uvw^2 + tu(1 + tvw)B(t,1,v,w) \notag \\ &\quad + t^4u^2vw^4 + \frac{t^2u^2vw}{1-v} \big( 1 + 2tw + t^2w^2 \big) B(t,1,1,w) \notag \\ &\quad - \frac{t^2u^2vw}{1-v} \big( 1 + tvw + tw + t^2vw^2 \big) B(t,1,v,w) \notag \\ &\quad + \frac{tuvw + t^2uvw^2}{1-v} \big( B(t,u,1,w) - uB_1(t,1,w) \big) \notag \\ &\quad - \frac{tuw + t^2uvw^2}{1-v} \big( B(t,u,v,w) - uB_1(t,v,w) \big). \end{align}

By (6.4), we have

(6.9)\begin{equation} B_1(t,1,w) = t^2w^2 + (t +t^2w)B(t,1,1,w). \end{equation}

Substituting (6.4) and (6.9) into (6.8) we obtain (6.7) after simplification.

Lemma 6.5. We have

(6.10)\begin{align} B(t,1,1,w) = \frac{-{\left(t^{2} + t\right)} w - t + 1- \sqrt{{\left(t^{4} - 2 \, t^{3} + t^{2}\right)} w^{2} + t^{2} + 2 \, {\left(t^{3} - t\right)} w - 2 \, t + 1} }{2 \, {\left(t^{2} w + t\right)}}. \end{align}

Proof. Letting u = 1 in (6.7) implies

(6.11)\begin{align} (t^{3} v^{2} w^{2} - t^{3} v w^{2} + t^{2} v^{2} w + t^{2} v w^{2} - t^{2} w + t v + t w - t - v + 1)B(t,1,v,w) \notag \\ = (1-v)t^2vw^2 + tvw(1+tw)B(t,1,1,w). \end{align}

We proceed to solve equation (6.11) by using kernel method. Let $v_0= v_0(t,w)$ satisfy

\begin{equation*}t^{3} v_0^{2} w^{2} - t^{3} v_0 w^{2} + t^{2} v_0^{2} w + t^{2} v_0 w^{2} - t^{2} w + t v_0 + t w - t - v_0 + 1 = 0,\end{equation*}

namely,

(6.12)\begin{equation} v_0 = \frac{{\left(t^{2} - t\right)} w - t + 1 - \sqrt{{\left(t^{4} - 2 \, t^{3} + t^{2}\right)} w^{2} + t^{2} + 2 \, {\left(t^{3} - t\right)} w - 2 \, t + 1} }{2 \, t^{2} w}. \end{equation}

(Note that there are two solutions for v ₀, we choose the one by the condition $B(0,1,1,1) = 0$.) Letting $v = v_0$ in (6.11), and solving for $B(t,1,1,w)$, gives

\begin{equation*}B(t,1,1,w) = \frac{tw {\left(v_0 - 1\right)} }{t w + 1}.\end{equation*}

Substituting (6.12) into the above expression and simplifying implies (6.10), as desired.

To obtain the expression for $B(t,u,v,w)$, we still need to find expressions for $B(t,1,v,w)$ and $B(t,u,1,w)$. By (6.11), we have

(6.13)\begin{equation} B(t,1,v,w) = \frac{(1-v)t^2vw^2 + tvw(1+tw)B(t,1,1,w)}{t^{3} v^{2} w^{2} - t^{3} v w^{2} + t^{2} v^{2} w + t^{2} v w^{2} - t^{2} w + t v + t w - t - v + 1}. \end{equation}

To find an expression for $B(t,u,1,w)$, we again use kernel method. Let $v_1 = v_1(t,u,w)$ satisfy

\begin{equation*}1-v_1 +tuw+t^2uv_1w^2 = 0,\end{equation*}

namely,

\begin{equation*}v_1 = \frac{t u w + 1}{1-t^{2} u w^{2} }.\end{equation*}

Letting $v = v_1$ in (6.7), and solving for $B(t,u,1,w)$ gives

(6.14)\begin{equation} B(t,u,1,w) = \frac{(v_1-1)tv_1w^2 + (v_1-1)(tuw+1)(tv_1w+1)B(t,1,v_1,w) }{v_1w(1+tw)}. \end{equation}

It then follows from (6.7) that

(6.15)\begin{equation} B(t,u,v,w) =\frac{\begin{array}{l} (1-v)t^2uvw^2 + tu(1-v)(tuw+1)(tvw+1)B(t,1,v,w) \\ \qquad\qquad\qquad\qquad\qquad\qquad\,\,\,+ tuvw(1+tw)B(t,u,1,w)\end{array}}{(1-v+tuw+t^2uvw^2)}, \end{equation}

where $B(t,1,v,w)$ and $B(t,u,1,w)$ are given by (6.13) and (6.14), respectively.

The following theorem follows directly from lemma 6.1.

Theorem 6.6. Let $A(t,u,v,w):= \sum_{n,r,l,k}a_{n,r,l,k}t^nu^rv^lw^k$. Then,

\begin{equation*} A(t,u,v,w) = 1+ tuvw + (1+tuvw)B(t,u,v,w), \end{equation*}

where $B(t,u,v,w)$ is given by (6.15).

The following result shows that the sequence $\{|\hat{\mathcal{A}}^{\text{pr}}_n(1123)|\}_{n\geq0}$ matches A082582 in the OEIS [18], as was conjectured by Cerbai [Reference Cerbai2].

Theorem 6.7. We have

\begin{equation*}A(t,1,1,w) = \frac{{\left(t^{2} - t\right)} w+ t + 1 - \sqrt{{\left(t^{4} - 2 \, t^{3} + t^{2}\right)} w^{2} + t^{2} + 2 \, {\left(t^{3} - t\right)} w - 2 \, t + 1} }{2 \, t}. \end{equation*}

In particular,

(6.16)\begin{equation} \mathcal{A}^{\mathrm{pr}}_{1123}(t) = \hat{\mathcal{A}}^{\mathrm{pr}}_{1123}(t) = \frac{1+t^2-\sqrt{1-4t+2t^2+t^4}}{2t} \end{equation}

and so

(6.17)\begin{equation} |\hat{\mathcal{A}}^{\mathrm{pr}}_n(1243)|= |\mathcal{A}^{\mathrm{pr}}_n(1123)|= |\hat{\mathcal{A}}^{\mathrm{pr}}_n(1123)|. \end{equation}

Theorem 6.8. Let

\begin{equation*}N(t,w):=\sum_{n\geq0}t^n\sum_{x\in\mathcal{A}_n(1123)}w^{\mathrm{ns}(x)}.\end{equation*}

Then,

(6.18)\begin{equation} N(t,w) = \frac{1+t-tw - \sqrt{t^{2}w^{2} + t^{2} - 2 (t^{2} + t) w - 2t + 1}}{2t}. \end{equation}

Proof. Any ascent sequence in $\mathcal{A}(1123)$ can be obtained uniquely from some primitive ascent sequence $y\in\mathcal{A}^{\text{pr}}(1123)$ by inserting proper flat steps immediately after the entries in $\mathrm{NS}(y)$. In terms of generating function, this gives

\begin{equation*}N(t,w) = A\left(t,1,1,\frac{w}{1-t}\right).\end{equation*}

The expression (6.18) for $N(t,w)$ then follows from theorem 6.7.

Remark 6.9. Mansour and Shattuck [Reference Mansour and Shattuck16] proved that the statistic “ $\mathrm{asc}$” on $\mathcal{A}_n(1123)$ is a Narayana distribution, that is

\begin{equation*} |\{x\in\mathcal{A}_n(1123): \mathrm{asc}(x)=k+1\}|=\frac{1}{n}{n\choose k+1}{n\choose k}. \end{equation*}

Theorem 6.8 shows that the statistic “ $\mathrm{ns}$” on $\mathcal{A}_n(1123)$ is a new Narayana distribution.

Theorem 6.10. For any $x \in \mathcal{A}_n(1123)$, we have

\begin{equation*}(\mathrm{asc},\mathrm{one}, \mathrm{fwd},\mathrm{ns})(x) = (\mathrm{asc},\mathrm{one},\mathrm{fwd},\mathrm{ns})(\hat{x}).\end{equation*}

Consequently, all results stated in this section for 1123-avoiding (primitive) ascent sequences are also true for 1123-avoiding (primitive) modified ascent sequences.

7. Final remarks and future directions

In section 3, we proved that both $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1324)$ and $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1342)$ are counted by the Catalan numbers by using generating functions. It is interesting to find a bijection between $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1324)$ and $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1342)$ or bijections between these two sets and other known Catalan objects. We failed to find any statistic on $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1324)$ or $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1342)$ that interprets the Narayana numbers. Thus, we pose the following challenging open problem for further research.

In sections 4.1 and 6, we proved that both $\hat{\mathcal{A}}^{\text{pr}}_n(1243)$ and $\hat{\mathcal{A}}^{\text{pr}}_n(1123)$ are equinumerous with the set of Dyck paths of semilength n with no uudd. Are there bijections among these three sets?

Given two patterns σ and τ, they are said to be strong-Wilf-equivalent if both $|\hat{\mathcal{A}}^{\mathrm{pr}}_n(\sigma)| = |\hat{\mathcal{A}}^{\mathrm{pr}}_n(\tau)|$ and $|\hat{\mathcal{A}}_n(\sigma)| = |\hat{\mathcal{A}}_n(\tau)|$ hold for any $n\geq 1$. We denote the strong-Wilf-equivalence of σ and τ by $\sigma \sim \tau$.

Conjecture 7.2. For $k\geq 1$, we have

\begin{equation*} 2\underbrace{1\dots 1}_{k} \sim 1 \underbrace{2\dots 2}_{k}3,\end{equation*}

where $\underbrace{a\dots a}_{k}$ denotes the sequence that contains k copies of a.

The case k = 1 of conjecture 7.2 have been verified by Cerbai [Reference Cerbai2]. In the same paper, Cerbai conjectured that $211 \sim 1223$ which corresponds k = 2 in conjecture 7.2. Note that we obtain the enumeration of $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1223)$ and $\hat{\mathcal{A}}_n(1223)$ in section 5. Hence, confirming of conjecture 7.2 will lead to the enumeration of $\hat{\mathcal{A}}^{\mathrm{pr}}_n(211)$ and $\hat{\mathcal{A}}_n(211)$, which is one of the two unsolved patterns of length 3. The other unsolved pattern of length 3 is 111.

Conjecture 7.3. For $k\geq 1$, we have

\begin{equation*} \underbrace{2\dots 2}_{k}1 \sim 12 \underbrace{3\dots 3}_{k}.\end{equation*}

When k = 1, conjectures 7.2 and 7.3 are the same, which yields that conjecture 7.3 is valid for k = 1. When k = 2, Cerbai [Reference Cerbai2] proved that $\hat{\mathcal{A}}^{\mathrm{pr}}_n(221)$ is counted by the Bell numbers. Hence, confirming of conjecture 7.3 will yield that $\hat{\mathcal{A}}^{\mathrm{pr}}_n(1233)$ is also counted by the Bell numbers. Cerbai [Reference Cerbai3] obtained that (primitive) modified ascent sequence avoiding a large number of patterns are counted by the Bell numbers. Numerical evidence shows that 1233 is the last pattern of length less than or equal to 4 that could potentially be counted by the Bell numbers.

All the conjectures above have been verified up to k = 5 and n = 10. Are there any other families of strong-Wilf-equivalence classes?

Parallel to the works in [Reference Lin14, Reference Lin and Yan15, Reference Martinez and Savage17] for patterns in inversion sequences or ascent sequences, it would be interesting to investigate systematically (primitive) modified ascent sequences avoiding triples of relations or avoiding vincular patterns.