# Counting Selections of Entries such having an Extremal Permutation of length n^2+1

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

-
Can you add an example of a sequence that is not included and explain why? –  Brendan McKay Mar 22 '12 at 23:59
Proof for 1,2,3,9 does not has an extremal permutation. w.l.o.g. suppose 1,2,3,9 does has such ex permutation and the monotone subsequence is increasing. Then we delete the 9th item of the ex sequence. Observe that the result sequence has no monosubseqence longer than 3. then we can seperate it to 3 disjoint increasing subsequence. A1 A2 A3. Since 1 ,2,3,9 is the longest monotone subsequence, then we have all the item betweet 3rd and 9th smaller than 3rd. then we have either A2 or A3 is in the zone between 3rd and 9th. thus either A2,9th or A3 9th is also an monosubseqence. –  WangYao Mar 23 '12 at 7:24
The proof is a little rough,but the separation could be find in the extremal combinitorics book 's Chapter Parity Ordered Set 's last exercise. –  WangYao Mar 23 '12 at 7:35