PARTIALLY ORDERED GENERALIZED PATTERNS AND k-ARY WORDS

Sergey Kitaev and Toufik Mansour ^{1}

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

                  kitaev@math.chalmers.se, toufik@math.chalmers.se

Abstract

Recently, Kitaev [Ki2] introduced partially ordered generalized patterns (POGPs) in the symmetric group, which further generalize the generalized permutation patterns introduced by Babson and Steingrímsson [BS]. A POGP p is a GP some of whose letters are incomparable. In this paper, we study the generating functions (g.f.) for the number of k-ary words avoiding some POGPs. We give analogues, extend and generalize several known results, as well as get some new results. In particular, we give the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes (that allowed to have repetition of letters), provided we know the g.f. for the number of k-ary words that avoid p.

1. Introduction

Let [k]^{n} denote the set of all the words of length n over the (totally ordered) alphabet [k] = {1, 2, …, k}. We call these words by n-long k-ary words. A generalized pattern τ is a word in [ℓ]^{m} (possibly with dashes between some letters) that contains each letter from [ℓ] (possibly with repetitions). We say that the word σ ∈ [k]^{n} contains a generalized pattern τ, if σ contains a subsequence isomorphic to τ in which the entries corresponding to consecutive entries of τ, which are not separated by a dash, must be adjacent. Otherwise, we say that σ avoids τ and write σ ∈ [k]^{n}(τ). Thus, [k]^{n}(τ) denotes the set of all the words in [k]^{n} that avoid τ. Moreover, if P is a set of generalized patterns then |[k]^{n}(P)| denotes the set all the words in [k]^{n} that avoid each pattern from P simultaneously. Example 1.1. A word π = a_{1}a_{2} … a_{n} avoids the pattern 13-2 if π has no subsequence a_{i}a_{i+1}a_{j} with j > i + 1 and a_{i} < a_{j} < a_{i+1}. Also, π avoids the pattern 121 if it has no subword a_{i}a_{i+1}a_{i+2} such that a_{i} = a_{i+2} < a_{i+1}.

Classical patterns are generalized patterns with all possible dashes (say, 2-1-3-4), in other words, those that place no adjacency requirements on σ. The first case of classical patterns studied was that of permutations avoiding a pattern of length 3 in 𝔖_{3}. Knuth [Kn] found that, for any τ ∈ 𝔖_{3}, |𝔖_{n}(τ)| = C_{n}, the nth Catalan number. Later, Simion and Schmidt [SS] determined the number |𝔖_{n}(P)| of permutations in 𝔖_{n} simultaneously avoiding any given set of patterns P ⊆ 𝔖_{3}. Burstein [Bu] extended this to |[k]^{n}(P)| with P ⊆ 𝔖_{3}. Burstein and Mansour [BM1] considered forbidden patterns with repeated letters. Also, Burstein and Mansour [BM2, BM3] considered forbidden generalized patterns with repeated letters.

1Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

Generalized permutation patterns were introduced by Babson and Steingrímsson [BS] with the purpose of the study of Mahonian statistics. Claesson [C] and Claesson and Mansour [CM] considered the number of permutations avoiding one or two generalized patterns with one dash. Kitaev [Ki1] examined the number of |𝔖_{n}(P)| of permutations in 𝔖_{n} simultaneously avoiding any set of generalized patterns with no dashes. Besides, Kitaev [Ki2] introduced a further generalization of the generalized permutation patterns namely partially ordered generalized patterns.

In this paper we introduce a further generalization of the generalized patterns namely partially ordered generalized patterns in words (POGPs), which is an analogue of POGPs in permutations [Ki2]. A POGP is a generalized pattern some of whose letters are incomparable. For example, if we write τ = 1-1′2′, then we mean that in an occurrence of τ in a word σ ∈ [k]^{n} the letter corresponding to the 1 in τ can be either larger, smaller, or equal to the letters corresponding to 1′ and 2′, whereas the letter corresponding to 1′ must be less than the letter corresponding to 2′. Thus, the word 113425 ∈ [5]^{6} contains seven occurrence of τ, namely 113, 134 twice, 125 twice, 325, and 425.

Following [Ki2], we consider two particular classes of POGPs – shuffle patterns and multi-patterns, which allows us to give an analogue for all the main results of [Ki2] for k-ary words. A multi-pattern is of the form τ = τ_{0}-τ_{1}- ⋯ -τ_{s} and a shuffle pattern of the form τ = τ_{0}-a_{1}-τ_{1}-a_{2}- ⋯ -τ_{s−1}-a_{s}-τ_{s}, where for any i and j, the letter a_{i} is greater than any letter of τ_{j} and for any i ≠ j each letter of τ_{i} is incomparable with any letter of τ_{j}. These patterns are investigated in Sections 3 and 4.

Let τ = τ_{0}-τ_{1}- ⋯ -τ_{s} be an arbitrary multi-pattern and let A_{τ_{i}}(x; k) be the generating function (g.f.) for the number of words in k-letter alphabet that avoid τ_{i} for each i. In Theorem 4.7 we find the g.f., in terms of the A_{τ_{i}}(x; k), for the number of k-ary words that avoid τ. In particular, this allows us to find the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern τ with no dashes, if we only know the g.f. for the number of k-ary words that avoid τ. Thus, in order to apply our results in what follows we need to know how many k-ary words avoid a given ordinary generalized pattern with no dashes. This question was examined, for instance, in [BM1, Sections 2 and 3], [BM2, Section 3] and [BM3, Section 3.3].

2. Definitions and Preliminaries

A partially ordered generalized pattern (POGP) is a generalized pattern where some of the letters can be incomparable. Thus, the letters of a POGP form a poset (see [Stan, Chapter 3]). If letters a and b are incomparable in a POGP τ then in an occurrence of τ in a word σ, the relative order of the letters in σ corresponding to a and b is unimportant. For the POGPs considered in this paper, one can use primes to mark comparable and incomparable letters of a POGP in the following way. If two letters, say 1 and 2, have the same number of primes k ≥ 0, say two, then they are comparable and naturally 1′′ < 2′′. Any two letters with different number of primes, say k ≥ 1 and ℓ ≥ 1, k ≠ ℓ, are incomparable. If a letter of a POGP has no primes, that means that this letter is greater than every letter with one or more primes. Example 2.1. The simplest non-trivial example of a POGP that differs from the ordinary generalized patterns is τ = 1′-2-1′′, where the second letter is the greatest one and the first and the last letters are incomparable to each other. The word σ = 31421 has five occurrences of τ, namely 342, 341, 142, 141, and 121.

Let A_{τ} (x; k) = ∑_{n≥0} a_{τ} (n; k)x^{n} denote the generating function (g.f.) for the numbers a_{τ} (n; k) of words in [k]^{n} avoiding the pattern τ. For τ = 1′-2-1′′, we have

(2.1)  A_{1′-2-1′′}(x; k) = \frac{1}{(1 − x)^{2k−1}} − ∑_{j=1}^{k−1} \frac{x}{(1 − x)^{2j}} .

Indeed, if σ ∈ [k]^{n} avoids τ, and σ contains s > 0 copies of the letter k, then the letters k appear as leftmost or rightmost letters of σ. If σ contains no k then σ ∈ [k − 1]^{n}. So, for all n ≥ 0, we have

a_{τ} (n; k) = a_{τ} (n; k − 1) + 2a_{τ} (n − 1; k − 1) + 3a_{τ} (n − 2; k − 1) + ⋯ + (n + 1)a_{τ} (0; k − 1),

since there are (i + 1)a_{τ} (n − i; k − 1) possibilities to place i letters k into σ, for 0 ≤ i ≤ n. Hence, for all n ≥ 2,

a_{τ} (n; k) − 2a_{τ} (n − 1; k) + a_{τ} (n − 2; k) = a_{τ} (n; k − 1),

together with a_{τ} (0, k) = 1 and a_{τ} (1, k) = k. Multiplying both sides of the recurrence above with x^{n} and summing over all n ≥ 2, we get Equation 2.1. Definition 2.2. If the number of words in [k]^{n}, for each n, that avoid a POGP τ is equal to the number of words that avoid a POGP ϕ, then τ and ϕ are said to be equivalent and we write τ ≡ ϕ.

The reverse R(σ) of a word σ = σ_{1}σ_{2} … σ_{n} is the word σ_{n} … σ_{2}σ_{1}. The complement C(σ) is the word θ = θ_{1}θ_{2} … θ_{n} where θ_{i} = k + 1 − σ_{i} for all i = 1, 2, …, n. For example, if σ = 123331 ∈ [3]^{6}, then R(σ) = 133321, C(σ) = 321113, and R(C(σ)) = 311123. We call these bijections of [k]^{n} to itself trivial. For example, the number of words that avoid the pattern 12-2 is the same as the number of words that avoid the patterns 2-21, 1-12, and 21-1, respectively.

Following [Ki2], it is convenient to introduce the following definition. Definition 2.3. Let τ be a generalized pattern without dashes. A word σ quasi-avoids τ if σ has exactly one occurrence of τ and this occurrence consists of the |τ| rightmost letters of σ, where |τ| denotes the number of letters in τ.

For example, the word 5112234 quasi-avoids the pattern 1123, whereas the words 5223411 and 1123345 do not. Proposition 2.4. Let τ be a non-empty generalized pattern with no dashes. Let A_{τ}^{∗}(x; k) denote the g.f. for the number of words in [k]^{n} that quasi-avoid τ. Then

(2.2)  A_{τ}^{∗}(x; k) = (kx − 1)A_{τ} (x; k) + 1.

Proof. Using the similar arguments as those in the proof of [Ki2, Proposition 4], we get that, for n ≥ 1,

a_{τ}^{∗}(n; k) = ka_{τ} (n − 1; k) − a_{τ} (n; k),

where a_{τ}^{∗}(n; k) denotes the number of words in [k]^{n} that quasi-avoid τ. Multiplying both sides of the last equality by x^{n} and summing over all natural numbers n, we get the desired result. □

Definition 2.5. Suppose {τ_{0}, τ_{1}, …, τ_{s}} is a set of generalized patterns with no dashes and

τ = τ_{0}-τ_{1}- ⋯ -τ_{s},

where each letter of τ_{i} is incomparable with any letter of τ_{j} whenever i ≠ j. We call such POGPs multi-patterns.

Definition 2.6. Suppose {τ_{0}, τ_{1}, …, τ_{s}} is a set of generalized patterns with no dashes and a_{1}a_{2} … a_{s} is a word of s letters. We define a shuffle pattern to be a pattern of the form

τ = τ_{0}-a_{1}-τ_{1}-a_{2}- ⋯ -τ_{s−1}-a_{s}-τ_{s},

where each letter of τ_{i} is incomparable with any letter of τ_{j} whenever i ≠ j, and the letter a_{i} is greater than any letter of τ_{j} for any i and j.

For example, 1′-2-1′′ is a shuffle pattern, and 1′-1′′ is a multi-pattern. From definitions, we obtain that we can get a multi-pattern from a shuffle pattern by removing all the letters a_{i}.

There is a connection between multi-avoidance of the generalized patterns and the POGPs. In particular, to avoid 1′-2-1′′ is the same as to avoid simultaneously the patterns 1-2-1, 1-3-2, and 2-3-1. A straightforward argument leads to the following proposition. Proposition 2.7. For any POGP τ there exists a set T of generalized patterns such that a word σ avoids τ if and only if σ avoids all the patterns in T.

For example, if τ = 1′2′-3-1′′, then to avoid τ is the same to avoid 5 patterns, 12-3-1, 12-3-2, 12-4-3, 13-4-2, and 23-4-1.

3. The shuffle pattern

We recall that according to Definition 2.6, a shuffle pattern is a pattern of the form

τ = τ_{0}-a_{1}-τ_{1}-a_{2}- ⋯ -τ_{s−1}-a_{s}-τ_{s},

where {τ_{0}, τ_{1}, …, τ_{s}} is a set of generalized patterns with no dashes, a_{1}a_{2} … a_{s} is a word of s letters, for any i and j the letter a_{i} is greater than any letter of τ_{j} and for any i ≠ j each letter of τ_{i} is incomparable with any letter of τ_{j}.

Let us consider the shuffle pattern ϕ = τ-ℓ-τ, where ℓ is the greatest letter in ϕ and each letter in the left τ is incomparable with every letter in the right τ. Theorem 3.1. Let ϕ be the shuffle pattern τ-ℓ-τ described above. Then for all k ≥ ℓ,

A_{ϕ}(x; k) = \frac{1}{(1 − xA_{τ} (x; k − 1))^{2}} (A_{ϕ}(x; k − 1) − xA_{τ}^{2}(x; k − 1)).

Proof. We show how to get a recurrence relation on k for A_{ϕ}(x; k), which is the g.f. for the number of words in [k]^{n}(ϕ). Suppose σ ∈ [k]^{n}(ϕ) is such that it contains exactly d copies of the letter k. If d = 0 then the g.f. for the number of such words is A_{ϕ}(x; k − 1). Assume that d ≥ 1. Clearly, σ can be written in the following form:

σ = σ_{0}kσ_{1}k ⋯ kσ_{d},

where σ_{j} is a ϕ-avoiding word on k −1 letters, for j = 0, 1, …, d. There are two possibilities: either σ_{j} avoids τ for all j, or there exists j_{0} such that σ_{j_{0}} contains τ and for any j ≠ j_{0}, the word σ_{j} avoids τ. In the first case, the number of such words is given by the g.f. x^{d}A_{τ}^{d+1}(x; k −1), whereas in the second case, by (d + 1)x^{d}A_{τ}^{d}(x; k − 1)(A_{ϕ}(x; k − 1) − A_{τ} (x; k − 1)). In the last expression, the multiple (d + 1) is the number of ways to choose j, such that σ^{j} has an occurrence of τ, and A_{ϕ}(x; k −1)−A_{τ} (x; k −1) is the g.f. for the number of words avoiding ϕ and containing τ.

Therefore,

A_{ϕ}(x; k) = A_{ϕ}(x; k − 1) + ∑_{d≥1}(d + 1)x^{d}A_{τ}^{d}(x; k − 1)A_{ϕ}(x; k − 1) − ∑_{d≥1} dx^{d}A_{τ}^{d+1}(x; k − 1),

equivalently,

A_{ϕ}(x; k) = A_{ϕ}(x; k − 1) + A_{ϕ}(x; k − 1)\frac{2xA_{τ} (x; k − 1) − x^{2}A_{τ}^{2}(x; k − 1)}{(1 − xA_{τ} (x; k − 1))^{2}} − \frac{xA_{τ}^{2}(x; k − 1)}{(1 − xA_{τ} (x; k − 1))^{2}} .

The rest is easy to check. □

Example 3.2. Let ϕ = 1′-2-1′′. Here τ = 1, so A_{τ} (x; k) = 1 for all k ≥ 1, since only the empty word avoids τ. Hence, according to Theorem 3.1, we have

A_{ϕ}(x; k) = \frac{A_{ϕ}(x; k − 1) − x}{(1 − x)^{2}},

which together with A_{ϕ}(x; 1) = \frac{1}{1−x} (for any n only the word \underbrace{11 … 1}_{n times} avoids ϕ) gives Equation 2.1.

More generally, we consider a shuffle pattern of the form τ_{0}-ℓ-τ_{1}, where ℓ is the greatest element of the pattern. Theorem 3.3. Let ϕ be the shuffle pattern τ-ℓ-ν. Then for all k ≥ ℓ,

A_{ϕ}(x; k) = \frac{1}{(1 − xA_{τ} (x; k − 1))(1 − xA_{ν}(x; k − 1))}(A_{ϕ}(x; k − 1) − xA_{τ} (x; k − 1)A_{ν}(x; k − 1)).

Proof. We proceed as in the proof of Theorem 3.1. Suppose σ ∈ [k]^{n}(ϕ) is such that it contains exactly d copies of the letter k. If d = 0 then the g.f. for the number of such words is A_{ϕ}(x; k − 1). Assume that d ≥ 1. Clearly, σ can be written in the following form:

σ = σ_{0}kσ_{1}k ⋯ kσ_{d},

where σ_{j} is a ϕ-avoiding word on k − 1 letters, for j = 0, 1, …, d. There are two possibilities: either σ_{j} avoids τ for all j, or there exists j_{0} such that σ_{j_{0}} contains τ, σ_{j} avoids τ for all j = 0, 1, …, j_{0} − 1 and σ_{j} avoids ν for any j = j_{0} + 1, …, d. In the first case, the number of such words is given by the g.f. x^{d}A_{τ}^{d+1}(x; k − 1). In the second case, we have

x^{d} ∑_{j=0}^{d} A_{τ}^{j} (x; k − 1)A_{ν}^{d−j}(x; k − 1)(A_{ϕ}(x; k − 1) − A_{τ} (x; k − 1)).

Therefore, we get

\begin{matrix}A_{ϕ}(x; k) = A_{ϕ}(x; k − 1) + A_{ϕ}(x; k − 1) ∑_{d≥1} x^{d} ∑_{j=0}^{d} A_{τ}^{j} (x; k − 1)A_{ν}^{d−j}(x; k − 1) \\ − ∑_{d≥1} x^{d} ∑_{j=1}^{d} A_{τ}^{j} (x; k − 1)A_{ν}^{d+1−j}(x; k − 1), \end{matrix}

equivalently,

A_{ϕ}(x; k) = (A_{ϕ}(x; k − 1) − xA_{τ} (x; k − 1)A_{ν}(x; k − 1)) ∑_{d≥0} x^{d} ∑_{j=0}^{d} A_{τ}^{j} (x; k − 1)A_{ν}^{d−j}(x; k − 1).

Hence, using the identity ∑_{n≥0} x^{n} ∑_{j=0}^{n} p^{j}q^{n−j} = \frac{1}{(1 − xp)(1 − xq)} we get the desired result. □

We now give two corollaries to Theorem 3.3.

Corollary 3.4. Let ϕ = τ_{0}-ℓ-τ_{1} be a shuffle pattern, and let f(ϕ) = f_{1}(τ_{0})-ℓ-f_{2}(τ_{1}), where f_{1} and f_{2} are any trivial bijections. Then ϕ ≡ f(ϕ).

Proof. Using Theorem 3.3, and the fact that the number of words in [k]^{n} avoiding τ (resp. ν) and f_{1}(τ) (resp. f_{2}(ν)) have the same generating functions, we get the desired result. □

Corollary 3.5. For any shuffle pattern τ-ℓ-ν, we have

τ-ℓ-ν ≡ ν-ℓ-τ.

Proof. Corollary 3.4 yields that the shuffle pattern τ-ℓ-ν is equivalent to the pattern τ-ℓ-R(ν), which is equivalent to the pattern R(τ-ℓ-R(ν)) = ν-ℓ-R(τ). Finally, we use Corollary 3.4 one more time to get the desired result. □

4. The multi-patterns

We recall that according to Definition 2.5, a multi-pattern is a pattern of the form τ = τ_{0}-τ_{1}- ⋯ -τ_{s}, where {τ_{0}, τ_{1}, …, τ_{s}} is a set of generalized patterns with no dashes and each letter of τ_{i} is incomparable with any letter of τ_{j} whenever i ≠ j.

The simplest non-trivial example of a multi-pattern is the multi-pattern ϕ = 1-1′2′. To avoid ϕ is the same as to avoid the patterns 1-12, 1-23, 2-12, 2-13, and 3-12 simultaneously. To count the number of words in [k]^{n}(1-1′2′), we choose the leftmost letter of σ ∈ [k]^{n}(1-1′2′) in k ways, and observe that all the other letters of σ must be in a non-increasing order. Using [BM1], for all n ≥ 1, we have

|[k]^{n}(1-1′2′)| = k · \binom{n + k − 2}{n − 1}.

The following theorem is an analogue to [Ki2, Theorem 21]. Theorem 4.1. Let τ = τ_{0}-τ_{1} and ϕ = f_{1}(τ_{0})-f_{2}(τ_{1}), where f_{1} and f_{2} are any of the trivial bijections. Then τ ≡ ϕ.

Proof. First, let us prove that the pattern τ = τ_{0}-τ_{1} is equivalent to the pattern ϕ = τ_{0}-f(τ_{1}), where f is a trivial bijection. Suppose that σ = σ_{1}σ_{2}σ_{3} ∈ [k]^{n} avoids τ and σ_{1}σ_{2} has exactly one occurrence of τ_{0}, namely σ_{2}. Then σ_{3} must avoid τ_{1}, so f(σ_{3}) avoids f(τ_{3}) and σ_{f} = σ_{1}σ_{2}f(σ_{3}) avoids ϕ. The converse is also true, if σ_{f} avoids ϕ then σ avoids τ. Since any word either avoids τ_{0} or can be factored as above, we have a bijection between the class of words avoiding τ and the class of words avoiding ϕ. Thus τ ≡ ϕ.

Now, we use the considerations above as well as the properties of trivial bijections to get

\begin{matrix}τ ≡ τ_{0}-f_{2}(τ_{1}) ≡ R(τ_{0}-f_{2}(τ_{1})) ≡ R(f_{2}(τ_{1}))-R(τ_{0}) ≡ \\ ≡ R(f_{2}(τ_{1}))-f_{1}(R(τ_{0})) ≡ R(f_{2}(τ_{1}))-R(f_{1}(τ_{0})) ≡ f_{1}(τ_{0})-f_{2}(τ_{1}). \end{matrix}

□

Using Theorem 4.1, we get the following corollary, which is an analogue to [Ki2, Corollary 22]. Corollary 4.2. The multi-pattern τ_{0}-τ_{1} is equivalent to the multi-pattern τ_{1}-τ_{0}.

Proof. From Theorem 4.1, using the properties of the trivial bijection R, we get

τ_{0}-τ_{1} ≡ τ_{0}-R(τ_{1}) ≡ R(R(τ_{1}))-R(τ_{0}) ≡ τ_{1}-R(R(τ_{0})) ≡ τ_{1}-τ_{0}.
□

Using induction on s, Corollary 4.2, and proceeding in the way proposed in [Ki2, Theorem 23], we get Theorem 4.3. Suppose we have multi-patterns τ = τ_{0}-τ_{1}- ⋯ -τ_{s} and ϕ = ϕ_{0}-ϕ_{1}- ⋯ -ϕ_{s}, where τ_{1}τ_{2} ⋯ τ_{s} is a permutation of ϕ_{1}ϕ_{2} ⋯ ϕ_{s}. Then τ ≡ ϕ.

The last theorem is an analogue to [Ki2, Theorem 23]. As a corollary to Theorem 4.3, using Theorem 4.1 and the idea of the proof of [Ki2, Corollary 24], we get the following corollary which is an analogue to [Ki2, Corollary 24]. Corollary 4.4. Suppose we have multi-patterns τ = τ_{0}-τ_{1}- ⋯ -τ_{s} and ϕ = f_{0}(τ_{0})-f_{1}(τ_{1})- ⋯ -f_{s}(τ_{s}), where f_{i} is an arbitrary trivial bijection. Then τ ≡ ϕ.

The following theorem is a good auxiliary tool for calculating the g.f. for the number of words that avoid a given POGP. For particular POGPs, it allows to reduce the problem to calculating the g.f. for the number of words that avoid another POGP which is shorter. We recall that A_{τ}^{∗}(x; k) is the generating function for the number of words in [k]^{n} that quasi-avoid the pattern τ. Theorem 4.5. Suppose τ = τ_{0}-ϕ, where ϕ is an arbitrary POGP, and the letters of τ_{0} are incomparable to the letters of ϕ. Then for all k ≥ 1, we have

A_{τ} (x; k) = A_{τ_{0}}(x; k) + A_{ϕ}(x; k)A_{τ_{0}}^{∗}(x; k).

Proof. Suppose σ = σ_{1}σ_{2}σ_{3} ∈ [k]^{n} avoids the pattern τ, where σ_{1}σ_{2} quasi-avoids the pattern τ_{0}, and σ_{2} is the occurrence of τ_{0}. Clearly, σ_{3} must avoid ϕ. To find A_{τ} (x; k), we observe that there are two possibilities: either σ avoids τ_{0}, or σ does not avoid τ_{0}. In these cases, the g.f. for the number of such words is equal to A_{τ_{0}}(x; k) and A_{ϕ}(x; k)A_{τ_{0}}^{∗}(x; k) respectively (the second term came from the factorization above). Thus, the statement is true. □

Corollary 4.6. Let τ = τ_{1}-τ_{2}- ⋯ -τ_{s} be a multi-pattern such that τ_{j} is equal to either 12 or 21, for j = 1, 2, …, s. Then

A_{τ} (x; k) = \frac{1 − (1 + \frac{kx−1}{(1−x)^{k}} )^{s}}{1 − kx} .

Proof. According to [BM2], A_{12}(x; k) = A_{21}(x; k) = \frac{1}{(1−x)^{k}}. Using Theorem 4.5, Proposition 2.4 and induction on s, we get the desired result. □

More generally, using Theorem 4.5 and Proposition 2.4, we get the following theorem that is the basis for calculating the number of words that avoid a multi-pattern, and therefore is the main result for multi-patterns in this paper. Theorem 4.7. Let τ = τ_{1}-τ_{2}- ⋯ -τ_{s} be a multi-pattern. Then

A_{τ} (x; k) = ∑_{j=1}^{s} A_{τ_{j}}(x; k) ∏_{i=1}^{j−1}((kx − 1)A_{τ_{i}}(x; k) + 1).

5. The distribution of non-overlapping generalized patterns

A descent in a word σ ∈ [k]^{n} is an i such that σ_{i} > σ_{i+1}. Two descents i and j overlap if j = i + 1. We define a new statistics, namely the maximum number of non-overlapping descents, or MND, in a word. For example, MND(33211) = 1 whereas MND(13211143211) = 3. One can find the distribution of this new statistic by using Corollary 4.6. This distribution is given in Example 5.2. However, we prove a more general theorem: Theorem 5.1. Let τ be a generalized pattern with no dashes. Then for all k ≥ 1,

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{τ} (σ)}x^{n} = \frac{A_{τ} (x; k)}{1 − y((kx − 1)A_{τ} (x; k) + 1)},

where N_{τ} (σ) is the maximum number of non-overlapping occurrences of τ in σ.

Proof. We fix the natural number s and consider the multi-pattern Φ_{s} = τ-τ- ⋯ -τ with s copies of τ. If a word avoids Φ_{s} then it has at most s − 1 non-overlapping occurrences of τ. Theorem 4.7 yields

A_{Φ_{s}}(x; k) = ∑_{j=1}^{s} A_{τ} (x; k) ∏_{i=1}^{j−1}((kx − 1)A_{τ} (x; k) + 1).

So, the g.f. for the number of words that has exactly s non-overlapping occurrences of the pattern τ is given by

A_{Φ_{s+1}}(x; k) − A_{Φ_{s}}(x; k) = A_{τ} (x; k)((kx − 1)A_{τ} (x; k) + 1)^{s}.

Hence,

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{τ} (σ)}x^{n} = ∑_{s≥0} A_{τ} (x; k)((kx − 1)A_{τ} (x; k) + 1)^{s} = \frac{A_{τ} (x; k)}{1 − y((kx − 1)A_{τ} (x; k) + 1)}.

□

All of the following examples are corollaries to Theorem 5.1. Example 5.2. If we consider descents (the pattern 12) then A_{12}(x; k) = \frac{1}{(1−x)^{k}} (see [BM2]), hence the distribution of MND is given by the formula:

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{12}(σ)}x^{n} = \frac{1}{(1 − x)^{k} + y(1 − kx − (1 − x)^{k})}.

Example 5.3. The distribution of the maximum number of non-overlapping occurrences of the pattern 122 is given by the formula:

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{122}(σ)}x^{n} = \frac{x}{(1 − x^{2})^{k} + x − 1 + y(1 − kx^{2} − (1 − x^{2})^{k})},

since according to [BM3, Theorem 3.10], A_{122}(x; k) = \frac{x}{(1−x^{2})^{k}−(1−x)}.

Example 5.4. If we consider the pattern 212 then A_{212}(x; k) = (1 − x ∑_{j=0}^{k−1} \frac{1}{1 + jx^{2}} )^{−1} (see [BM3,

Theorem 3.12]), hence the distribution of the maximum number of non-overlapping occurrences of the pattern 212 is given by the formula:

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{212}(σ)}x^{n} = \frac{1}{1 − x ∑_{j=0}^{k−1} \frac{1}{1 + jx^{2}} + xy (∑_{j=0}^{k−1} \frac{1}{1 + jx^{2}} − k)}.

Example 5.5. Using [BM3, Theorem 3.13], the distribution of the maximum number of non-overlapping occurrences of the pattern 123 is given by the formula:

∑_{n≥0} ∑_{σ∈[k]^{n}} y^{N_{123}(σ)}x^{n} = \frac{1}{∑_{j=0}^{k} a_{j}\binom{k}{j}x^{j} + y (1 − kx − ∑_{j=0}^{k} a_{j}\binom{k}{j}x^{j})},

where a_{3m} = 1, a_{3m+1} = −1, and a_{3m+2} = 0, for all m ≥ 0.

References

[BS] E. Babson, E. Steingrímsson: Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. de Combin., B44b:18pp, (2000).

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

[BM1] A. Burstein and T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electronic J. Combin. 9:2 (2002), #R3.

[BM2] A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, preprint CO/0112281.

[BM3] A. Burstein and T. Mansour, Counting occurrences of some subword patterns, Discrete Math. and Theor. Comp. Sci. 6:1 (2003), 1–12.

[C] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), 961-971.

[CM] A. Claesson and T. Mansour, Enumerating Permutations Avoiding a Pair of Babson-Steingrímsson Patterns, preprint CO/0107044.

[Ki1] S. Kitaev, Multi-avoidance of generalised patterns, Discrete Math. 260 (2003), 89-100.

[Ki2] S. Kitaev, Partially ordered generalized patterns, Discrete Math., to appear.

[Kn] D. E. Knuth: The Art of Computer Programming, 2nd ed. Addison Wesley, Reading, MA, (1973).

[SS] R. Simion, F. Schmidt: Restricted permutations, European J. Combin. 6, no. 4 (1985), 383–406.

[Stan] R. P. Stanley: Enumerative Combinatorics, Vol. 1, Cambridge University Press, (1997).