Where the monotone pattern (mostly) rules
7 Where the monotone pattern (mostly) rules
Miklós Bóna
Department of Mathematics
University of Florida
Gainesville FL 32611-8105
bona@math.ufl.edu ∗
Abstract
We consider pattern containment and avoidance with a very tight
definition that was used first by Riordan more than 60 years ago. Us-
ing this definition, we prove the monotone pattern is easier to avoid
than almost any other pattern of the same length. We also show that
with this definition, almost all patterns of length k are avoided by the
same number of permutations of length n. The corresponding state-
ments are not known to be true for more relaxed definitions of pattern
containment. This is the first time we know of that expectations are
used to compare numbers of permutations avoiding certain patterns.
1 Introduction
The classic definition of pattern avoidance on permutations is as follows.
Let p = p1p2 · · · pn be a permutation, let k < n, and let q = q1q2 · · · qk be
another permutation. We say that p contains q as a pattern if there exists
a subsequence 1 ≤ i1 < i2 < · · · < ik ≤ n so that for all indices j and r, the
inequality qj < qr holds if and only if the inequality pij < pir holds. If p
does not contain q, then we say that p avoids q. In other words, p contains
q if p has a subsequence of entries, not necessarily in consecutive positions,
which relate to each other the same way as the entries of q do.
Classic pattern avoidance has been a rapidly developing field for the last
decade. One of the most fascinating subjects in this field was the enumera-
tion of permutations avoiding a given pattern. Let Sn(q) denote the number
of permutations of length n (or in what follows, n-permutations) that avoid
∗Partially supported by an NSA Young Investigator Award.
http://arxiv.org/abs/0704.1489v1
the pattern q, and let us consider the numbers Sn(q) for each pattern q of
length k. A very interesting and counter-intuitive phenomenon is that in
this multiset of k! numbers, the number Sn(q) will, in general, not be the
largest or the smallest number. There are several results on this fact (see
[1], [2] or [3]), but the phenomenon is still not perfectly well understood.
In 2001, Elizalde and Noy [4] proposed another definition of pattern con-
tainment. We will say that the permutation p = p1p2 · · · pn tightly contains
the permutation q = q1q2 · · · qk if there exists an index 0 ≤ i ≤ n− k so that
qj < qr if and only if pi+j < pi+r. In other words, for p to contain q, we
require that p has a consecutive string of entries that relate to each other
the same way the entries of q do. For instance, 246351 contains 132 (take
the second, third, and fifth entries, for instance), but it does not tightly con-
tain 132 since there are no three entries in consecutive positions in 246351
that would form a 132-pattern. If p does not tightly contain q, then we say
that p tightly avoids q. Let Tn(q) denote the number of n-permutations that
tightly avoid q. Elizalde and Noy conjectured in [4] that no pattern of length
k is tightly avoided by more n-permutations than the monotone pattern. In
other words, if q is a pattern of length k, then
Tn(q) ≤ Tn(12 · · · k). (1)
This conjecture is still open. (In the special case of k = 3, it was proved in
[4].) Still, it is worth pointing out that changing the definition of pattern
avoidance changed the status of the monotone pattern among all patterns
of the same length. With this definition, it is believed that the monotone
pattern is the easiest pattern to avoid.
This perceived change in the status of the monotone pattern led us to
the following direction of research. Let us take the idea of Elizalde and Noy
one step further, by restricting the notion of pattern containment further
as follows. Let p = p1p2 · · · pn be a permutation, let k < n, and let q =
q1q2 · · · qk be another permutation. We say that p very tightly contains q if
there is an index 0 ≤ i ≤ n− k and an integer 0 ≤ a ≤ n− k so that qj < qr
if and only if pi+j < pi+r, and,
{pi+1, pi+2, · · · , pi+k} = {a+ 1, a+ 2, · · · , a+ k}.
That is, p very tightly contains q if p tightly contains q and the entries of
p that form a copy of q are not just in consecutive positions, but they are
also consecutive as integers (in the sense that their set is an interval).
For example, 15324 tightly contains 132 (consider the first three entries),
but does not very tightly contain 132. On the other hand, 15324 very tightly
contains 213, as can be seen by considering the last three entries. If p does
not very tightly contain q, then we will say that p very tightly avoids q.
Note that in the special case when q is the monotone pattern, this notion
was studied before pattern avoidance became widely known. The literature
of permutations very tightly avoiding monotone patterns goes back at least
to [7]. More recent examples include [6] and [5]. However, we did not
find any examples where the notion was used in connection with any other
pattern.
Let Vn(q) denote the number of n-permutations that very tightly avoid q.
While we cannot prove that Vn(q) ≤ Vn(12 · · · k) for all patterns q of length
k, we will be able to prove that this inequality holds for most patterns q of
length k. As a byproduct, we will prove that for all k, there exists a set Wk
of patterns of length k so that limk→∞
= 1, and Vn(q) is identical for
all patterns q ∈ Wk(q). In other words, almost all patterns of length k are
equally difficult to very tightly avoid. There are no comparable statements
known for the other two discussed notions of pattern avoidance.
Our argument will be a probabilistic one. Once the framework is set
up, the computation will be elementary. However, this is the first time we
know of that expectations are successfully used to compare the number of
permutations avoiding a given pattern (admittedly, with a very restrictive
definition of pattern avoidance). We wonder whether more sophisticated
methods of enumeration could extend the reach of this technique to less
restrictive definitions of pattern avoidance.
2 A Probabilistic Argument
2.1 The outline of the argument
For the rest of this section, let k ≥ 3 be a fixed positive integer. Let
α = 12 · · · k, the monotone pattern of length k. Recall that Vn(α) is the
number of n-permutations very tightly avoiding α. Our goal is true prove
Vn(q) ≤ Vn(α)
for any pattern q of length k.
Let q be any pattern of length k. For a fixed positive integer n, let
Xn,q be the random variable counting the occurrences of q in a randomly
selected n-permutation. As the following straightforward proposition shows,
the expectation of Xn,q does not depend on q; it only depends on n, and the
length k of q.
Proposition 1 For any fixed n, and q ∈ Sk, we have
E(Xn,q) =
(n− k + 1)2
Proof: Let Xi be the indicator random variable of the event that the
string pi+1 · · · pi+k is a q-pattern in the very tight sense. Then E(Xi) =
P (pi+1 · · · pi+k ≃ q) =
n−k+1
, since there are n− k+1 favorable choices
for the set of the entries pi+1, · · · , pi+k, and there is 1/k! chance that their
pattern is q. Now note that E(Xn,q) =
i=0 Xi, and the statement is
proved by the linearity of expectation. ✸
Let pn,i,q be the probability that a randomly selected n-permutation
contains exactly i copies of q, and let Pn,i,q be the probability that a randomly
selected n-permutation contains at least i copies of q.
Set m = n− k + 1, and observe that no n-permutation can very tightly
contain more than m copies of any given pattern q of length k. Now note
that by the definition of expectation
E(Xn, q) =
ipn,i,q
pn,m−i,q
= pn,m,q + (pn,m,q + pn,m−1,q) + · · ·+ (pn,m,q + · · · + pn,1,q)
P (n, i, q).
By Proposition 1, we know that E(Xn,q) = E(Xn,α), and then previous
displayed equation implies that
P (n, i, q) =
P (n, i, α). (2)
So if we could show that for i ≥ 2, the inequality
P (n, i, q) ≤ P (n, i, α) (3)
holds, then (2) would imply that P (n, 1, q) ≥ P (n, 1, α), which is just what
we set out to prove.
The simple counting argument that we present in this paper will not
prove (2) for every pattern q. However, it will prove (2) for most patterns
q. We describe these patterns in the next subsection.
2.2 Condensible and Non-condensible Patterns
Let us assume that the permutation p = p1p2 · · · pn very tightly contains two
non-disjoint copies of the pattern q = q1q2 · · · qk. Let these two copies be q
and q(2), so that q(1) = pi+1pi+2 · · · pi+k and q
(2) = pi+j+1pi+j+2 · · · pi+j+k
for some j ∈ [1, k − 1]. Then |q(1) ∩ q(2)| = k − j + 1 = s. Furthermore,
since the set of entries of q(1) is an interval, and the set of entries of q(2) is
an interval, it follows that the set of entries of q(1) ∩ q(2) is also an interval.
So the rightmost s entries of q, and the leftmost s entries of q must form
identical patterns, and the respective sets of these entries must both be
intervals.
For obvious symmetry reasons, we can assume that q1 < qk. We claim
that then the rightmost s entries of q must also be the largest s entries of q.
This can be seen by considering q(1). Indeed, the set of these entries of q(1)
is the intersection of two intervals of the same length, and therefore, must
be an ending segment of the interval that starts on the left of the other. An
analogous argument, applied for q(2), shows that the leftmost s entries of q
must also be the smallest s entries of q.
The following Proposition collects the observations made in this subsec-
tion.
Proposition 2 Let p be a permutation that very tightly contains copies q(1)
and q(2) of the pattern q = q1q2 · · · qk. Let us assume that q1 < qk. Then
q(1) and q(2) are disjoint unless all of the following hold.
There exists a positive integer s ≤ k − 1 so that
1. the rightmost s entries of q are also the largest s entries of q, and the
leftmost s entries of q are also the smallest s entries of q, and
2. the pattern of the leftmost s entries of q is identical to the pattern of
the rightmost s entries of q.
It is easy to see that if q satisfies both of these criteria, then two very
tightly contained copies of q in p may indeed intersect. For example, the
pattern q = 2143 satisfies both of the above criteria with s = 2, and indeed,
214365 very tightly contains two intersecting copies of q, namely 2143 and
4365.
Definition 1 Let q be a pattern that satisfies both conditions of Proposition
2. Then we say that q is condensible.
It is not difficult to prove that almost all patterns of length k are non-
condensible. We do not want to break the course of our proof with this, so
we postpone this computation until the Appendix.
2.3 The Computational Part of the Proof
The following Lemma is the heart of our main result.
Lemma 1 Let q be a non-condensible pattern, and let i > 1. Then
P (n, i, q) ≤ P (n, i, α).
Proof: We point out that if n < ik, then the statement is clearly true.
Indeed, P (n, i, q) = 0 since any two copies of q in an n-permutation p would
have to be disjoint, and n is too small for that. Therefore, in the rest of the
proof, we can assume that n ≥ ik. For k ≤ 2, the statement is trivial, so we
assume k ≥ 3 as well.
First, we prove a lower bound on P (n, i, α). The number of n-permutations
very tightly containing i copies of α is at least as large as the number of
n-permutations very tightly containing the pattern 12 · · · (i + k − 1). The
latter is at least as large as the number of n-permutations that very tightly
contain a 12 · · · (i + k − 1)-pattern in their first i+ k − 1 positions, that is,
(n− k − i+ 2) · (n− k − i+ 1)! = (n− k − i+ 2)!. Therefore,
(n− k − i+ 2)!
≤ P (n, i, α). (4)
We are now going to find an upper bound for P (n, i, q). Let S be an i-
element subset of [n] so that the elements of S can be the starting positions
of i (necessarily disjoint) very tight copies of q in an n-permutation. If
S = {s1, s2, · · · , si}, then this is equivalent to saying that
1 ≤ s1 < s2 − k+ 1 ≤ s3 − 2k + 2 ≤ · · · ≤ si − (i− 1)(k − 1) ≤ n− i(k − 1).
Therefore, there are
n−i(k−1)
possibilities for S. Now let AS be the event
that in a random permutation p = p1 · · · pn, the subsequence pjpj+1 · · · pj+k−1
is a very tight q-subsequence for all j ∈ S. Let Ai,q be the event that p
contains at least i very tight copies of q. Then P (Ai,q) = P (n, i, q). Fur-
thermore,
Ai,q = ∪SAS ,
where the union is taken over all
n−i(k−1)
possible subsets for S. Therefore,
P (n, i, q) = P (Ai,q) ≤
P (AS). (5)
Let us now compute P (AS). We will see that this probability does not de-
pend on the choice of S. Indeed, just as there are
n−i(k−1)
possibilities for
S, there are
n−i(k−1)
possibilities for the entries in the positions belonging
to S. Once those entries are known, the rest of the q-patterns starting in
those entries are determined, and there are (n− ik)! possibilities for the rest
of the permutation. This shows that P (AS) =
n−i(k−1)
(n − ik)! 1
for all
S. Therefore, (5) implies
P (n, i, q) ≤
n− i(k − 1)
(n− ik)!
. (6)
Comparing (6) and (4), we see that our lemma will be proved if we show
that for i > 1, the inequality
n− i(k − 1)
(n− ik)! ≤ (n− i− k + 2)!,
or, equivalently,
(n− i(k − 1))i ≤ i!
2(n− k− i+ 2)(n− k− i+ 1) · · · (n− i(k − 1) + 1)) (7)
holds. Where (z)j = z(z−1) · · · (z− j+1). Note that the left-hand side has
i factors, while the right-hand side, not counting i!2, has (k − 1)(i − 1) >
i factors, each of which are larger than the factors of the left-hand side.
Therefore, (7) holds, and the Lemma is proved. ✸
The proof of our main result is now immediate.
Theorem 1 Let q be any pattern of length k. Then
Vn(q) ≤ Vn(α).
Proof: Lemma 1 and formula (2) together imply that P (n, 1, q) ≥ P (n, 1, α),
which means that there are at least as many n-permutations that very tightly
contain q as n-permutations that very tightly contain α. ✸
2.4 A Result on Non-condensible Patterns
We have seen in Proposition 2 that if q is non-condensible and q1 < qk,
then any two copies of q contained in a given permutation p are disjoint.
Therefore, the number of n-permutations that very tightly avoid q can be
computed by the Principle of Inclusion-Exclusion. Indeed, in this case, the
following holds.
Proposition 3 Let q be a non-condensible pattern. Then
Vn(q) = n!−
⌊n/k⌋
n− i(k − 1)
(n− ik)!.
In particular, Vn(q) does not depend on the choice of q.
Proof: In the proof of Lemma 1, more precisely, in our argument showing
that (6) holds, we showed that there are
n−i(k−1)
ways to choose an i-
element set of positions that can be the starting positions of i disjoint very
tight copies of q, and there are
n−i(k−1)
ways to choose the sets of entries
forming these same copies. Once these choices are made, the rest of the
permutation can be chosen in (n− ik)! ways. The statement now follows by
the Principle of Inclusion-Exclusion. ✸
As we said, we will prove in Proposition 4 that almost all patterns are
non-condensible. Note that nothing comparable is known for the other two
notions of pattern avoidance. Numerical evidence suggests that similarly
strong results will probably not hold if the traditional definition or the tight
definition is used.
3 Further Directions
The novelty of this paper, beside the notion of very tight containment, was
the application of expectations to compare the numbers of permutations
avoiding two patterns. The computations themselves were elementary. This
leads to the following question.
Question 1 Is it possible to apply our method to compare the numbers Tn(q)
and Tn(α), or the numbers Sn(q) and Sn(α), for at least some patterns q?
As we used a very simple estimate in our proof of Lemma 1, there may
be room for improvement at that point.
There are several natural questions that can be raised about the enumer-
ation of permutations that very tightly avoid a pattern. Let us recall that
we proved a formula for Vn(q) for the overwhelming majority of patterns
q, namely for non-condensible patterns. A formula for Vn(α), where α is
the monotone pattern, can be found in [6] and [5]. This raises the following
question.
Question 2 Are there other patterns q for which Vn(q) can be explicitly
determined?
Let us call patterns q and q′ very tightly equivalent if Vn(q) = Vn(q
′) for
all n. We have seen that almost all patterns of length k are very tightly
equivalent. This raises the following questions.
Question 3 How many equivalence classes are there for very tight patterns
of length k?
Question 4 Can we say anything about the same topic for tight pattern
containment, or traditional pattern containment? If equivalence is defined
for them in an analogous way, how many equivalence classes will be formed,
(for patterns of length k) and how large will the largest one be?
4 Appendix
In this section we prove the following simple fact.
Proposition 4 Let hn be the number of condensible permutations of length
n. Then
Proof: We prove that another class of permutations, one that contains
all condensible permutations, is also very small. Let an be the number of
decomposable permutations, that is, permutations p1p2 · · · pn for which is
there is an index i so that pj < pm if j ≤ i < m. In other words, p can be
cut into two parts so that everything before the cut is less than everything
after the cut. (Note that if a permutation is not decomposable, then it is
called indecomposable, and Exercise 1.32 of [8] contains more information
about these permutations.)
Counting according to the index i of the above definition, we see that
i!(n − i)!
where in the last step we used the well-known unimodal property of binomial
coefficient, in particular the inequality that
if 2 ≤ i ≤ n− 2.
Therefore, an/n! converges to 0 as n goes to infinity. Clearly, all con-
densible patterns are decomposable since their first i entries are also their i
smallest entries, so our claim follows. ✸
References
[1] M. Bóna, Combinatorics of Permutations, CRC Press, 2004.
[2] M. Bóna, The limit of a Stanley-Wilf sequence is not always rational,
and layered patterns beat monotone patterns, J. Combin. Theory Ser.
A 110 (2005) no. 2, 223–235.
[3] New Records on Stanley-Wilf Limits. European Journal of Combina-
torics, 28 (2007), vol. 1, 75-85.
[4] S. Elizalde; M. Noy, Consecutive patterns in permutations. Formal
power series and algebraic combinatorics (Scottsdale, AZ, 2001). Adv.
in Appl. Math. 30 (2003), no. 1-2, 110–125.
[5] D. M. Jackson; R. C. Reid, A note on permutations without runs of
given length, Aequationes Math. 17 (1978), no. 2-3, 336-343.
[6] D. M. Jackson; J. W. Reilly, Permutations with a prescribed number
of p-runs. Ars Combinatoria 1 (1976), no. 1, 297-305.
[7] J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc.,
51 (1945), 745-748.
[8] R. Stanley, Enumerative Combinatorics, Volume 1. Cambridge Uni-
versity Press, Cambridge UK, second edition 1997.
	Introduction
	A Probabilistic Argument
	The outline of the argument
	Condensible and Non-condensible Patterns
	The Computational Part of the Proof
	A Result on Non-condensible Patterns
	Further Directions
	Appendix
