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. 
 A: 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.
