Let $n\geq 1$ be a positive integer and let $S_n$ be the set of permutations of $\{1, \dots, n\}$ (thought of as non-repeating, exhaustive sequences of elements of $\{1, \dots, n\}$. Let $2 \leq k \leq n$. Define $H_n(k)$ as the number of elements of $S_n$ which do not have an increasing subsequence of $k$ consecutive terms. For instance, if $k=2$ then $H_n(2)$ is the number of permutations with no two consecutive increasing terms - in other words $H_n(2)$ is the number of decreasing permutations, so $H_n(2)=1$. At the other extreme, $H_n(n) = n!-1$, because there is only one permutation with $n$ consecutive increasing terms
I am interested in an asymptotic expression for $H_k(n)$. More precisely, I would like to know, as a function of $n$, the minimal $k=k(n)$ for which $H_k(n)/n! > 0.95$. There are exact formulas for $H_k(n)$ in the literature (for instance in this paper : http://arxiv.org/abs/1504.02513) but these are not helpful for estimating $H_k(n)$. Any help much appreciated!