Greatest number of occurrences of the pattern 4213 in a permutation. 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}$?

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$.
