Powers of permutations that avoid chains of patterns

NEW

Problem: For $n\ge2$, let $\mathcal S_n$ be the symmetric group. A permutation $\rho$ avoids the consecutive pattern $\overline{213}$ if there is no $i$ with

$$\rho_{i+1}<\rho_i<\rho_{i+2}.$$

A permutation $\pi\in\mathcal S_n$ is unimodal if its one-line form increases up to $n$ and then decreases; equivalently, it avoids the classical patterns $213$ and $312$. The conjecture is:

$$\#\{\pi\in\mathcal S_n:\pi\text{ is unimodal and }\pi^2\text{ avoids }\overline{213}\} =2^{n-2}+n-1.$$

If interpreted at $n=1$, the displayed formula gives $1/2$ while the actual count is $1$, so the natural intended range is $n\ge2$.

Result: The conjecture is true for all $n\ge2$.

Proof. Every unimodal $\pi\in\mathcal S_n$ is uniquely determined by the set $B\subseteq[n-1]$ of entries lying to the right of $n$:

$$\pi=a_1a_2\cdots a_k\, n\, b_m b_{m-1}\cdots b_1,$$

where $A=[n-1]\setminus B=\{a_1<\cdots<a_k\}$ and $B=\{b_1<\cdots<b_m\}$.

Let $p=k+1$, the position of $n$, and let $q=\pi^2$, so $q_i=\pi_{\pi_i}$.

For any consecutive block $q_iq_{i+1}q_{i+2}$, put

$$x=\pi_i,\quad y=\pi_{i+1},\quad z=\pi_{i+2}.$$

If $i\le p-2$, then $x<y<z$. A $213$-pattern in $q_iq_{i+1}q_{i+2}$ would therefore be a classical $213$-pattern in $\pi_x\pi_y\pi_z$, impossible since $\pi$ is unimodal. If $i\ge p$, then $x>y>z$. A $213$-pattern in $q_iq_{i+1}q_{i+2}$ would become a classical $312$-pattern in $\pi_z\pi_y\pi_x$, also impossible. Hence the only possible consecutive $213$ in $q$ is the central block

$$q_{p-1}q_pq_{p+1}=\pi_{a_k}\,\pi_n\,\pi_{b_m},$$

when both sides exist.

Now $\pi_n=b_1$. If $n-1\in A$, then $a_k=n-1$. If $m\ge2$, then

$$\pi_{a_k}=\pi_{n-1}=b_2,$$

and one checks directly that $\pi_{b_m}>b_2$. Thus the central block is

$$b_2,\ b_1,\ \pi_{b_m},$$

with $b_1<b_2<\pi_{b_m}$, hence it is a consecutive $213$.

If $n-1\notin A$, equivalently $n-1\in B$, then the central block is never $213$. Indeed, if $m\ge2$, then $\pi_{b_m}=\pi_{n-1}=b_2$, and $\pi_{a_k}$ is not strictly between $b_1$ and $b_2$: it is either $\le b_1$, equal to $n$, or another element of $B$, hence $\ge b_2$.

Therefore $\pi^2$ avoids $\overline{213}$ exactly when either $n-1\in B$, or $|B|\le1$.

Counting such $B\subseteq[n-1]$:

• $n-1\in B$: $2^{n-2}$ choices;
• $n-1\notin B$ and $|B|\le1$: $1+(n-2)=n-1$ choices.

Thus the total is

$$2^{n-2}+n-1.$$

Audit: the proof uses exactly the reconstructed definitions of unimodal permutations, group square, and consecutive $\overline{213}$-avoidance; the only boundary repair is the necessary range $n\ge2$.

Citation: No prior resolution is used here. Source of the conjecture and terminology: Kassie Archer and Aaron Geary, “Powers of permutations that avoid chains of patterns,” arXiv:2312.14351.