9
$\begingroup$

Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another family of permutations.

An interval in the permutation $\pi$ (thought of in one-line notation) is a contiguous sequence of entries which is also contiguous in value. For example, the entries $43$ form an interval in the permutation $514362$. Every permutation of length $n$ has trivial intervals of lengths $0$, $1$, and $n$, and permutations with only these trivial intervals are (sometimes) called simple.

Like fixed points, it can be shown that the number of nontrivial intervals in a random permutation is Poisson distributed (see this paper by Corteel, Louchard, and Pemantle), although unlike fixed points, the expected number of nontrivial intervals in a random permutation is $2$. It follows that (in the limit) the proportion of simple permutations is $1/e^2$.

Is there a "non-enumerative" proof that a positive proportion of permutations are simple?

$\endgroup$

1 Answer 1

6
$\begingroup$

I think the main idea of Brendan McKay's answer to Terence Tao's question still works. It's a bit more complicated (and less non-enumerative), but still "robust" in the sense of Tao's question.

First one should somehow "estimate away" those permutations that have an interval of length 3 or more. The proportion of such permutations is only $O(1/n)$.

Then, since the average number of intervals of length 2 is 2, it suffices to show that (i) there can't be many more permutations with 1 interval than with none, and (ii) there can't be many more permutations with 2 intervals than with 1.

There is a variety of ways to define a "switching operation" that provides (up to a $O(1/n)$ error) the necessary comparisons. For instance, consider the operation of taking a symbol that belongs to an interval of length 2 and switching it with the first symbol. The inverse operation is to look at the first symbol (say $i$), and switch it with a neighbor of $i-1$ or $i+1$.

For a permutation with $k$ intervals (of length 2 and disjoint), there are (in general) $2k$ ways of performing the "interval destroying" operation, and, regardless of $k$, 4 ways of performing the "interval creating" inverse. Taking $k=1$ this shows that asymptotically there are only twice as many permutations with one interval as with none, and with $k=2$ it shows that there are roughly as many permutations with two intervals as with one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.