Counting Selections of Entries such having an Extremal Permutation of length n^2+1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T04:44:43Z http://mathoverflow.net/feeds/question/91959 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91959/counting-selections-of-entries-such-having-an-extremal-permutation-of-length-n2 Counting Selections of Entries such having an Extremal Permutation of length n^2+1 WangYao 2012-03-22T22:52:41Z 2012-03-23T21:07:08Z <p>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$.</p> <p>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}$.</p> <p>For example: Let <code>$E_4=\{1,2,3,8\}$</code></p> <p>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)$.</p> <p>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.</p> <p>The problem is: Considering the all ${n^2+1 \choose n+1}$ entries set $E_{n+1}$s how can we count </p> <p>THE NUMBER OF SUCH $E$s HAVING AN EXTREMAL PERMUTATION?</p> <p>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. </p> <p>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}$. </p> <p>Any suggestion or links to counting method would do much help.</p> <p>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}$</p>