On the Stanley-Wilf conjecture for the number of permutations avoiding a given

pattern

Richard Arratia

Department of Mathematics University of Southern California Los Angeles, CA 90089-1113

              email:  rarratia@math.usc.edu

Submitted: July 27, 1999; Accepted: August 25, 1999.

Abstract. Consider, for a permutation σ ∈ S_{k}, the number F (n, σ) of permutations in S_{n} which avoid σ as a subpattern. The conjecture of Stanley and Wilf is that for every σ there is a constant c(σ) < ∞ such that for all n, F (n, σ) ≤ c(σ)^{n}. All the recent work on this problem also mentions the “stronger conjecture” that for every σ, the limit of F (n, σ)^{1/n} exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity.

We also discuss n-permutations, containing all σ ∈ S_{k} as subpatterns. We prove that this can be achieved with n = k^{2}, we conjecture that asymptotically n ∼ (k/e)^{2} is the best achievable, and we present Noga Alon’s conjecture that n ∼ (k/2)^{2} is the threshold for random permutations.

Mathematics Subject Classification: 05A05,05A16.

1. Introduction

Consider, for a permutation σ ∈ S_{k}, the set A(n, σ) of permutations τ ∈ S_{n} which avoid σ as a subpattern, and its cardinality, F (n, σ) := |A(n, σ) |. Recall that “τ contains σ” as a subpattern means that there exist 1 ≤ x_{1} < x_{2} < ⋯ < x_{k} ≤ n such that for 1 ≤ i, j ≤ k,

(1) τ(x_{i}) < τ(x_{j}) if and only if σ(i) < σ(j).

An outstanding conjecture is that for every σ there is a finite constant c(σ) such that for all n, F (n, σ) ≤ c(σ)^{n}. In the 1997 Ph.D. thesis of Bóna [2], supervised by

The author thanks Noga Alon, Béla Bollobás, and Miklós Bóna for discussions of this problem.

Stanley, this conjecture is attributed to “Wilf and Stanley [oral communication] from 1990.” All the recent work on this problem also mentions the “stronger conjecture” that for every σ, the limit of F (n, σ)^{1/n} exists and is finite. According to Wilf (private communication, 1999) the original conjecture was of this latter form.

In this short note we give, as Theorem 1, a simple argument, involving subadditivity, which shows that the two versions of the conjecture are equivalent.

Here is some background information on the current status of the Stanley-Wilf conjecture. Represent σ ∈ S_{k} by the word σ(1) σ(2) ⋯ σ(k). For the case of the increasing pattern, i.e the identity permutation, σ = 12 ⋯ k, the upper bound F (n, σ) ≤ ((k − 1)^{2})^{n} is well known, and follows from the Robinson-Schensted-Knuth correspondence; also Regev [7] gives the asymptotics

F (n, 12 ⋯ k) ∼ λ_{k} \frac{(k − 1)^{2n}}{n^{k(k−2)/2}} ,

with an explicit constant λ_{k}. Simion and Schmidt [8] give a bijective proof that for each σ ∈ S_{3}, F (n, σ) = \frac{1}{n+1} \binom{2n}{n}; see also Knuth [6], section 2.2.1, exercises.

For σ = 1342, Bóna [2] finds the explicit generating function for F (n, σ), showing that for all n, F (n, 1342) < 8^{n}, and lim F (n, 1342)^{1/n} = 8. Note in contrast that lim F (n, 1234)^{1/n} = 9. Bóna observes that indeed, in all cases for which lim F (n, σ)^{1/n} is known explicitly, it is an integer! For the special class of “layered patterns,” such as σ = 67 345 12, Bóna [3] has shown that sup_{n} F (n, σ)^{1/n} is finite. Alon and Friedgut [1] prove an upper bound for the general case which is tantalizingly close to the goal; they relate the problem to a result on generalized Davenport-Schinzel sequences from Klazar [5], and show that for every σ ∈ S_{k} there exists c(σ) < ∞ such that for all n, F (n, σ) ≤ c(σ)^{nγ^{∗}(n)}, where γ^{∗}(n) is an extremely slowly growing function, given explicitly in terms of the inverse of the Ackermann function.

Theorem 1. For every k ≥ 2 and σ ∈ S_{k}, for every m, n ≥ 1,

F (m + n, σ) ≥ F (m, σ) F (n, σ) (2)

and F (n, σ) ≥ 1; hence by Fekete’s lemma on subadditive sequences,

(3) c(σ) := lim_{n→∞} F (n, σ)^{1/n} ∈ [1, ∞] exists,

and ∀n ≥ 1, F (n, σ) ≤ c(σ)^{n}.

Proof. First we will show (2) by constructing, from an m-permutation and an npermutation which avoid τ, an (m + n)-permutation which avoids τ, injectively.

Without loss of generality, we may assume that k precedes 1 in σ (since, with (·)^{r} to denote the left-right reverse of a permutation, τ avoids σ iff τ^{r} avoids σ^{r}, and hence for all n, F (n, σ) = F (n, σ^{r}).)

Let τ′ ∈ S_{m} and τ′′ ∈ S_{n}, where each of τ′ and τ′′ avoids σ. Let τ′′′ be the result of adding m to each symbol in the word for τ′′, so that τ′′′ is a word in which each of the symbols m + 1, …, m + n appears exactly once.

Consider the concatenation τ of τ′ with τ′′′ as a permutation, τ ∈ S_{m+n}. Clearly, τ avoids σ, establishing (2).

[In detail, suppose to the contrary that τ contains σ, say at the k-tuple of positions given by 1 ≤ x_{1} < x_{2} < ⋯ < x_{k} ≤ m + n. Recall that k precedes 1 in σ; say that σ(a) = 1 and σ(b) = k with 1 ≤ b < a ≤ k, so that by (1), for 1 ≤ i ≤ k, τ(x_{a}) ≤ τ(x_{i}) ≤ τ(x_{b}). If x_{k} ≤ m then τ′ contains σ, and if x_{1} > m then τ′′ contains σ. If neither of these, then the x_{1} ≤ m so that τ(x_{1}) ≤ m, hence τ(x_{a}) ≤ τ(x_{1}) ≤ m and therefore x_{a} ≤ m; similarly x_{k} > m so that τ(x_{k}) > m, hence τ(x_{b}) ≥ τ(x_{k}) > m and therefore x_{b} > m, contradicting b < a.]

Recalling that k precedes 1 in σ, the identity permutation in S_{n} avoids σ and demonstrates that F (n, σ) ≥ 1 for every n ≥ 1. Fekete’s lemma [4], see also [9], is that if a_{1}, a_{2}, … ∈ ℝ satisfy for all m, n ≥ 1, a_{m} + a_{n} ≤ a_{m+n}, then lim_{n→∞} a_{n}/n = inf_{n≥1} a_{n}/n ∈ [−∞, ∞). Applying this with a_{n} := − log F (n, σ) completes our proof.

There exist [10] examples with σ, σ′ ∈ S_{k}, with σ′ the identity permutation, and F (n, σ) > F (n, σ′), and Bóna [2], Theorem 4 shows that for all n ≥ 7, F (n, 1324) > F (n, 1234). Nevertheless, it is possible that for every k, the largest exponential growth rate is the (k − 1)^{2} achieved by the identity permutation.

Conjecture 1. ($100.00) For all σ ∈ S_{k} and n ≥ 1, F (n, σ) ≤ (k − 1)^{2n}.

The problem of the shortest common superpattern.

Define G(n, k) to be the number of permutations τ ∈ S_{n} which avoid at least one permutation in S_{k}, i.e.

G(n, k) := | ∪_{σ∈S_{k}} A(n, σ) |, where F (n, σ) := |A(n, σ) |.

Simion and Schmidt [8], p. 398, give a formula for n! − G(n, 3), the number of n-permutations which contain all six patterns of length 3. In considering G(n, k), it is natural to consider the length m(k) of the shortest permutation which contains every σ ∈ S_{k} as a subpattern, i.e. to consider

m(k) := min{n: G(n, k) < n! } = min{n: ∪_{σ∈S_{k}}A(n, σ) ≠ S_{n} }.

For a trivial lower bound on m(k), since τ ∈ S_{n} contains at most \binom{n}{k} subpatterns, to contain every subpattern requires \binom{n}{k} ≥ k!, hence lim inf_{k} m(k)/k^{2} ≥ 1/e^{2}.

Theorem 2. There exists an n-permutation, with n = k^{2}, containing every k-permutation as a subpattern; i.e. m(k) ≤ k^{2}.

Proof. Consider the lexicographic order on [k]^{2} as a one-to-one map specifying the ranks of the ordered pairs, i.e. let r : [k]^{2} → [k^{2}], with (i, j) ↦ (i − 1)k + j. Also consider the transposed lexicographic order t : [k]^{2} → [k^{2}] given by t(i, j) := r(j, i). Consider the permutation τ ∈ S_{k^{2}} given by τ = r ∘ t^{−1}; for example, with k = 3, this is τ = 147258369. Then, clearly, τ contains every σ ∈ S_{k} as a subpattern. In detail, with the positions x_{1} := t(σ(1), 1), …, x_{k} := t(σ(k), k) we have x_{1} < ⋯ < x_{k} and for m = 1 to k, τ(x_{m}) = (r ∘ t^{−1})(t(σ(m), m)) = r(σ(m), m) so that τ(x_{a}) < τ(x_{b}) iff σ(a) < σ(b).

Conjecture 2. As k → ∞, m(k) ∼ (k/e)^{2} .

In contrast, from the known behavior of the length L_{n} of the longest increasing subsequence, L_{n} ∼ 2\sqrt{n} with high probability, one cannot hope to use random permutations to show that lim inf m(k)/k^{2} ≤ (1/e)^{2}. The probability that a random n-permutation does not contain every σ ∈ S_{k} as a subpattern is G(n, k)/n!. Define the threshold t(k) by t(k) = min{n: G(n, k)/n! ≤ 1/2}, so that trivially m(k) ≤ t(k), and hence lim inf t(k)/k^{2} ≥ 1/4.

Conjecture 3. (Noga Alon) The threshold length t(k), for a random permutation to contain all k-permutations with substantial probability, has t(k) ∼ (k/2)^{2}.

References

[1] Alon, N., and Friedgut, E. (1999) On the number of permutations avoiding a given pattern. J. Combinatorial Theory, Ser. A, to appear

[2] Bóna, M. (1997) Exact and asymptotic enumeration of permutations with subsequence conditions. Ph.D. Thesis, M.I.T.

[3] Bóna, M. (1999) The solution of a conjecture of Stanley and Wilf for all layered patterns. J. Combinatorial Theory, Ser. A 85, 96-104.

[4] Fekete, M. (1923) Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzähligen Koeffizienten. Math. Z. 17, 228-249.

[5] Klazar, M. (1992) A general upper bound in extremal theory of sequences. Comment. Math. Univ. Carolin. 33, 737-746.

[6] Knuth, D. E. (1968) The art of computer programming. Addison-Wesley, Reading, MA.

[7] Regev, A. (1981) Asymptotic values for degrees associated with strips of Young diagrams. Adv. Math. 41, 115-136.

[8] Simion, R., and Schmidt, F. W. (1985) Restricted permutations. European J. of Combinatorics 6, 383-406.

[9] Steele, J. M. (1997) Probability theory and combinatorial optimization. CBMS-NSF regional conference series in applied mathematics 69. SIAM, Philidelphia, PA.

[10] West, J. (1990) Permutations with forbidden subsequences; and stack sortable permutations. Ph.D. Thesis, MIT.