## Return to Question

3 edited tags
2 fixed LaTeX

Let $S_{n^+1}$ S_{n^2+1}$be permutations of length$n^2+1$. By Erdos-Szekeres Theorem. any$s \in S_{n^+1}$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}$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^+1 {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}$, 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$E_{n+1}$

1

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

Let $S_{n^+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^+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^+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$