FINITE AUTOMATA AND PATTERN AVOIDANCE IN WORDS

Petter Brändén Matematik, Chalmers tekniska högskola och Göteborgs universitet S-412 96 Göteborg, Sweden branden@math.chalmers.se

Toufik Mansour Department of Mathematics, Haifa University 31905 Haifa, Israel toufik@math.haifa.ac.il

Abstract. We say that a word w on a totally ordered alphabet avoids the word v if there are no subsequences in w order-equivalent to v. In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula [20] for exact asymptotics for the number of words on k letters of length n that avoids the pattern 12 ⋯ (ℓ + 1). Moreover, we give the first combinatorial proof of the exact formula [9] for the number of words on k letters of length n avoiding a three letter permutation pattern.

2000 Mathematics Subject Classification: 05A05, 05A15, 68Q45.

1. Introduction

In this paper we study pattern avoidance in words. The subject of pattern avoidance in permutations has thrived in the last decades, see [30] and the references there. Only very recently Alon and Friedgut [3] studied pattern avoidance in words to achieve an upper bound on the number of permutations in S_{n} avoiding a given pattern. We study pattern avoidance in words by defining a finite automaton that generates the words avoiding a given pattern and use the transfer matrix method to count them. By this approach we are able to find the asymptotics, as n → ∞, for the number of words on k letters of length n avoiding a pattern p, as well as exact enumeration results. In particular we re-derive Regev’s [20] result on the exact asymptotics for the number of words on k letters of length n avoiding a pattern 12 ⋯ (ℓ + 1), and give the first combinatorial proof of a formula for the number of words on k letters of length n avoiding the pattern 123.

Let S_{n} denote the set of permutations of the set [n] := {1, 2, …, n}. If σ ∈ S_{k} and τ ∈ S_{n}, we say that τ contains σ if there is a sequence 1 ≤ t_{1} < t_{2} < ⋯ < t_{k} ≤ n of integers such that for all 1 ≤ i, j ≤ k we have τ(t_{i}) ≤ τ(t_{j}) if and only if σ(i) ≤ σ(j). Here σ is called a pattern. If τ does not contain σ we say that τ avoids σ. In the study of pattern avoidance the focus has been on enumerating and giving estimates to the number of elements in the set S_{n}(σ), the set of permutations in S_{n} that avoids σ.

Maybe the most interesting open problem in the field is: Does there exists a constant c such that |S_{n}(τ)| < c^{n} for all n ≥ 0? This problem is equivalent to the seemingly stronger statement, see [4]: Conjecture 1.1. (Stanley, Wilf) For any pattern τ ∈ S_{ℓ}, the limit

lim_{n→∞} |S_{n}(τ)|^{\frac{1}{n}} ,

exists and is finite.

The conjecture has been verified for layered patterns [8] and for all patterns which can be written as an increasing subsequence followed by a decreasing [3]. In the latter reference Alon and Friedgut proved a weaker version of Conjecture 1.1, namely: For any permutation σ there exists a constant c = c(σ) such that |S_{n}(σ)| ≤ c^{nγ^{⋆}(n)}, where γ^{⋆} is an extremely slow growing function, related to the Ackermann hierarchy. The method of proof in [3] was by considering pattern avoidance in words. This is also the theme of this paper.

Denote by [k]^{∗} the set of all finite words with letters in [k]. If w = w_{1}w_{2} ⋯ w_{s} ∈ [k]^{∗} and v = v_{1}v_{2} ⋯ v_{r} ∈ [m]^{∗} where r ≤ s, we say that w contains the pattern v if there is a sequence 1 ≤ t_{1} < t_{2} < ⋯ < t_{r} ≤ s such that for all 1 ≤ i, j ≤ s we have

w_{t_{i}} ≤ w_{t_{j}} if and only if v_{i} ≤ v_{j}.

If w does not contain v we say that w avoids v. For example, the word w = 323122411 ∈ [4]^{9} avoids the pattern 132 and contains the patterns 123, 212, 213, 231, 312, and 321. If S is any set of finite words we denote the set of words in S that avoids v by S(v).

The history of pattern avoidance in words is not as rich as the one in permutations. We mention the references [2, 3, 9, 10, 14, 20]. In [20] Regev gave a complete answer for the asymptotics for |[k]^{n}(p_{ℓ})| when n → ∞, where p_{ℓ} = 12 ⋯ (ℓ + 1): Theorem 1.2 (Regev). For all k ≥ ℓ we have

|[k]^{n}(p_{ℓ})| ≃ C_{ℓ,k}n^{ℓ(k−ℓ)}ℓ^{n} (n → ∞),

where

C_{ℓ,k}^{−1} = ℓ^{ℓ(k−ℓ)} ∏_{i=1}^{ℓ} ∏_{j=1}^{k−ℓ}(i + j − 1).

1.1. Organization of the paper. The paper is organized as follows. In Section 2 we present the relevant definitions and attain some preliminary results, and in Section 3 we use the transfer matrix method to determine the asymptotic growth for the sequence n ↦ |[k]^{n}(p)|. In Section 4.1 we study the special features of the automaton, A(p_{ℓ}, k), which generates the words with letters in [k] that avoids the increasing pattern 12 ⋯ (ℓ+1). Here we will give a simple proof of Theorem 1.2 using the transfer matrix method and give a combinatorial proof for the formula [9] for |[k]^{n}(p)|, where p is any permutation pattern of length three. We also consider the diagonal sequence |[n]^{n}(123)| and determine its asymptotic growth as well as showing that its generating function is transcendental. We conclude the paper by indicating further problems connected to the work in this paper.

2. Definitions and preliminary results

Given a word-pattern p and an integer k > 0 we define an equivalence relation ∼_{p} on [k]^{∗} by: v ∼_{p} w if for all words r ∈ [k]^{∗} we have

vr avoids p if and only if wr avoids p.

For example, if p = 132, k ≥ 4, v = 13 and w = 14, then v ≁_{p} w, since 133 avoids p but 143 contains p. At first sight it may seem difficult to determine if v ∼_{p} w, since a priori there is an infinite number of right factors r to check. By the following lemma we have to check only a finite number words r. Lemma 2.1. Let p be a pattern of length ℓ and let v, w ∈ [k]^{∗} be any two words. Then v ∼_{p} w if and only if for all words r ∈ [k]^{s}, 0 ≤ s ≤ ℓ, we have

vr avoids p if and only if wr avoids p.

Proof. Define an equivalence relation ∼′_{p} on [k]^{∗} by: v ∼′_{p} w if for all words r ∈ [k]^{s}, 0 ≤ s ≤ ℓ, we have

vr avoids p if and only if wr avoids p.

Clearly, v ∼_{p} w implies v ∼′_{p} w. On the other hand if v ≁_{p} w we may assume that there is an r ∈ [k]^{∗} such that vr contains p and wr avoids p. Any occurrence of p in vr can use at most ℓ letters of r. Thus there is a subsequence r′ of r of length at most ℓ such that vr′ contains p and wr′ avoids p, i.e., v ≁′_{p} w. □

Let E(p, k) be the set of equivalence classes of ∼_{p}. By Lemma 2.1 the number of equivalence classes is finite. We denote the equivalence class of a word w by ⟨w⟩. The equivalence classes of ∼_{p} for p ∈ S_{3} and k = 3, 4, 5 are given in Table 1. Definition 2.2. Given a positive integer k and a pattern p we define a finite automaton^{1}, A(p, k) = (E(p, k), [k], δ, ⟨ε⟩, E(p, k) \ {⟨p⟩}), by

• the states are, E(p, k), the equivalence-classes of ∼_{p},

• [k] is the input alphabet,

• δ : E(p, k) × [k] → E(p, k) is the transition function defined by δ(⟨w⟩, i) = ⟨wi⟩, where wi is w concatenated with the letter i ∈ [k],

• ⟨ε⟩ is the initial state, where ε is the empty word,

• all states but ⟨p⟩ are final states.

For an example see Fig. 1.

We will identify A(p, k) with the (labelled) directed graph with vertices E(p, k) and with a (labelled) edge ⟶^{i} between ⟨v⟩ and ⟨w⟩ if vi ∼_{p} w. Clearly, we may order the states as x_{1}, x_{2}, …, x_{e} so that if i < j there is no path from x_{j} to x_{i}. The transition matrix, T (p, k), of A(p, k) is the matrix of size e × e with non-negative integer coefficients defined by:

[T (p, k)]_{ij} = |{s ∈ [k] : δ(x_{i}, s) = x_{j}}|.

Thus [T (p, k)]_{ij} counts the number of edges between x_{i} and x_{j}, and T (p, k) is triangular.

1For a definition of a finite automaton, see [1] and references therein.

k p The equivalences classes in E(p, k)
3 123 ⟨ϵ⟩, ⟨1⟩, ⟨12⟩, ⟨123⟩
132 ⟨ϵ⟩, ⟨1⟩, ⟨13⟩, ⟨132⟩
213 ⟨ϵ⟩, ⟨2⟩, ⟨21⟩, ⟨213⟩
231 ⟨ϵ⟩, ⟨2⟩, ⟨23⟩, ⟨231⟩
312 ⟨ϵ⟩, ⟨3⟩, ⟨31⟩, ⟨312⟩
321 ⟨ϵ⟩, ⟨3⟩, ⟨32⟩, ⟨321⟩
4 123 ⟨ϵ⟩, ⟨1⟩, ⟨2⟩, ⟨12⟩, ⟨13⟩, ⟨23⟩, ⟨123⟩
132 ⟨ϵ⟩, ⟨1⟩, ⟨2⟩, ⟨13⟩, ⟨14⟩, ⟨24⟩, ⟨132⟩, ⟨241⟩
213 ⟨ϵ⟩, ⟨2⟩, ⟨3⟩, ⟨21⟩, ⟨23⟩, ⟨31⟩, ⟨32⟩, ⟨213⟩
231 ⟨ϵ⟩, ⟨2⟩, ⟨3⟩, ⟨23⟩, ⟨24⟩, ⟨32⟩, ⟨34⟩, ⟨231⟩
312 ⟨ϵ⟩, ⟨3⟩, ⟨4⟩, ⟨31⟩, ⟨41⟩, ⟨42⟩, ⟨312⟩, ⟨314⟩
321 ⟨ϵ⟩, ⟨3⟩, ⟨4⟩, ⟨32⟩, ⟨42⟩, ⟨43⟩, ⟨321⟩
5 123 ⟨ϵ⟩, ⟨1⟩, ⟨2⟩, ⟨3⟩, ⟨12⟩, ⟨13⟩, ⟨14⟩, ⟨23⟩, ⟨24⟩, ⟨34⟩, ⟨123⟩
132 ⟨ϵ⟩, ⟨1⟩, ⟨2⟩, ⟨3⟩, ⟨13⟩, ⟨14⟩, ⟨15⟩, ⟨24⟩, ⟨25⟩, ⟨35⟩, ⟨132⟩, ⟨241⟩, ⟨251⟩, ⟨351⟩, ⟨352⟩, ⟨3513⟩
213 ⟨ϵ⟩, ⟨2⟩, ⟨3⟩, ⟨4⟩, ⟨21⟩, ⟨23⟩, ⟨24⟩, ⟨31⟩, ⟨32⟩, ⟨34⟩, ⟨41⟩, ⟨42⟩, ⟨43⟩, ⟨213⟩, ⟨234⟩, ⟨243⟩
231 ⟨ϵ⟩, ⟨2⟩, ⟨3⟩, ⟨4⟩, ⟨23⟩, ⟨24⟩, ⟨25⟩, ⟨32⟩, ⟨34⟩, ⟨35⟩, ⟨42⟩, ⟨43⟩, ⟨45⟩, ⟨231⟩, ⟨243⟩, ⟨432⟩
312 ⟨ϵ⟩, ⟨3⟩, ⟨4⟩, ⟨5⟩, ⟨31⟩, ⟨41⟩, ⟨42⟩, ⟨51⟩, ⟨52⟩, ⟨53⟩, ⟨312⟩, ⟨314⟩, ⟨315⟩, ⟨415⟩, ⟨425⟩, ⟨3153⟩
321 ⟨ϵ⟩, ⟨3⟩, ⟨4⟩, ⟨5⟩, ⟨32⟩, ⟨42⟩, ⟨43⟩, ⟨52⟩, ⟨53⟩, ⟨54⟩, ⟨321⟩

Table 1. The equivalence classes of ∼_{p} for p ∈ S_{3} and k = 3, 4, 5.

Example 2.3. If p = 2314 and k = 5, then it is easy to check (see [18]) that the states are ⟨ϵ⟩, ⟨2⟩, ⟨3⟩, ⟨32⟩, ⟨34⟩, ⟨24⟩, ⟨23⟩, ⟨324⟩, ⟨341⟩, ⟨241⟩, ⟨234⟩, ⟨2342⟩, ⟨231⟩, and ⟨2314⟩ (see Fig. 1).

Figure 1. The figure shows the final states in the automaton A(2314, 5).

Note that there are two edges between the states ⟨324⟩ and ⟨241⟩, namely ⟨324⟩ ⟶^{1} ⟨241⟩ and ⟨324⟩ ⟶^{2} ⟨241⟩. Moreover, all final states in A(2314, 5) have 3 loops, except ⟨324⟩ which has 2 loops.

The following simple lemma will be helpful in finding the asymptotic growth of the sequence |[n]^{k}(p)|, for fixed k. Lemma 2.4. Let the automaton A(p, k) be given, let d be the number of distinct letters in p and suppose that k ≥ d − 1. If ⟨v⟩ is any state different from ⟨p⟩, then the number of loops at ⟨v⟩ does not exceed d − 1. Moreover, there are exactly d − 1 loops at ⟨ε⟩.

Proof. Suppose that there are more than d − 1 loops at ⟨v⟩. Then the loops use at least d different labels. From these labels we can form a word w order-isomorphic to p. But then vw ∼_{p} v which is a contradiction.

Let p_{1} be the first letter of p. Then, if i < p_{1} or i > k − d + p_{1} we have i ∼_{p} ε. But there are d − 1 such is, which proves the lemma. □

Although pattern avoidance in words and pattern avoidance in permutations share many common features, there are some important aspects in which they differ. For permutations there are three simple operations, f, that respects pattern-avoidance in the sense that f(τ) avoids f(σ) if and only if τ avoids σ, namely the reversal, the complement and the inverse of a permutation. The first two operations have obvious generalizations to words, while the inverse does not. It has in fact been an open question to construct an inverse for words possessing “the right” properties. Such an inverse was recently constructed by Hohlweg and Reutenauer [13]. Unfortunately it is not possible to construct an inverse that respects pattern avoidance in words, which would imply the identity |[k]^{n}(p)| = |[k]^{n}(p^{−1})|, for all k, n ≥ 0 and permutation patterns p. The first counter example to this is |[5]^{7}(1342)| = 67854 > 67853 = |[5]^{7}(1423)|, see Table 5.2. If w ∈ [k]^{n} let the complement of w in [k]^{n} be w^{c} = (k+1−w_{1})(k+1−w_{2}) ⋯ (k+1−w_{n}). Then we have in fact that A(p, k) and A(p^{c}, k) are isomorphic as automata for any p ∈ [k]^{∗}, since v ∼_{p} w if and only if v^{c} ∼_{p^{c}} w^{c}.

Certainly w avoids p if and only if w^{r} avoids p^{r}, where ^{r} is the reversal operator and w and p are any words. However A(p, k) and A(p^{r}, k) are not in general isomorphic. Indeed, for p = 2314 and k = 5 we have that |E(2314, 5)| = 13 and |E(4132, 5)| = 14.

3. Transfer matrix method

In this section we use the transfer matrix method (see [26, Theorem 4.7.2]) to obtain information about the sequences |[k]^{n}(p)|. Given a matrix A let (A; i, j) be the matrix with row i and column j deleted. If p is a pattern and k > 0 an positive integer let T′(p, k) = (T (p, k), e_{k} − 1, e_{k} − 1). Theorem 3.1. Let k be a positive integer, p be a pattern and e_{k} be the number of states in A(p, k). Then the generating function for |[k]^{n}(p)| is

∑_{n≥0} |[k]^{n}(p)|x^{n} = \frac{∑_{j=1}^{e_{k}−1} (−1)^{j+1} det(I − xT′, j, 1)}{∏_{i=1}^{e_{k}−1}(1 − λ_{i}x)} = \frac{det B(x)}{∏_{i=1}^{e_{k}−1}(1 − λ_{i}x)},

where λ_{i} is the number of loops at state x_{i}, and B(x) is the matrix obtained by replacing the first column in I − xT′ with a column of all ones.

Proof. The theorem follows from the transfer matrix method, see [26, Theorem 4.7.2], since we want to count the number of paths from ⟨ε⟩ to any state other than ⟨p⟩ of length n in A(p, k). □

Regev [20] computed the exact asymptotics for |[k]^{n}(p_{ℓ})|, where p_{ℓ} is the increasing pattern 12 ⋯ (ℓ + 1) and n → ∞. We will next find the exact asymptotics (up to a constant) for |[k]^{n}(p)| for all patterns p. Given two sequences {a_{n}} and {b_{n}} of real numbers, we denote a_{n} ≃ b_{n} if lim_{n→∞} \frac{a_{n}}{b_{n}} = 1. A path in A(p, k) is called simple if it starts at ⟨ε⟩, does not use any loops, and does not end in ⟨p⟩. Theorem 3.2. Let p be any pattern with d distinct letters and let k ≥ d − 1 be given. Then there is a constant C > 0 such that

|[k]^{n}(p)| ≃ Cn^{M}(d − 1)^{n} (n → ∞),

where M + 1 is the maximum number of states with d − 1 loops, in a simple path.

Proof. Let P := x_{1}, x_{2}, …, x_{j} be a simple path in A(p, k). Moreover, let ℓ_{j} be the number of loops at state x_{j}. Then |[k]^{n}(p)| = ∑_{P} N(P, n) where

N(P, n) = ∑_{α_{1}+···+α_{j}=n−j+1} ℓ_{1}^{α_{1}}ℓ_{2}^{α_{2}} ⋯ ℓ_{j}^{α_{j}},

and the sum is over all weak compositions of n − j + 1 into at most j parts. Now, N(P, n) is equal to the coefficient to t^{n−j+1} in (1 − ℓ_{1}t)^{−1} ⋯ (1 − ℓ_{j}t)^{−1}. Let r be the number of i such that ℓ_{i} = d − 1. Note that by Lemma 2.4 r is greater than or equal to one. The dominant term of (1 − ℓ_{1}t)^{−1} ⋯ (1 − ℓ_{j}t)^{−1} is (by partial fraction decomposition) equal to

\frac{f(t)}{(1 − (d − 1)t)^{r}} ,

where f(t) is a polynomial of degree less than r and f((d − 1)^{−1}) ≠ 0. By well known results it follows that N(P, n) ≃ C(P)(d − 1)^{n}n^{r−1}, where C(P) > 0 is a constant depending on P and k. Taking the greatest possible r yields the desired results. □

When there are exactly d − 1 loops at every state except ⟨p⟩ in A(p, k), then it follows from Theorem 3.1 that |[k]^{n}(p)| = (d − 1)^{n}Q(n), where Q is a polynomial in n. We have in fact: Corollary 3.3. Let A(p, k) be such that all states but ⟨p⟩ has exactly d−1 loops. Then

|[k]^{n}(p)| = ∑_{j=0}^{M} a_{j}(d − 1)^{n−j}\binom{n}{j},

where a_{j} counts the number of simple paths of length j in A(p, k). Moreover, if p is a pattern of length ℓ + 1 then a_{j} = (k − d + 1)^{j} for all j = 0, 1, …, ℓ.

Proof. The corollary follows from the proof of Theorem 3.2 since N(P, n) = (d − 1)^{n−j}\binom{n}{j}. If p is a pattern of length ℓ + 1 then we have that a_{j} = (k − d + 1)^{j} where j = 0, 1, …, ℓ, since k^{j} = ∑_{i=0}^{j} a_{i}(d − 1)^{j−i}\binom{j}{i} for all j = 0, 1, …, ℓ. □

As an example of Corollary 3.3 we note that if p is any pattern of length ℓ + 1 with exactly d different letters then

|[d]^{n}(p)| = ∑_{j=0}^{ℓ}(d − 1)^{n−j}\binom{n}{j}.

4. The increasing patterns

We will in this section investigate the properties of A(p_{ℓ}, k), where p_{ℓ} = 12 ⋯ (ℓ + 1). The following lemma describes the structure of A(p_{ℓ}, k): Lemma 4.1. Let k ≥ ℓ be given. For any subset S of [k] of size ℓ let w_{S} be the word consisting of the elements of S listed in increasing order. Then the words w_{S} together with p_{ℓ} constitute a complete set of representatives for the equivalence-classes E(p_{ℓ}, k). In particular we have:

|E(p_{ℓ}, k)| = \binom{k}{ℓ} + 1.

If S = {s_{1} < ⋯ < s_{ℓ}} ⊆ [k] and j ∈ [k] let

S^{j} = {s_{1} < ⋯ < s_{i−1} < j < s_{i+1} < ⋯ < s_{ℓ}},

where i is the integer such that s_{i−1} < j ≤ s_{i}, (s_{0} := 0, s_{ℓ+1} := k + 1). Then

δ(⟨w_{S}⟩, j) = \begin{cases}⟨w_{S^{j}}⟩ if j ≤ s_{ℓ}, \\ ⟨p_{ℓ}⟩ otherwise . \end{cases}

In particular, the loops of w_{S} are the elements of S.

Proof. It is clear that the words w_{S} are representatives for different classes. Let v ∈ [k]^{∗}(p_{ℓ}). We say that an increasing subword x_{1}x_{2} ⋯ x_{j} of v is extendible if x_{j} ≤ k + j − ℓ − 1, i.e., if we may extend x_{1}x_{2} ⋯ x_{j} to an occurrence of p_{ℓ} using letters from [k]. Suppose that the maximum length of an extendible increasing subsequence in v is equal to s, s ≤ ℓ. For 1 ≤ j ≤ s let

r_{j}(v) := min{x_{j} : x_{1}x_{2} ⋯ x_{j} is an extendible subword of v}.

Clearly r_{1}(v) < r_{2}(v) < ⋯ < r_{s}(v). Let

S = {r_{1}(v), r_{2}(v), …, r_{s}(v), k + s + 1 − ℓ, k + s − ℓ, …, k − 1, k}.

Then we see that w_{S} ∼ v. The statement about the transition function follows from the construction. □

In the sequel we will use some standard notation from the theory of partitions and symmetric functions. For undefined terminology we refer the reader to Chapter 7 of [27]. Theorem 4.2. Define a partial order on the final states in A(p_{ℓ}, k) by: x ≤ y if there exists a path from x to y in A(p_{ℓ}, k). Then this partial order is isomorphic to

J([ℓ] × [k − ℓ]),

the lattice of order ideals of the poset [ℓ] × [k − ℓ].

Proof. Let S = {s_{1} < s_{2} < ⋯ < s_{ℓ}} and T = {t_{1} < t_{2} < ⋯ < t_{ℓ}} be subsets of [k]. We claim that there exists a path from ⟨w_{S}⟩ to ⟨w_{T} ⟩ if and only if s_{i} ≥ t_{i} for all 1 ≤ i ≤ ℓ. From this the theorem follows since the latter poset is isomorphic to the interval [∅, λ_{ℓ,k−ℓ}], in the Young’s lattice, where λ_{ℓ,k−ℓ} := (k − ℓ, k − ℓ, …, k − ℓ) is of length ℓ. Indeed, consider the bijection defined by:

(s_{1}, s_{2}, …, s_{ℓ}) ↦ (s_{ℓ} − ℓ, s_{ℓ−1} − ℓ + 1, …, s_{1} − 1) ∈ [∅, λ_{ℓ,k−ℓ}].

Then s_{i} ≥ t_{i} for all 1 ≤ i ≤ j if and only if the image of S is greater than the image of T in [∅, λ_{ℓ,k−ℓ}]. But [∅, λ_{ℓ,k−ℓ}] is its own dual, so the statement follows from the simple fact that [∅, λ_{ℓ,k−ℓ}] is isomorphic to J([ℓ] × [k − ℓ]).

If there is an edge between ⟨w_{S}⟩ and ⟨w_{T} ⟩, we are done by Lemma 4.1. The “only if” direction thus follows by induction on the length of the path.

Now, if s_{i} ≥ t_{i} for all 1 ≤ i ≤ ℓ consider the path

⟨w_{S}⟩ ⟶^{t_{1}} ⟨w_{S}t_{1}⟩ ⟶^{t_{2}} ⟨w_{S}t_{1}t_{2}⟩ ⟶^{t_{3}} ⋯ ⟶^{t_{ℓ}} ⟨w_{S}t_{1}t_{2} ⋯ t_{ℓ}⟩.

It is not hard to see that ⟨w_{S}t_{1}t_{2} ⋯ t_{ℓ}⟩ = ⟨w_{T} ⟩, which completes the proof. □

We now have a different proof of the following theorem of Regev [20]: Theorem 4.3 (Regev). For all k ≥ ℓ we have

|[k]^{n}(p_{ℓ})| ≃ C_{ℓ,k}n^{ℓ(k−ℓ)}ℓ^{n} (n → ∞),

where

C_{ℓ,k}^{−1} = ℓ^{ℓ(k−ℓ)} ∏_{i=1}^{ℓ} ∏_{j=1}^{k−ℓ}(i + j − 1).

Proof. By Corollary 3.3 and Theorem 4.2 we have that

|[k]^{n}(p_{ℓ})| ≃ a_{M}ℓ^{−M} \binom{n}{M}ℓ^{n} ≃ \frac{a_{M}}{M!}ℓ^{−M}n^{M}ℓ^{n} (n → ∞),

where M = ℓ(k −ℓ) and a_{M} is equal to the number of maximal chains in J([ℓ]×[k −ℓ]). By [27, Proposition 7.10.3] and the hook-length formula [27, Corollary 7.21.6] we have that

a_{ℓ(k−ℓ)} = f^{λ_{ℓ,k−ℓ}} = \frac{(ℓ(k − ℓ))!}{∏_{i=1}^{ℓ} ∏_{j=1}^{k−ℓ}(i + j − 1)},

from which the theorem follows. □

It should be clear from the correspondence in Theorem 4.2 that the simple paths of length r in A(p_{ℓ}, k + ℓ) are in a one-to-one correspondence with tableaux T of the following type:

(i) T is weakly increasing in rows and columns, (ii) no integer appears in more than one row, (iii) the entries of T are exactly [r], (iv) the shape of T is confided in λ_{ℓ,k}.

Recall that the tableaux satisfying (i) and (ii) above are the border-strip tableaux (or rim-hook tableaux) of height zero. We call these tableaux segmented. Let a(ℓ, k, r) denote the number of segmented tableaux satisfying (iii) and (iv), so that:

(4.1)  |[k + ℓ]^{n}(p_{ℓ})| = ∑_{r=0}^{ℓk} ℓ^{n−r}a(ℓ, k, r)\binom{n}{r}.

The function a(ℓ, k, r) is actually a polynomial in k of degree r. To see this let us call a segmented tableau inside [ℓ] × [k] primitive if all columns are different, and let the set of such tableaux of length i with r different entries be PR_{ℓ,i,r}. If we denote the number of elements in PR_{ℓ,i,r} by pr(ℓ, i, r) we have

a(ℓ, k, r) = ∑_{i=r/ℓ}^{r} pr(ℓ, i, r)\binom{k}{i},

since for any such primitive tableaux of length i we may insert a number α_{1} copies of the first column before the first column, a number α_{2} copies of the second column between the first and the second column, and so on. After the last column we may insert a number α_{i+1} columns of all blanks, requiring that

α_{1} + α_{2} + ⋯ + α_{i+1} = k − i.

Thus there are \binom{k}{i} segmented tableaux arising from a given primitive one. The numbers pr(ℓ, i, r) are in general hard to count, but there are two special cases which are nice, namely pr(ℓ, r, r) and pr(2, i, r). We start by counting pr(ℓ, r, r). Theorem 4.4. With definitions as above:

pr(ℓ, n, n) = |S_{n}(p_{ℓ})|.

Proof. We will define a bijection between S_{n} and ∪_{ℓ≥0}PR_{ℓ,n,n} such that the height of the tableau corresponds to the greatest increasing subsequence in the permutation. Recall the definition of r_{i}(v) in the proof of Lemma 4.1, and let r(v) = (r_{1}(v), r_{2}(v), …, r_{ℓ}(v)), where ℓ is the length of the longest increasing subsequence in v. Let k be big enough so that all increasing subsequences in permutations in S_{n} are considered extendible.

Now, if π = π_{1}π_{2} ⋯ π_{n} is any permutation in S_{n} define T = T (π) as follows. Let the first column of T be r(π) the second column be r(π_{1} ⋯ π_{n−1}) and so on. The image of the permutation 351462 is:

T (351462) = 1 1 1 1 3 3 2 4 4 5 5 6 6 .

By Lemma 4.1 we have that T (π) ∈ PR_{ℓ,n,n}. Moreover from Lemma 4.1 we also get that a tableau T is the image of some π ∈ S_{n} if and only if

(a) T has n columns and entries 1, 2, …, n,

(b) Let T^{i} denote the ith column. If i < j then T^{i} is smaller than T^{j} in the product order. (If T^{i} and T^{j} have different size fill the empty slots of T^{j} with n + 1),

(c) Exactly one new entry appears every time you move from T^{i+1} to T^{i}.

Now, if T ∈ ∪_{ℓ≥0}PR_{ℓ,n,n} condition (a) and (b) are trivially satisfied. At least one new entry appears every time we move from T^{i+1} to T^{i}, since otherwise T^{i} = T^{i+1} and T fails to be primitive. On the other hand if there appear more than one new entry in a transition then in a later transition there must appear no new entry, since T has n columns and n entries. This verifies condition (c) and the theorem follows. □

A special case of Theorem 4.4 is that pr(2, n, n) = C_{n}, the nth Catalan number. This is also a special case of the next theorem. Note, that Theorem 4.5 is what we need to have combinatorial proof of a closed formula, see Theorem 4.7, for the numbers |[k]^{n}(123)|. Burstein [9] achieved a different, but of course equivalent, formula for |[k]^{n}(123)|, but not in a bijective manner.

Theorem 4.5. With definitions as above:

pr(2, i, r) = \frac{1}{i + 1}\binom{2i}{i}\binom{i}{r − i}.

Before we give a proof of Theorem 4.5 we will need some definitions and a lemma. Let PR^{+}(2, s, r) be the tableaux in PR(2, s, r) that fill up the shape [2] × [r], and let pr^{+}(2, s, r) := |PR^{+}(2, s, r)|. Then pr(2, s, r) = pr^{+}(2, s, r) + pr^{+}(2, s, r + 1) since we get the tableaux that do not fill up the shape by deleting all entries r + 1. To prove the theorem we will show that pr^{+}(2, s, r) = \binom{s−1}{2s−r}C_{s}, where C_{s} is the sth Catalan number.

We first define an operation + that takes tableaux with r different entries to tableaux with r +1 different entries. Let T ∈ PR^{+}(2, s, r). Suppose that j is an index such that T_{ij} = T_{i(j+1)} for some i = 1, 2. Write T as T = LR where L is the j first columns and R is the s − j last columns. Let R′ be the array order equivalent with R with entries the same as R, add r + 1, take away T_{i(j+1)} (two arrays A and B are said to be order equivalent if A_{ij} ≤ A_{i′j′} if and only if B_{ij} ≤ B_{i′j′} for all i, j, i′, j′). We define T + j to be the tableaux T + j := LR′. In T there are exactly t = 2s − r indices j ∈ [s − 1] such that T_{ij} = T_{i(j+1)} for some i = 1, 2. Let S = {s_{1} < s_{2} < ⋯ < s_{t}} be these indices and define a function Φ : PR^{+}(2, s, r) → \binom{[s−1]}{t} × ST_{2,s}, where ST_{2,s} is the set of standard tableaux of shape [2] × [s], by

Φ(T) = (S, T + s_{t} + s_{t−1} + ⋯ + s_{1}).

The fact that Φ is a bijection will prove the theorem, since by the hook-length formula we have |ST_{2,s}| = C_{s}. To find the inverse of Φ we need a kind of inverse operation to +.

Let T ∈ PR^{+}(2, s, r) and 1 ≤ b ≤ s − 1 be such that T_{1b} < T_{1(b+1)} and T_{2b} < T_{2(b+1)}. Define two arrays T |_{b} and T |^{b} as follows. Write T = LR where L are the b first columns and R are the s − b last columns. Define T |^{b} := L′R′, to be the array where L = L′ and R′ is the unique array order equivalent with R, with entries the same as R add T_{1b} take away r. Similarly, let T |_{b} := L′R′, be the array with L = L′ and where R′ is the unique array order equivalent with R, with entries the same as R, add T_{2b} take away r.

\begin{matrix}1 & 2 & 4 & 4 \\ 3 & 5 & 6 & 7 \end{matrix} |^{2} = 1 2 2 2 3 5 4 6
\begin{matrix}1 & 2 & 4 & 4 \\ 3 & 5 & 6 & 7 \end{matrix} |_{2} = 1 2 4 4 3 5 5 6

Note that exactly one of T |^{2} and T |_{2} above is a primitive segmented tableaux. This is no accident. Lemma 4.6. Let T ∈ PR^{+}(2, s, r) and 1 ≤ b ≤ s − 1 be such that T_{1b} < T_{1(b+1)} and T_{2b} < T_{2(b+1)}. Then

T |_{b} ∈ PR^{+}(2, s, r − 1) ⇔ T |^{b} ∉ PR^{+}(2, s, r − 1)
⇔ T_{2(b+1)} = T_{2b} + 1

Moreover, if B = T |^{b} ∈ PR^{+}(2, s, r − 1) then B_{1b} = B_{1(b+1)} and if A = T |_{b} ∈ PR^{+}(2, s, r − 1) then A_{1b} = A_{1(b+1)}.

Proof. Consider A := T |_{b}. All entries in T that are smaller than T_{2b} will be mapped on themselves and A_{ij} = T_{ij} − 1 for A_{ij} > T_{2b}. Therefore A ∈ PR^{+}(2, s, r − 1) if and only if T_{2(b+1)} = T_{2b} + 1 (since otherwise the entry T_{2b} will appear in both the first and the second row).

Consider B := T |^{b}. Let y_{i}, i = 1, 2, …, h be the entries in T satisfying T_{2b} < y_{i} ≤ T_{2(b+1)} ordered by size. Then the entry y_{1} will be mapped to an element smaller than T_{2b} and y_{i} will be mapped to y_{i−1} for i > 1. Thus B ∈ PR^{+}(2, s, r − 1) if and only if T_{2(b+1)} > T_{2b} + 1 as claimed.

The last statement is a direct consequence of the above proof. □

We are now ready to give a proof of Theorem 4.5.

Proof of Theorem 4.5. If T ∈ PR^{+}(2, s, r) and 1 ≤ b ≤ s−1 are such that T_{1b} < T_{1(b+1)} and T_{2b} < T_{2(b+1)} we define T − b to be the one of the arrays T |_{b} and T |^{b} which is in PR^{+}(2, s, r − 1). By Lemma 4.6 we have that

(4.2)  (T + j) − j = T if T_{ij} = T_{i(j+1)} for some i = 1, 2,
(T − j) + j = T if T_{ij} < T_{i(j+1)} for both i = 1, 2.

Now, if S = {x_{1} < x_{2} < ⋯ < x_{t}}, where t = 2s − r and P ∈ ST_{2,s} we let

Ψ(S, P) := P − x_{1} − x_{2} − ⋯ − x_{t}.

By (4.2) it follows that Ψ is the inverse to Φ and the theorem follows. □

We now have a combinatorial proof of the following theorem given in a different form in [9]: Theorem 4.7. For all n, k ≥ 0 we have

|[k + 2]^{n}(123)| = ∑_{r,i} 2^{n−r}C_{i}\binom{i}{r − i}\binom{n}{r}\binom{k}{i},

where C_{i} is the ith Catalan number. The generating function

F (x, y) := ∑_{n,k} |[k + 2]^{n}(123)|x^{k}y^{n},

is given by

F (x, y) = \frac{1}{(1 − x)(1 − 2y)}C (\frac{xy(1 − y)}{(1 − x)(1 − 2y)^{2}} ) ,

where C(z) is the generating function for the Catalan numbers. Equivalently, F (x, y) is algebraic of degree two and satisfies the equation:

x(1 − x)y(1 − y)F^{2} − (1 − x)(1 − 2y)F + 1 = 0.

To complete the picture for permutation patterns of length 3 it remains to enumerate |[k]^{n}(132)|. Simion and Schmidt [24] introduced a simple bijection between S_{n}(123) and S_{n}(132) which fixes each element of S_{n}(123) ∪ S_{n}(132). West [29] generalized this bijection to obtain a bijection between S_{n}(p) and S_{n}(q) where p(ℓ) = q(ℓ − 1) = ℓ, p(ℓ − 1) = q(ℓ) = ℓ − 1, and p, q ∈ S_{ℓ}. Here we indicate how to generalize West’s result to obtain a bijection between [k]^{n}(p) and [k]^{n}(q) where p and q are as above. Theorem 4.8. Let p = p_{1}p_{2} ⋯ p_{ℓ} be a pattern with greatest entry equal to d and p_{ℓ−1} = d − 1, p_{ℓ} = d. If d occurs exactly once in p then

|[k]^{n}(p)| = |[k]^{n}(p̃)|,

where p̃ = p_{1}p_{2} ⋯ p_{ℓ}p_{ℓ−1}.

Proof. The proof is a straight forward generalization of West’s algorithm presented in [29, Section 3.2].

□

For example, if p = 132 then p̃ = 123. Hence, by Theorem 4.8 we get that if p and q are any permutation patterns of length 3 then |[k]^{n}(p)| = |[k]^{n}(q)| for all n, k ≥ 0 (see [9] for an analytical proof). If p = 1232 the p̃ = 1223. Hence, Theorem 4.8 gives |[k]^{n}(1232)| = |[k]^{n}(1223)| for all n, k ≥ 0.

Since, S_{n}(p) ⊂ [n]^{n}(p), the numbers |[n]^{n}(p)| are interesting. A sequence f(n) is polynomially recursive (P-recursive) if there is a finite number of polynomials P_{i}(n) such that

∑_{i=0}^{N} P_{i}(n)f(n + i) = 0,

for all integers n ≥ 0. For the case when p is permutation pattern of length 3 we have the following: Theorem 4.9. Let p be a permutation pattern of length 3. Then the sequence f(n) := |[n]^{n}(p)| is P -recursive and satisfies the three term recurrence:

p(n)f(n − 2) + q(n)f(n − 1) + r(n)f(n) = 0,

where

p(n) = 3(n − 3)(n − 1)(3n − 5)(3n − 4)(5n − 4),
q(n) = 288 − 1440n + 2780n^{2} − 2435n^{3} + 976n^{4} − 145n^{5}, and
r(n) = 2(n − 2)^{2}n(n + 1)(5n − 9).

Proof. The fact that f(n) is P -recursive follows easily from the expansion of f(n) as a double sum using Theorem 4.7 and the theory developed in [17]. The polynomials p, q and r were found using the package MULTISUM (see [28]) developed by Wegschaider and Riese. □

Corollary 4.10. The asymptotics of f(n) = |[n]^{n}(123)| is given by

f(n) ∼ Cn^{−2} (\frac{27}{2})^{n} ,

where C > 0 is a constant.

Proof. This is a direct consequence of Theorem 4.9 and the theory of asymptotics for P -recursive sequences, see [31]. □

A consequence of this is that the generating function of f(n) is transcendent, since the exponent of n in the asymptotic expansion of a sequence with an algebraic generating function is never a negative integer.

4.1. Generating function approach. In this section we will investigate the generating function that enumerates the number of segmented tableaux according to size of rows and number of different entries. Let A_{ℓ}(x_{1}, x_{2}, …, x_{ℓ}, t) be the generating function:

A_{ℓ} = ∑_{T} x_{1}^{λ_{1}(T)}x_{2}^{λ_{1}(T)−λ_{2}(T)} ⋯ x_{ℓ}^{λ_{ℓ−1}(T)−λ_{ℓ}(T)}t^{N(T)},

where λ_{i}(T) denotes the size of row i in T, N(T) denotes the number of different entries in T and the sum is over all segmented tableaux with at most ℓ rows. For i = 1, 2, …, ℓ let A_{ℓ}^{i}(x_{1}, …, x_{ℓ}, t) be the generating function for those tableaux which have their maximal entry in row i. If F (x_{1}, x_{2}, …, x_{n}) is a formal power-series in n variables the divided difference of F with respect to the variable x_{i} is

Δ_{i}F := \frac{F − F (x_{i} = 0)}{x_{i}},

where F (x_{i} = 0) is short for F (x_{1}, x_{2}, …, x_{i−1}, 0, x_{i+1}, …, x_{n}). Theorem 4.11. With definitions as above we have that A_{ℓ} satisfies the following system of equations:

A_{ℓ} = 1 + A_{ℓ}^{1} + ⋯ + A_{ℓ}^{ℓ},
A_{ℓ}^{1} = x_{1}x_{2}tA_{ℓ} + x_{1}x_{2}A_{ℓ}^{1},
A_{ℓ}^{2} = x_{3}tΔ_{2}A_{ℓ} + x_{3}Δ_{2}A_{ℓ}^{2},
⋮
A_{ℓ}^{ℓ−1} = x_{ℓ}tΔ_{ℓ−1}A_{ℓ} + x_{ℓ}Δ_{ℓ−1}A_{ℓ}^{ℓ−1},
A_{ℓ}^{ℓ} = tΔ_{ℓ}A_{ℓ} + Δ_{ℓ}A_{ℓ}^{ℓ}.

Proof. The theorem follows by treating two separate cases. Let n be the greatest entry in the tableau T. The case when there is one n in a row corresponds to the first summand and the case when there are more than one n in a row corresponds to the second summand. □

When ℓ = 2, A = A_{2}, the system boils down to:

(4.3)  ((1 − x_{2}^{−1})(1 − \frac{x_{1}x_{2}t}{1 − x_{1}x_{2}} ) − x_{2}^{−1}t) A = 1 − x_{2}^{−1}(1 + t)A(x_{2} = 0).

This equation can be solved using the so called kernel method as described in [5]. If we let

x_{2} = \frac{1 + x_{1}(1 + 2t) − \sqrt{(1 + x_{1}(1 + 2t))^{2} − 4x_{1}(1 + t)^{2}}}{2x_{1}(1 + t)} ,

then the parenthesis infront of A in (4.3) cancels, and we get:

A(x_{2} = 0) = \frac{1 + x_{1}(1 + 2t) − \sqrt{(1 + x_{1}(1 + 2t))^{2} − 4x_{1}(1 + t)^{2}}}{2x_{1}(1 + t)^{2}} .

By the interpretation of a(ℓ, k, r), we have that the bi-variate generating function for a(2, k, r) is (1 + x_{1})^{−1}A_{2}(x_{1}, 1, t). From this and (4.1) one may derive an analytic proof of Theorem 4.7.

5. Further results and open problems

5.1. Further directions. Recall that the Stanley-Wilf Conjecture asserts that for any permutation π the limit lim_{n→∞} |S_{n}(π)|^{1/n} exists and is finite. What about the sequence |[n]^{n}(π)|? Problem 5.1. Let π be a permutation. Is there a constant 0 < C < ∞ such |[n]^{n}(π)| ≤ C^{n} for all n ≥ 0?

Note that the answer to Problem 5.1 is no when π is not a permutation, since then S_{n}(π) ⊆ [n]^{n}(π). Again, Problem 5.1 is equivalent to the statement that

lim_{n→∞} |[n]^{n}(π)|^{1/n},

exists and is finite. This is because for all m, n ≥ 0 we have

|[n + m]^{n+m}(π)| ≥ |[n]^{n}(π)| · |[m]^{m}(π)|,

so we may apply Fekete’s Lemma on sub-additive sequences. See [4, Theorem 1] for details (the proof extends to words word for word). For permutations π ∈ S_{3} we have by Corollary 4.10 that lim_{n→∞} |[n]^{n}(π)|^{1/n} = 27/2 as opposed to lim_{n→∞} |S_{n}(π)|^{1/n} = 4.

For which permutations do we know that Problem 5.1 is true? It follows from the work in [3] that Problem 5.1 is true for all permutations which can be written as an increasing sequence followed by a decreasing. Also, with no great effort Bóna’s proof [8] of the Stanley-Wilf conjecture for layered patterns may be extended to this setting. Thus for all classes that the Stanley-Wilf conjecture is known to hold, the seemingly stronger Problem 5.1 holds. The following conjecture therefore seems plausible: Conjecture 5.2. For all permutations π we have:

∃C∀n(|[n]^{n}(p)| ≤ C^{n}) ⇔ ∃D∀n(|S_{n}(p)| ≤ D^{n}).

There are several problems concerning the automatons associated to a pattern that has connections to the above problems. One problem is to give an estimate to the number of simple paths in A(p, k), another is to estimate the number of equivalence classes in A(p, k). Yet another problem is to give an estimate to the maximum size of an equivalence class.

5.2. Formula for |[k]^{n}(p)|. Our algorithm (see Theorem 3.1) for finding a formula for |[k]^{n}(p)| is implemented in C++ and Maple, see [18]. The first with input p and k and output the automaton A(p, k) and the second with input the automaton A(p, k) and output the exact formula for |[k]^{n}(p)|. This algorithm allows us to get an explicit formula for |[k]^{n}(p)| where p ∈ S_{k} and k ≥ 1 are given. For example, an output for the algorithm for p ∈ S_{4} and k = 3, 4, 5, 6 is given by Table 5.2, where we define,

[b_{0}, b_{1}, …, b_{d}]_{x} = ∑_{j=0}^{d} b_{j}\binom{n}{j}x^{n−j}.

Finally we remark that our method can be generalized as follows. Given a set of patterns T we define an equivalence relation ∼_{T} on [k]^{∗} by: v ∼_{T} w if for all words r ∈ [k]^{∗} we have

vr avoids T if and only if wr avoids T,

where a word u avoids T if u avoids all patterns in T. As in Section 2 we define an automaton A(T, k) with the equivalence classes of ∼_{T} as states. With minor changes in the proof, Theorem 3.1 can be extended to avoidance of a set of patterns. For example, if T = {1234, 2134} and k = 5, then by [18] we get that

|[4]^{n}(T)| = 2 · 3^{n} + 2\binom{n}{2}3^{n−2} − 2^{n},
|[5]^{n}(T)| = 3 · 3^{n} + 6\binom{n}{2}3^{n−2} + 6\binom{n}{3}3^{n−3} + 8\binom{n}{4}3^{n−4} − 2 · 2^{n},
|[6]^{n}(T)| = 4 · 3^{n} + 12\binom{n}{2}3^{n−2} + 24\binom{n}{3}3^{n−3}
+54\binom{n}{4}3^{n−4} + 60\binom{n}{5}3^{n−5} + 40\binom{n}{6}3^{n−6} − 3 · 2^{n}.

Acknowledgements. We would like to thank M. Bousquet-Mélou and C. Krattenthaler for interesting discussions, D. Zeilberger for informing us about the work of Wegschaider and Riese, and Wegschaider and Riese for running their program for us.

References

[1] A. V. Aho, R. Sethi, J.D. Ullman, Compilers: principles, techniques and tools, Addison-Wesley, Reading, Mass., 1986.

[2] M. Albert, R. Aldred, M.D. Atkinson, C. Handley, and D. Holton, Permutations of a multiset avoiding permutations of length 3, European Journal of Combinatorics 22 (2001) 1021–1031.

[3] N. Alon and E. Friedgut, On the number of permutations avoiding a given pattern, Journal Combinatorics Theory Series A 89 (2000) 133–140.

[4] R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electronic Journal of Combinatorics 6 (1999) (electronic)

[5] C. Banderier and M. Bousquet-Mélou and A. Denise, and P. Flajolet and D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Formal power series and algebraic combinatorics (Barcelona, 1999). Discrete Mathematics 246 (2002), no. 1-3, 29–55.

[6] M. Bóna, Permutations avoiding certain patterns: the case of length 4 and some generalization, Discrete Mathematics 80 (1997) 257–272.

p  k |[k]^{n}(p)|
1234, 1243 3 [1]_{3}
1432, 2143 4 [1, 1, 1, 1]_{3}
5 [1, 2, 4, 8, 11, 10, 5]_{3}
6 [1, 3, 9, 27, 66, 126, 183, 189, 126, 42]_{3}
7 [1, 4, 16, 64, 221, 632, 1478, 2772, 4074, 4536, 3612, 1848, 462]_{3}
8 [1, 5, 25, 125, 555, 2103, 6735, 18075, 40290, 73770, 109206,
127710, 113850, 72930, 30030, 6006]_{3}
9 [1, 6, 36, 216, 1170, 5508, 22338, 77688, 230823, 583410,
1247076, 2235816, 3322836, 4025736, 3880305, 2867436,
1528956, 525096, 87516]_{3}
10 [1, 7, 49, 343, 2191, 12313, 60361, 257407, 953554, 3064558, 8527666,
20482462, 42268534, 74452378, 110916091, 137998861,

140882742, 115068954, 72390318, 32978946, 9699690, 1385670]_{3}

1324  3 [1]_{3}
4 [1, 1, 1, 1]_{3}
5 [1, 2, 4, 8, 11, 10, 5, 1]_{3}
6 [1, 3, 9, 27, 66, 126, 183, 197, 152, 80, 26, 4]_{3}
7 [1, 4, 16, 64, 221, 632, 1478, 2808, 4308, 5295, 5152, 3895, 2219,
904, 239, 33, 1]_{3}
1342  3 [1]_{3}
4 [1, 1, 1, 1]_{3}
5 [1, 2, 4, 8, 11, 10, 4]_{3}
6 [1, 3, 9, 27, 66, 126, 176, 168, 96, 24]_{3}
1423  3 [1]_{3}
4 [1, 1, 1, 1]_{3}
5 [1]_{2} + [0, 3, 3, 9, 10, 11, 3]_{3}
6 [13, 1]_{2} + [−12, 15, −2, 37, 57, 134, 169, 167, 76, 12]_{3}
2413  3 [1]_{3}
4 [1, 1, 1, 1]_{3}
5 [10, 4, 1]_{2} + [−9, 8, 1, 9, 11, 10, 2]_{3}
6 [96, 28, 5]_{2} + [−95, 71, −36, 54, 52, 132, 167, 137, 44, 4]_{3}

Table 2. Patterns of length 4

[7] M. Bóna, Exact enumeration of 1342-avoiding permutations: A close link with labelled trees and planar maps, Journal Combinatorics Theory Series A 175 (1997) 55–67.

[8] M. Bóna, The solution of a conjecture of Stanley and Wilf for all layered patterns, Journal Combinatorics Theory Series A 85 (1999) 96–104.

[9] A. Burstein, Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[10] A. Burstein and T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electronic Journal of Combinatorics 9:2 (2002), #R3.

[11] I.M. Gessel, Symmetric functions and P -recursiveness, Jounal Combinatorics Theory Series A 53 (1990) 257–285.

[12] J. M. Hammersley, A few seedlings of research, Proceedings Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1, Berkeley/Los Angeles, 1972, University of California Press, 345–394.

[13] C. Hohlweg and C. Reutenauer, Inverses of words and the parabolic structure of the symmetric group, European Journal of Combinatorics 22 (2001) 1075–1082.

[14] M. Klazar, The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, Formal power series and algebraic combinatorics (Moscow,2000), Springer, Berlin (2000) 250–255

[15] D.E. Knuth, The art of computer programming, Volume 1, Fundamental algorithms, Addison Wesley, Reading, Massachusetts, 1973.

[16] D.E. Knuth, The art of computer programming, Volume 3, Fundamental algorithms, Addison Wesley, Reading, Massachusetts, 1973.

[17] L. Lipshitz, D-finite power series, J. Algebra 122 (1989) 353–373.

[18] T. Mansour, Automata word pattern, Maple Programming, Available in <http://math.haifa.ac.il/toufik>.

[19] A. Regev, Asymptotic values for degress associated with strips of Young diagrams, Advances in Mathematics 41 (1981) 115-136.

[20] A. Regev, Asymptotics of the number of k-words with an ℓ-descent, Electronic Journal of Combinatorics 5 (1998), #R15.

[21] D. G. Rogers, Ascending sequences in permutations, Discrete Mathematics 22 (1978) 35–40.

[22] D. Rotem, On a correspondence between binary trees and a certain type of permutation, Info. Proc. Letters 4 (1975) 58–61.

[23] D. Rotem, Stack sortable permutations, Discrete Mathematics 33 (1981) 185–196.

[24] R. Simion and F. Schmidt, Restricted permutations, European Journal of Combinatorics 6 (1985) 383–406.

[25] N. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York, 1995.

[26] R. Stanley, Enumerative Combinatorics, volume 1, Cambridge University Press, Cambridge, 1997.

[27] R. Stanley, Enumerative Combinatorics, volume 2, Cambridge University Press, Cambridge, 1999.

[28] K. Wegschaider and A. Riese, A Mathematica package for proving hypergeometric multi-sum identities, Available in <http://www.risc.uni-linz.ac.at/research/combinat/risc/software>.

[29] J. West, Permutations with forbidden subsequences and stack sortable permutations, Ph.D. Thesis, M.I.T., (1990).

[30] H. Wilf, The patterns of permutations, Discrete Mathematics 257 (2002) 575–583.

[31] J. Wimp and D. Zeilberger, Resurrecting the asymptotics of linear recurrences, Journal Mathematics Anal. Appl. 111 (1985), no. 1, 162–176.