Conjecture on pattern-avoiding ascent sequences under the maximum bijection

Four pattern restrictions of the maximum hat map

Let $A_0$ be the set of ascent sequences in the positive-integer convention: the empty sequence is allowed, and a nonempty sequence $a_1\cdots a_n$ satisfies

$$a_i\le 1+\operatorname{asc}(a_1\cdots a_{i-1}).$$

Here $\operatorname{asc}(\epsilon)=0$, while for a nonempty word it is one plus the number of strict rises between consecutive entries. In particular, $a_1=1$. Write $A_0(p)$ for the sequences avoiding the word pattern $p$, and $\mathfrak S(p_1,\ldots,p_r)$ for permutations avoiding the indicated classical patterns. Word-pattern occurrences preserve both inequalities and equalities.

We prove that $H=\mathrm{hat}_{\max}$ restricts to the four size-preserving bijections

$$\begin{aligned} A_0(123)&\longrightarrow\mathfrak S(123,213),\\ A_0(112)&\longrightarrow\mathfrak S(213,312),\\ A_0(121)&\longrightarrow\mathfrak S(213,231),\\ A_0(213)&\longrightarrow\mathfrak S(213,45123). \end{aligned}$$

These are Cerbai, Claesson and Sagan, Conjecture 9.2, also Conjecture 9.2 in the published paper.

The elementary descriptions of the first three word classes and the restricted-growth property of the fourth are already known; see Duncan and Steingrímsson, Pattern avoidance in ascent sequences, Theorems 2.1–2.2 and Lemma 2.4, after increasing their entries by one. We include the needed arguments and establish the four images under the specified map $H$.

1. The insertion rule

An inversion sequence has $1\le a_i\le i$. For a permutation $\pi$ and a possible new last value $a$, let $\pi^{+a}$ be obtained by increasing every entry at least $a$ by one. The source's Lemma 5.3 and Corollary 5.5 give

$$H(\epsilon)=\epsilon,\qquad H(ua)=H(u)^{+a}a, \tag{1}$$

and state that $H$ is a bijection from inversion sequences to permutations. Indeed, the last value can be deleted and all larger values decremented, reversing each insertion. Equivalently, if $\pi=H(a_1\cdots a_n)$, then

$$a_i=1+\#\{j<i:\pi_j<\pi_i\}. \tag{2}$$

Future insertions preserve the relative order of existing entries. Thus

$$a_i<a_{i+1}\quad\Longleftrightarrow\quad \pi_i<\pi_{i+1}. \tag{3}$$

We use this already established unrestricted bijection and prove the four restrictions. The empty sequence satisfies all four claims. Whenever a last entry is mentioned below, the prefix is nonempty.

2. The patterns $123$ and $112$

An ascent sequence avoids $123$ exactly when all its entries are in $\{1,2\}$. To see the nontrivial direction, consider its first entry at least $3$. The ascent bound requires an earlier strict rise, necessarily from $1$ to $2$, producing a $123$ occurrence. Conversely, every binary word beginning with $1$ is an ascent sequence and avoids $123$.

A permutation avoids both $123$ and $213$ exactly when no entry has two smaller entries to its left: any two such entries, in either order, form one of these two patterns with it. By (2), this is exactly the condition that every prefix rank is at most $2$. This proves the first bijection.

An ascent sequence avoids $112$ exactly when it consists of an initial segment

$$1,2,\ldots,m$$

followed by a weakly decreasing word with entries at most $m$. Indeed, the initial strictly increasing segment must have this form by the ascent bound. At the first non-increase, the new value $a$ has already appeared in that segment. Avoiding $112$ forces every subsequent value to be at most $a$. Applying the same observation at each later position makes the entire remaining word weakly decreasing. The converse follows directly from this description.

The permutations avoiding $213$ and $312$ are exactly the unimodal permutations: an increasing segment followed by a decreasing segment. Both forbidden patterns have their smallest entry in the middle, and any change from decreasing to increasing creates such a valley. By (3), the preceding ascent sequences map precisely to these permutations. Conversely, the prefix-rank code of a unimodal permutation starts $1,2,\ldots,m$ and is then weakly decreasing, so it belongs to the described ascent-sequence class. This proves the second bijection.

3. The pattern $121$

An ascent sequence avoids $121$ exactly when it is weakly increasing. Before a first descent, the ascent bound makes the word consist of nonempty constant blocks with successive values $1,2,\ldots,m$. A descent then returns to a previously used value, forming $121$. Conversely, such a weakly increasing block word clearly avoids $121$. Its possible next values are its last value $b$ and $b+1$.

We check that the same rule governs $\mathfrak S(213,231)$. Suppose $\pi$ belongs to this class and ends in $b$. Insert a new last value $a$ using (1).

If $a<b$, the old entries with values $a$ and $b$, followed by the new entry, become a $231$ occurrence. If $a>b+1$, the old entries with values $a-1$ and $b$, followed by the new entry, form $213$.

For $a=b$ or $a=b+1$, no new forbidden occurrence is possible. A new $213$ would require an earlier descending pair whose larger value is below $a$; that pair would already form $213$ with the old last entry $b$. A new $231$ would similarly require an earlier increasing pair above the new last value; it would already form $231$ with $b$. In these comparisons, $b$ itself cannot be an earlier member of the pair, since it was the last entry of $\pi$.

Consequently the permissible new ranks are exactly

$$a\in\{b,b+1\}.$$

Starting from $1$, this is precisely the rule for the weakly increasing ascent sequences. Prefix deletion and standardization preserve permutation avoidance, so the rule proves surjectivity as well as preservation. Injectivity follows from that of $H$, proving the third bijection.

4. The pattern $213$: a rule for sequences

A restricted growth word starts with $1$ and satisfies

$$a_i\le 1+\max(a_1,\ldots,a_{i-1})$$

at later positions. Every such word is an ascent sequence: its current maximum is at most its ascent number, because each new maximum creates a strict rise.

Conversely, every $213$-avoiding ascent sequence is a restricted growth word. At a first violation, its new value $a$ exceeds $M+1$, where $M$ is the previous maximum. If the prefix is weakly increasing, its ascent number is $M$, contradicting the ascent bound. If not, any earlier inversion has both entries below $a$ and forms $213$ with it. Let $\mathcal R_{213}$ denote the class of $213$-avoiding restricted growth words. We have therefore shown

$$A_0(213)=\mathcal R_{213}. \tag{4}$$

For such a word $u$, define its label $L(u)$ as follows. Set $L(\epsilon)=1$. For nonempty $u$ with maximum $M$, set

$$\begin{aligned} &L(u)=\\ &\begin{cases} M+1,&\text{no inversion},\\ \begin{aligned} &\min\{u_i:i<j,\\ &\ u_i>u_j\}, \end{aligned} &\text{otherwise}. \end{cases} \end{aligned} \tag{5}$$

Let $\chi(u)$ be $1$ if $u$ has an inversion and $0$ otherwise. The allowed next letters are exactly

$$1\le a\le L(u). \tag{6}$$

Indeed, restricted growth imposes $a\le M+1$, while an old inversion with top $u_i$ forms a new $213$ precisely when $a>u_i$.

The label update is

$$L(ua)=a+1-\mathbf1_{\{a=L(u)\}}\chi(u). \tag{7}$$

To check it, recall that all values $1,\ldots,M$ occur in $u$. If $u$ already has an inversion, then $a\le L(u)\le M$. For $a<M$, the smallest new inversion top is $a+1$, so the new label is $\min(L(u),a+1)$. If $a=M$, necessarily $a=L(u)=M$, and the old label remains unchanged. These give (7). If $u$ has no inversion, appending $a<M$ creates least inversion top $a+1$, while appending $M$ or $M+1$ leaves a weakly increasing word with maximum $a$. Again (7) follows. The empty case gives $L(1)=2$ directly.

5. The matching rule for permutations

Let

$$\mathcal C=\mathfrak S(213,45123).$$

For $\pi\in\mathcal C$ ending in $b$, define

$$\begin{aligned} &B(\pi)=\\ &\begin{cases} b,&\begin{aligned} &\text{if a }3412\\ &\text{ occurrence ends at }b, \end{aligned}\\ b+1,&\text{otherwise}. \end{cases} \end{aligned} \tag{8}$$

Set $B(\epsilon)=1$, and let $\eta(\pi)$ indicate whether $\pi$ contains $231$. We shall prove that its allowable new last ranks are $1,\ldots,B(\pi)$ and that

$$B(\pi^{+a}a) =a+1-\mathbf1_{\{a=B(\pi)\}}\eta(\pi). \tag{9}$$

First, in a $213$-avoiding permutation ending in $b$, every inversion top exceeds $b$. Otherwise that inversion followed by $b$ would form $213$.

Appending rank $a$ preserves $213$-avoidance exactly when $a\le b+1$. If $a>b+1$, the old entries $b+1,b$ and the new entry form $213$. If $a\le b+1$, a new $213$ would come from an old inversion whose top is at most $b$, which is impossible.

A new $45123$ must have the new entry last. Thus it is equivalent to an old $3412$ occurrence, written in positional order as $u,v,x,y$, with

$$x<y<a\le u<v. \tag{10}$$

Every such inversion top $u$ exceeds $b$. Moreover, any old $3412$ occurrence has $y\ge b$: if $y<b$, its four entries followed by $b$ would already form $45123$. For $a\le b+1$, condition (10) can therefore hold exactly when $a=b+1$ and an old $3412$ ends at $b$. This proves the allowed-rank rule (8).

It remains to prove the update. Since the new last value is $a$, its new label is $a$ precisely when a new $3412$ ends there. Such an occurrence exists exactly when $\pi$ has entries $u,v,x$, in that positional order, satisfying

$$x<a\le u<v. \tag{11}$$

In particular, these old entries form $231$.

Suppose first that $a<B(\pi)$. Since $B(\pi)\le b+1$, we have $a\le b$. If $a=b$, condition (11) would give an old $3412$ ending at $b$, contradicting $a<B(\pi)$.

If $a<b$ and (11) holds, then $u>b$ by the inversion-top observation. Locate the old entry with value $a$. If it occurs before $x$, the entries $a,x,b$ form $213$. If it occurs after $x$, the entries $u,v,x,a,b$ form $45123$. Both are impossible. Thus no new $3412$ ends at $a$ when $a<B(\pi)$.

Now suppose $a=B(\pi)$ and $\pi$ contains $231$. If $B(\pi)=b$, an old $3412$ ending at $b$ supplies the first three entries in (11). If $B(\pi)=b+1$, take any old $231$ occurrence with first two values $u<v$. Its inversion top $u$ exceeds $b$, so the entries $u,v,b$ satisfy (11) with $a=b+1$. Conversely, if $\pi$ contains no $231$, (11) is impossible for every $a$. These cases prove (9). The empty prefix again gives label $2$ after its sole insertion.

6. Completion of the fourth bijection

We now match the two recursive constructions. Start with the empty word and permutation, both labelled $1$. Suppose $u$ and $\pi=H(u)$ have already been matched, with $L(u)=B(\pi)$.

Their indicators also agree:

$$\chi(u)=\eta(\pi). \tag{12}$$

Indeed, $\chi(u)=0$ means that $u$ is weakly increasing. By the third bijection, and the injectivity of $H$, this is equivalent to $\pi\in\mathfrak S(213,231)$. Since $\pi$ already avoids $213$, this is exactly $\eta(\pi)=0$.

The allowable next values coincide by (6) and (8). Equations (7), (9), and (12) show that the labels remain equal after each insertion. Induction therefore matches all $213$-avoiding restricted growth words with all permutations in $\mathcal C$. Every permutation in $\mathcal C$ is reached because deleting its last entry and standardizing gives a shorter member of $\mathcal C$; equation (1) reverses this deletion uniquely.

Finally, (4) identifies the word class with $A_0(213)$. This proves the fourth bijection and completes all four assertions. $\square$