Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two subsequences $a, b$ of $\sigma$ such that:
- $a$ is a longest increasing subsequence of $\sigma$,
- $b$ is a longest decreasing subsequence of $\sigma$,
- $a$ and $b$ are disjoint.
The shortest permutations with this property are $(2, 4, 1, 3)$ and $(3, 1, 4, 2)$. Say, for the former, we can choose $a = (2, 3)$ and $b = (4, 1)$.
I am interested in the size of $A_n$ as a function of $n$. The sequence $|A_1|, |A_2|, \ldots$ starts with $0, 0, 0, 2, 16, 124, 1012, 9060, 88550, 943050, 10879550$. I was not able to locate this or associated sequences in OEIS. I'm curious whether this sequence had been studied before, and if it can be efficiently computed, whether with a formula or a concise polynomial-time algorithm.
A particular aspect I'd like to focus on is this: define $\tau(n) = |A_n| / |S_n|$ — proportion of $n$-permutations with the property above. It appears that $\tau(n)$ steadily grows towards some limit: for instance, enumeration yields $\tau(10) \approx 0.26$, and Monte-Carlo simulations suggest that $\tau(100) \approx 0.41$, $\tau(1000) \approx 0.44$, and $\tau(10000) \approx 0.46$. A reasonable guess for $\alpha = \lim_{n \to \infty} \tau(n)$ is $1/2$, but I have very poor understanding of why $A_n$ has this size, instead of, say, vanishing or devouring most of $S_n$.
To sum up, my questions are:
- What is known about the sequence $|A_n|$? Can it be efficiently computed?
- Is $\alpha = \lim_{n \to \infty} \tau(n)$ well-defined? Is it true that $\tau(n)$ is strictly increasing, at least for sufficiently large $n$?
- What are non-trivial bounds on $ \alpha$? Is $\alpha = 1/2$? If not, what is the value of $\alpha$?
Outside of computational experiments, I tried some basic tools like RS correspondence. All I got is that the property doesn't depend only on the shape of the correponding diagrams. I'm not very familiar with anything deeper, and will be grateful for references that might be relevant to the question.
