Greatest number of occurrences of the pattern 4213 in a permutation.

Question

Statistic St000750 in the FindStat database is a map $\operatorname{St000750} \colon S_n \rightarrow \mathbb N_{\geq 0}$ given by

The number of occurrences of the pattern $4213$ in a permutation.

This is the number of length-4 substrings such that the first number is largest, the second is third-largest, the third is smallest, and the fourth is second-largest. For example, the permutation $\pi = 563214$ has $\operatorname{St000750}(\pi) = 6$ occurrences of this pattern: $$5324, 5314, 5214, 6324, 6314, \text{and}\ 6214.$$

---

I'm interested in computing$$ a(n) = \max \{ \operatorname{St000750}(\pi) : \pi \in S_n\} $$ By brute-forcing $0 \leq n \leq 9$, I get that

• $a(0) = a(1) = a(2) = a(3) = 0$,
• $a(4) = 1$,
• $a(5) = 3$,
• $a(6) = 6$,
• $a(7) = 13$,
• $a(8) = 24$, and
• $a(9) = 40$.

Moreover, this sequence does not appear in the On-Line Encyclopedia of Integer Sequences.

However, an analogous sequence for the pattern $132$ is A061061, with a simple formula: $A061061(n) = \max\{A061061(k) + k\binom{n-k}{2} : 1 \leq k < n\}$.

Is there a way to compute this sequence which is better than brute force? If not, how can you construct a better upper bound than $a(n) \leq \binom{n}{4}$?

Answer 1

Proposition 3.1 in the paper On Packing Densities of Permutations by Albert, Atkinson, Handley, Holton, and Stromquist proves that the packing density of the $1342$ pattern (the limit of $a(n)/\binom n4$) is between $0.19657$ and $\frac29$, with an explicit upper bound of $\frac{n^2(n+1)^2}{108}$ on $a(n)$. This is also an upper bound for the $4213$ pattern, which is symmetric to it. Theorem 4 in Sliacan and Stromquist's Improving bounds on packing densities of 4-point permutations improves the bounds on the packing density to the interval $$[0.198836597,0.198837287]$$ almost but not quite solving the problem. It doesn't look like anyone's finished it off since then.

I'm going to keep my earlier answer, which shows an upper bound of about $0.77\binom n4$, below, just because what else am I going to do with it.

---

The number of $213$ patterns (like $132$ patterns) in a permutation of length $n$ is at most $\frac{2 \sqrt 3 - 3}{6} n^3$, and we can use that to bound the number of $4213$ patterns.

Let's divide the possible $4213$ patterns into two types:

1. Ones in which the first number comes from the first quarter of the permutation, and the rest come from the last three quarters. There are $\frac n4 \binom{3n/4}{3}$ substrings of this form, but we'll bound the number of them that form $4213$ patterns.
2. All others. There are $\binom n4 - \frac n4 \binom{3n/4}{3}$ substrings of this form, and to get an upper bound we'll just assume that all of them form $4213$ patterns.

For the first type, if the substring forms a $4213$ pattern, its last three numbers form a $213$ pattern, so there can be at most $\frac{2\sqrt3 - 3}{6} (\frac{3n}{4})^3$ ways to choose those last three numbers; $\frac{2\sqrt3 - 3}{6} \frac n4 (\frac{3n}{4})^3$ patterns overall.

So this gives us an upper bound of $\binom n4 - \frac n4 \binom{3n/4}{3} + \frac{2\sqrt3 - 3}{6} \frac n4 (\frac{3n}{4})^3$. Asymptotically, this is $(\frac{27\sqrt3 - 22}{32} + o(1)) \binom n4$, or about $0.77\binom n4$.

Answer 2

You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{p,v}$ indicate whether position $p\in\{1,\dots,n\}$ takes value $v\in\{1,\dots,n\}$. Let integer decision variable $y_p$ be the value in position $p$. Let $Q=\{q\subset \{1,\dots,n\}:|q|=4\}$ be the $4$-subsets of positions. For $q=\{q_1,q_2,q_3,q_4\}\in Q$, let binary decision variable $z_q$ indicate whether the values taken by the four positions in $q$ match the pattern 4213. The problem is to maximize $\sum_{q\in Q} z_q$ subject to linear constraints \begin{align} \sum_{p=1}^n x_{p,v} &= 1 &&\text{for $v\in\{1,\dots,n\}$} \tag1 \\ \sum_{v=1}^n x_{p,v} &= 1 &&\text{for $p\in\{1,\dots,n\}$} \tag2 \\ \sum_{v=1}^n v\cdot x_{p,v} &= y_p &&\text{for $p\in\{1,\dots,n\}$} \tag3 \\ y_{q_3} + 1 - y_{q_2} &\le n(1-z_q) &&\text{for $q\in Q$} \tag4 \\ y_{q_2} + 1 - y_{q_4} &\le n(1-z_q) &&\text{for $q\in Q$} \tag5 \\ y_{q_4} + 1 - y_{q_1} &\le n(1-z_q) &&\text{for $q\in Q$} \tag6 \\ \end{align} Constraint $(1)$ assigns each value to exactly one position. Constraint $(2)$ assigns each position to exactly one value. Constraint $(3)$ enforces $x_{p,v}=1 \iff y_p = v$. Constraints $(4)$, $(5)$, and $(6)$ enforce $z_q=1 \implies y_{q_3} < y_{q_2} < y_{q_4} < y_{q_1}$, as required by pattern 4213.

I confirmed your values of $a(n)$, and the next three are $a(10)=62$, $a(11)=96$, and $a(12)=138$.

The linear programming relaxation appears to yield upper bound $\binom{n}{4}(1-1/n)$ for $n \ge 5$.

Answer 3

The corresponding OEIS sequence now exists: A342646. Bert Dobbelaere calculated a(13) - a(15): 192, 264, 354