4
$\begingroup$

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:

  1. What is known about the sequence $|A_n|$? Can it be efficiently computed?
  2. 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$?
  3. 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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Here are some heuristic comments. A longest increasing (or decreasing) sequence in a typical permutation of size $n$ has length on the order of $\sqrt{n}$. If the LIS and LDS occurred in random positions, we would expect their intersection to have cardinality on the order of $\sqrt{n} \sqrt{n} / n = 1$. Of course, an increasing and a decreasing subsequence can have intersection of size at most one. And you are asking for the permutations where the LIS and LDS have no intersection. So maybe this makes it seem reasonable that about half have intersection size 0, and half size 1. $\endgroup$
    – Sam Hopkins
    Commented Oct 14 at 0:32
  • $\begingroup$ @SamHopkins There is a way how this argument makes sense, of course. Still, even if we assume that LIS and LDS are unique and equidistributed among subsets of size $2 \sqrt n$, the probability of them being disjoint is only about $0.0183$ (based on a quick experiment). Probably the biggest contributor to the discrepancy is the fact that we only need one disjoint LIS-LDS pair, whereas there can be a lot of options for each. $\endgroup$
    – Mikhail Tikhomirov
    Commented Oct 14 at 0:52
  • $\begingroup$ Feels like there's a secondary contributor here: LIS will tend to be made up of smaller numbers earlier in the permutation and larger numbers later, LDS the reverse. This should lead them to be less likely to overlap than uniform random sets $\endgroup$
    – Kevin P. Costello
    Commented Oct 14 at 2:32

0

Reset to default

You must log in to answer this question.