# Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$

Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$.

For example the permutation 45123 contains only $1$ monotone subsequence of length $3$ (namely 123), so it is a minimal case for $k =3$, $n=5$: any permutation of length $5$ contains at least one monotone subsequence of length $3$ by the Erdős-Szekeres theorem.

Problem 1 Can we find such permutation when $n$ becomes very large with respect to $k$?

Problem 2 Moreover can we calculate their proportion in $S_n$?

By "$n$ is very large", I mean $n>\mathrm{poly}(k)$

For example for 3 monotone subsequence (the following result lacks rigorous proof)
The 123456, 1234567 and 12345678 are trivial maximal cases as they contain ${n \choose 3}$ monotone sequence at length $3$

• when $n=6$ one of the minimal cases is 321654 containing $2$ monotone subsequences of length $3$. They are 321 and 654.

• when $n=7$ one of the seeming minimal cases is 4321765 containing $5$ monotone subsequences of length $3$ They are 432 431 421 321 and 765.

• when $n=8$ one of the seeming minimal cases is 43218765 containing $8$ monotone subsequences of length $3$ They are 432 431 421 321 765 876 875 and 865.

What are the minimal cases when $n>8$? Can we explicitly give the minimal case and give the number of monotone subsequence $k$ contained in the minimal case ?

If possible, I hope we can specialize the solution to some fixed position in the permutation. Suppose the 1st 3rd 5th 7th number of a permutation consists of a monotone sequence,can we design a minima permutation for such condition?

Hope you have some idea for this problem.

Observe that the extremal Erdős-Szekeres cases have a zero proportional compared to $n!$ when $n$ becomes infinite.

-
Since we know that the Robinson Stone Correspondence from permutations to Young Tableau. How can the structure of Young Tableau can help us on this subject – Yao Wang Feb 15 '12 at 3:23
I think you mean the Robinson-Schensted correspondence. – Marc van Leeuwen Feb 15 '12 at 12:42
Yeah，you are right. Thanks for comment. Any related research would be precious. – Yao Wang Feb 16 '12 at 20:18
Your cases $n=7,8$ are certainly not minimal; up to $n=9$ one can avoid monotone sequences of length $4$, for instance $321654978$ or $741852963$. Also please state a precise question. – Marc van Leeuwen Feb 18 '12 at 9:57
@Marc van Leeuwen The minimal case mentioned is the permutation $S_n$ itself.The \emph{number} of monotone subsequence at length 3 matters, not the \emph{length} of the longest monotone subsequence. I call the my examples as minimal case for they \emph{have fewest monotone sequence at length \mathbf{3},not at other length such as 4 or 5 }. Maybe my english is not pretty enough to describe my question. – Yao Wang Feb 21 '12 at 6:38

The question is not very clear what it means by a minimum case for 3-monotone sequence; it seems that it means this is a case where the longest monotone sequence is as short as it can be: no permutation of $5$ has only monotone sequences of length${}<3$. By the Erdős–Szekeres theorem, whenever $n>(k-1)^2$ every permutation of $n$ has at least one monotone sequence of length $k$.
In fact for every $n$ with $(k-1)^2<n\leq k^2$, one can find all permutations for which the maximal length monotone subsequences are of length $k$ by first forming all the partitions $\lambda$ of $n$ into at most $k$ parts of size at most $k$, for each such $\lambda$ take all pairs of standard Young tableaux $P,Q$ of shape $\lambda$, and apply the inverse Schensted correspondence ot $(P,Q)$. This gives quite a lot of permutations, but I would not be surprised if their proportion of all $n!$ permutations nevertheless goes to $0$ as $n\to\infty$ (probabilists almost certainly know the answer to this question;-).
As for permutations where the maximal length monotone subsequence is both minimal and unique, these are of course much more rare, and certainly don't exist for every $n$. However they do exist for $n=k^2+1$, where one has \begin{align} (&k,k-1,\ldots,1\\ ,&2k,2k-1\ldots,k+1\\,&3k,\ldots,2k+1\\ &\ldots\\,&k^2-k,\ldots,(k-1)k+1\\ ,& k^2+1,k^2,k^2-1,\ldots k^2-k+1)\end{align} whose unique monotone subsequence of length $k+1$ is formed by its final portion.
Thanks for your answer very much. But as we know the Erdos Szekeres cases. I mean when n is very large,i.e. $n> k^k$. Thus, inevitably many monotone sequence appeared – Yao Wang Feb 17 '12 at 19:25
d。Maybe I should show a case that what will happen when n becomes larger than $(k-1)^2+1$ – Yao Wang Feb 17 '12 at 19:32