Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$. Say a permutation $s$ of length $n^2+1$ is an extremal permutation if it contains exactly $1$ monotone subsequence of length $n+1$.
We say for $E_{n+1}$ denoting a set of $n+1$ entries of $S$. We say an entries set $E_{n+1}$ having a extremal permutation $s_{n^2+1}$ if the very monotone subsequence of length $n+1$ of such $s_{n^2+1}$ is located at this $E_{n+1}$.
For example:
Let $E_4=\{1,2,3,8\}$
This $E_4$ has an extremal permutations $s_{10}=(4,3,2,7,6,10,9,1,5,8)$. The monotone subsequence is $(4,3,2,1)$ which is located at $E_4=(1,2,3,8)$.
I can prove that there are many $E_{n+1}$ that do not have an extremal permutation $s_{n^2+1}$.Also I have made a polynomial time algorithm to decide if such $E_{n+1}$ have or not have such extremal permutation.
The problem is: Considering the all ${n^2+1 \choose n+1} $ entries set $E_{n+1}$s how can we count
THE NUMBER OF SUCH $E$s HAVING AN EXTREMAL PERMUTATION?
First ,let's consider a simpler case. I have proved that if $1$ is in $E_{n+1}$, then $2$ must be in $E_{n+1}$ if $E_{n+1}$ having an extremal permutation.
OK, now I can prove that if both $1$ and $2$ is in $E_{n+1}$, then we could pick $e_3\leq n+2$ and $e_i \leq (i-2)n+2$ to form an $E_{n+1}$ such have a extremal permutation. But I do not know to compute the number of such $E_{n+1}$.
Any suggestion or links to counting method would do much help.
I am think the counting the number of all $E_{n+1}$ is $#P-hard$, but intuitively, there should exist an recursive formula counting $E_{n+1}$
