Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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