WORDS RESTRICTED BY 3-LETTER GENERALIZED MULTIPERMUTATION PATTERNS

ALEXANDER BURSTEIN AND TOUFIK MANSOUR

Abstract. We find exact formulas and/or generating functions for the number of words avoiding 3-letter generalized multipermutation patterns and find which of them are equally avoided.

1. Introduction

A generalized pattern τ is a (possibly hyphenated) string in [ℓ]^{m} which contains all letters in [ℓ] = {1, …, ℓ}. We say that the string σ ∈ [k]^{n} contains a generalized pattern τ if σ contains a subsequence isomorphic to τ in which the entries corresponding to consecutive entries of τ not separated by a hyphen must be adjacent. Otherwise, we say that σ avoids τ and write σ ∈ [k]^{n}(τ). Thus, [k]^{n}(τ) denotes the set of strings in [k]^{n} (i.e. n-long k-ary strings) which avoid τ.

Example 1.1. An string π = a_{1}a_{2} … a_{n} avoids 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}.

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

Generalized permutation patterns were introduced by Babson and Steingrímsson [1] with the purpose of the study of Mahonian statistics. Later, Claesson [4] and Claesson and Mansour [5] considered the number of permutations avoiding one or two generalized patterns with one hyphen.

In this paper, we consider the case of words avoiding a single generalized pattern of length 3.

We say that two patterns τ_{1} and τ_{2} are Wilf-equivalent or belong to the same Wilf class if |[k]^{n}(τ_{1})| = |[k]^{n}(τ_{2})| for all integers k, n ≥ 0. Given a generalized pattern τ we define its reversal r(τ) to be τ read right-to-left (including hyphens). For example, r(13-2) = 2-31. We also define complement of τ, denoted c(τ), to be the pattern obtained by substituting ℓ+1−τ(i) for τ(i) and leaving hyphens in the same positions (for example, c(13-2) = 31-2). Clearly, c ∘ r = r ∘ c, so ⟨c, r⟩ = D_{2}, the group of symmetries of a rectangle. We call the set {τ, r(τ), c(τ), c(r(τ))} the symmetry class of τ. Obviously, all patterns in the same symmetry class (e.g. 13-2, 2-31, 31-2, 2-13) are Wilf-equivalent, so we only need to consider one representative of each symmetry class to determine Wilf classes.

Date: April 6, 2003.

Let τ be any generalized pattern; we define #τ(σ) as the number of occurrences of τ in σ. Let F_{τ} (n, k; q; a_{1}, …, a_{d}) be the occurrence polynomial, whose coefficient at q^{r} is the number of words in [k]^{n} having exactly r occurrences of τ and ending on a_{1} … a_{d}; that is,

F_{τ} (n, k; q; a_{1}, …, a_{d}) = ∑_{σ∈[k]^{n−d}} q^{#τ(σa_{1}...a_{d})}.

For d = 0, we denote F_{τ} (n, k; q) = F_{τ} (n, k; q; ∅). We also denote the generating function for the sequence {F_{τ} (n, k; q)}_{n≥0} by F_{τ} (x; k; q); that is,

F_{τ} (x, k; q) = ∑_{n≥0} x^{n}F_{τ} (n, k; q) = ∑_{n≥0} ∑_{σ∈[k]^{n}} q^{#τ(σ)}x^{n}.

2. Two-letter generalized patterns

Here, the only symmetry classes with repeated letters are those of generalized patterns 11 and 1-1. However, avoiding 1-1 simply means having no repeated letters, so

|[k]^{n}(1-1)| = \binom{k}{n}n! = (k)_{n},

the n-th lower factorial of k, which is 0 when n > k. Avoiding 11 is the same as having no repeated adjacent letters, so (see Theorem 2.1)

|[k]^{n}(11)| = k(k − 1)^{n−1},

for all n ≥ 1. The remaining symmetry classes is those of patterns 12 and 1-2. A word avoiding 1-2 is just a non-increasing string, so

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

Avoiding 12 means there is no adjacent pair of letters in increasing order, in other words, a string avoiding 12 is a non-increasing string so (see Theorem 2.3)

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

Indeed, the strings avoiding 12 are exactly those avoiding 1-2.

Theorem 2.1. Let τ = 11 … 1 ∈ [1]^{l} be a generalized pattern. Then

F_{τ} (x; k; q) = \frac{1 + (1 − q)x ∑_{j=0}^{l−2}(kx)^{j} − (1 − q)(k − 1) ∑_{d=2}^{l−1} x^{d} ∑_{j=0}^{l−1−d}(kx)^{j}}{1 − (k − 1 + q)x − (k − 1)(1 − q)(1 − x^{l−2})\frac{x^{2}}{1−x}} .

Proof. Let ⟨j⟩_{d} = jj … j, a string of d letters j. Then, by definition,

\begin{aligned}F_{τ} (n, k; q; ⟨j⟩_{d}) & = ∑_{σ∈[k]^{n−d}} q^{#τ(σ,⟨j⟩_{d})} = ∑_{i=1}^{k} ∑_{σ∈[k]^{n−d−1}} q^{#τ(σ,i,⟨j⟩_{d})} = \\ & = ∑_{i≠j} ∑_{σ∈[k]^{n−d−1}} q^{#τ(σ,i,⟨j⟩_{d})} + ∑_{σ∈[k]^{n−d−1}} q^{#τ(σ,⟨j⟩_{d+1})}. \end{aligned}

If we sum over all j = 1, 2, …, k, then for all d ≤ l − 2 we have

∑_{j=1}^{k} F_{τ} (n, k; q; ⟨j⟩_{d}) = (k − 1)F_{τ} (n − d; k; q) + ∑_{j=1}^{k} F_{τ} (n, k; q; ⟨j⟩_{d+1}),

hence

F_{τ} (n, k; q) = (k − 1) ∑_{d=1}^{l−2} F_{τ} (n − d, k; q) + G(n, k; q),

where G(n, k; q) = ∑_{j=1}^{k} ∑_{σ∈[k]^{n−(l−1)}} q^{#τ(σ,⟨j⟩_{l−1})}. Again, by the same above argument it is easy to see

G(n, k; q) = (k − 1)F_{τ} (n − (l − 1), k; q) + qG(n − 1, k; q).

Now consider G_{τ} (n, k; q) − qG_{τ} (n − 1, k; q) together with the two equations above to obtain

F_{τ} (n, k; q) = (k − 1 + q)F_{τ} (n − 1, k; q) + (k − 1)(1 − q) ∑_{d=2}^{l−1} F_{τ} (n − d, k; q),

for all n ≥ l. Besides, F_{τ} (n, k; q) = k^{n} for all n ≤ l−1, hence, taking the generating functions of both sides, we see that the theorem holds. □

Example 2.2. Theorem 2.1 yields for all n ≥ 1,

F_{11}(n, k; q) = k(q + k − 1)^{n−1}.

and

F_{111}(x; k; q) = \frac{1 + x(1 + x)(1 − q)}{1 − (k − 1 + q)x − (k − 1)(1 − q)x^{2}} .

Letting q = 0, we get |[k]^{n}(11)| = k(k − 1)^{n−1}, and

∑_{n≥0} |[k]^{n}(\underbrace{11 … 1}_{l})|x^{n} = \frac{1 + x + ⋯ + x^{l−1}}{1 − (k − 1)x − ⋯ − (k − 1)x^{l−1}} .

For a different approach to the last formula, see [7], Example 6.4 ff., pp. 1102–1103, for an easily generalizable case of k = 2.

We also obtain from the above that the number of strings in [k]^{n} with exactly j occurrences of the generalized pattern 11 is \binom{n−1}{j}k(k − 1)^{n−j−1}.

Theorem 2.3. For all n ≥ 2 and k ≥ 1,

F_{12}(x; k; q) = \frac{1}{1 + \frac{1−(1+(1−q)x)^{k}}{1−q}} .

Proof. By definitions,

F_{12}(n, k; q; j) = ∑_{i=1}^{k} ∑_{w∈[k]^{n−2}} q^{#12(wij)} =

= q ∑_{i=1}^{j−1} ∑_{w∈[k]^{n−2}} q^{#12(wi)} + ∑_{i=j}^{k} ∑_{w∈[k]^{n−2}} q^{#12(wi)} =

= (q − 1) ∑_{i=1}^{j−1} ∑_{w∈[k]^{n−2}} q^{#12(wi)} + ∑_{i=1}^{k} ∑_{w∈[k]^{n−2}} q^{#12(wi)} =

= F_{12}(n − 1, k; q) + (q − 1) ∑_{i=1}^{j−1} ∑_{w∈[k]^{n−2}} q^{#12(wi)}.

Besides, F_{12}(n, k; q; 1) = F_{12}(n − 1, k; q), hence it is easy to see by induction on j that

F_{12}(n, k; q; j) = ∑_{i=0}^{j−1} \binom{j − 1}{i}(q − 1)^{i}F_{12}(n − 1 − i, k; q).

Therefore, for all n ≥ 1,

\begin{aligned}F_{12}(n, k; q) & = ∑_{j=1}^{k} ∑_{i=0}^{j−1} \binom{j − 1}{i}(q − 1)^{i}F_{12}(n − 1 − i, k; q) = \\ & = ∑_{j=1}^{k} \binom{k}{j}(q − 1)^{j−1}F_{12}(n − j, k; q). \end{aligned}

Besides, F_{12}(0, k; q) = 1, hence the theorem holds for the generating function F_{12}(x; k; q). □

3. Three-letter generalized patterns

This section is divided into three subsections corresponding to the three cases of 3-letter generalized patterns: classical patterns, patterns with exactly one adjacent pair of letters, and patterns without internal dashes (i.e. with three consecutive letters).

3.1. Classical patterns. The symmetry class representatives are 1-2-3, 1-3-2, 1-1-2, 1-2-1, 1-1-1. It is known [2] that

|[k]^{n}(1-2-3)| = |[k]^{n}(1-3-2)| = 2^{n−2(k−2)} ∑_{j=0}^{k−2} a_{k−2,j}\binom{n + 2j}{n},

where

a_{k,j} = ∑_{m=j}^{k} C_{m}D_{k−m}, D_{t} = \binom{2t}{t}, C_{t} = \frac{1}{t + 1}\binom{2t}{t}.

Recently, it was shown in [3] that

|[k]^{n}(1-1-1)| = ∑_{i=0}^{k} \binom{k}{i}\binom{i}{n − i}\frac{n!}{2^{n−i}} = ∑_{i=0}^{k} B(i, n − i)(k)_{i},

where (k)_{i} is the falling factorial, and B(r, s) = \frac{(r + s)!}{2^{s}(r − s)!s!} is the Bessel number

of the first kind. In particular, f_{1-1-1}(n, k) = 0 when n > 2k. It was also proved in [3] that

|[k]^{n}(1-2-1)| = |[k]^{n}(1-1-2)| = ∑_{j=0}^{k} \binom{n + k − j − 1}{n}c(n, n − j),

where c(n, j) is the signless Stirling number of the first kind.

3.2. Generalized patterns with exactly one adjacent pair of letters. Let F_{τ} (x; k) be the generating function for the sequence {f_{τ} (n, k)}_{n≥0} where f_{τ} (n, k) = |[k]^{n}(τ)|; that is,

F_{τ} (x; k) = ∑_{n≥0} f_{τ} (n, k)x^{n}.

In the current subsection, we find explicit formulas or recurrence formulas for F_{τ} (x; k) where τ is a three-letter generalized pattern with exactly one adjacent pair of letters. The symmetry class representatives are 11-1, 11-2, 21-1, 21-2, 12-3, 21-3 and 13-2. We will now find F_{τ} (x; k) for each of the above patterns.

Theorem 3.1. For all k ≥ 1,

\begin{aligned}F_{11-1}(x; k) & = |\begin{matrix}B_{k}(x) & −A_{k}(x) & 0 & … & 0 \\ B_{k−1}(x) & 1 & −A_{k−1}(x) & … & 0 \\ B_{k−2}(x) & 0 & 1 & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ B_{2}(x) & 0 & 0 & ... & −A_{2}(x) \\ B_{1}(x) + A_{1}(x) & 0 & 0 & … & 1 \end{matrix}| \\ & = ∏_{i=1}^{k} A_{i}(x) + ∑_{j=1}^{k} (B_{j}(x) ∏_{i=j+1}^{k} A_{i}(x)) \end{aligned}

where A_{j}(x) = \frac{jx^{2}}{1−(j−1)x} and B_{j}(x) = \frac{1+x}{1−(j−1)x}.

Proof. Let a_{n,k} = |[k]^{n}(11-1)|, and let a_{n,k}(i_{1}, …, i_{d}) be the number of all words σ ∈ [k]^{n}(11-1) such that σ_{j} = i_{j} for all j = 1, 2, … d. Then it follows that a_{n,k} = ∑_{i=1}^{k} a_{n,k}(i). On the other hand, a_{n,k}(i) = ∑_{j=1}^{k} a_{n,k}(i, j), a_{n,k}(i, j) = a_{n−1,k}(j) for i ≠ j, and a_{n,k}(i, i) = a_{n−2,k−1}. Therefore,

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

for all n ≥ 2 and k ≥ 1. Besides, a_{1,k} = k and a_{0,k} = 1, hence, for all k ≥ 1,

F_{11-1}(x; k) = \frac{1 + x}{1 − (k − 1)x} + \frac{kx^{2}}{1 − (k − 1)x}F_{11-1}(x; k − 1),

and F_{11-1}(x; 0) = 1. The rest follows by induction on k. □

Theorem 3.2. For all k ≥ 1,

F_{11-2}(x; k) = ∏_{j=0}^{k−1} \frac{1 − (j − 1)x}{1 − (j + x)x}.

Proof. Let σ ∈ [k]^{n}(11-2); then there are f_{11-2}(n, k − 1) such words where σ_{j} ≠ k for all j. Let f_{11-2}(n, k; j) be the number of words σ ∈ [k]^{n}(11-2) where σ_{j} = k and j is minimal, then σ = σ_{1}kσ_{2} for some σ_{1} ∈ [k − 1]^{j−1}(11) and σ_{2} ∈ [k]^{n−j}(11-2). Moreover, for all σ_{1} and σ_{2} as above, we have σ = σ_{1}kσ_{2} ∈ [k]^{n}(11-2), so

\begin{aligned}f_{11-2}(n, k) & = f_{11-2}(n, k − 1) + ∑_{j=1}^{n} f_{11-2}(n, k; j) \\ f_{11-2}(n, k; j) & = f_{11}(j − 1, k − 1)f_{11-2}(n − j, k) \end{aligned}

so

∑_{j=1}^{n} f_{11-2}(n, k; j) = f_{11-2}(n − 1, k) + ∑_{j=2}^{n} f_{11}(j − 1, k − 1)f_{11-2}(n − j, k).

Hence, from the Example 2.2, we get that, for all n ≥ 1,

f_{11-2}(n, k) = f_{11-2}(n, k − 1) + f_{11-2}(n − 1, k) + ∑_{j=0}^{n−2}(k − 1)(k − 2)^{j}f_{11-2}(n − 2 − j, k).

In addition, f_{11-2}(0, k) = δ_{0,k}, hence

F_{11-2}(x; k) = \frac{1 − (k − 2)x}{1 − (k − 1)x − x^{2}} F_{11-2}(x; k − 1).

The rest follows easily. □

Example 3.3. For k = 1, 2, Theorem 3.2 yields F_{11-2}(x; 1) = \frac{1}{1−x} and F_{11-2}(x; 2) = \frac{1}{(1−x)(1−x−x^{2})}. In other words, f_{11-2}(n, 1) = 1 and f_{11-2}(n, 2) = F_{n+3} − 1, where F_{n+3} is the (n + 3)-rd Fibonacci number.

Theorem 3.4. Patterns 21-1 and and 21-2 are Wilf-equivalent, and we have, for k ≥ 0,

F_{21-2}(x; k) = F_{21-1}(x; k) = 1 + ∑_{d=0}^{k−1} (x^{d+1}F_{21-1}(x; k − d) ∑_{i=d}^{k−1} (1 − x)^{i−d}\binom{i}{d}).

Proof. Let us find F_{21-1}(x; k) and F_{21-2}(x; k) to prove that the two are equal. Let us derive the formula for F_{21-1}(x; k). Let g_{n;k}(i_{1}, …, i_{d}) be the number of words w in [k]^{n}(21-1) such that w_{j} = i_{j} for

all j = 1, 2, …, d (in other words, w begins with the string i_{1} … i_{d}).

Consider g_{n,k}(i, j). There are two cases. If j ≥ i, then the first i cannot be part of any 21-1 in a word w beginning with (i, j) and places no further restrictions on the rest of the w, so g_{n,k}(i, j) = g_{n−1,k}(j) if j ≥ i. If j < i, then deleting the first i from w starting with (i, j), we get a word w′ ∈ [k]^{n−1}(21-1) which contains exactly one j, namely, as the first letter. Now let w′′ ∈ [k − 1]^{n−1} be the word obtained from w′ by subtracting 1 from each letter > j. Obviously, this is mapping is a bijection onto the set of words in [k − 1]^{n−1}(21-1) starting with j (since neither it nor its inverse, i.e. adding one to each letter ≥ j except the first letter, creates any new occurrences of 21-1). Thus, g_{n,k}(i, j) = g_{n−1,k−1}(j) if j < i.

\begin{aligned}g_{n,k}(i) & = ∑_{j=1}^{k} g_{n,k}(i, j) = ∑_{j=1}^{i−1} g_{n−1,k−1}(j) + ∑_{j=i}^{k} g_{n−1,k}(j) \\ & = f_{21-1}(n − 1, k) + ∑_{j=1}^{i−1} (g_{n−1,k−1}(j) − g_{n−1,k}(j)). \end{aligned} ; (3.1)

We can show by induction on d that (3.1) implies

g_{n,k}(d) = ∑_{j=0}^{d−1} \binom{d − 1}{j} ∑_{i=0}^{d−1−j} \binom{d − 1 − j}{i}(−1)^{i}f_{21-1}(n − 1 − i − j, k − j).

Hence for all n ≥ 1,

f_{21-1}(n, k) = ∑_{d=1}^{k} ∑_{j=0}^{d−1} \binom{d − 1}{j} ∑_{i=0}^{d−1−j} \binom{d − 1 − j}{i}(−1)^{i}f_{21-1}(n − 1 − i − j, k − j)

with f_{21-1}(0, k) = 1.

If we multiply through by x^{n} and sum over all n ≥ 1, we get

F_{21-1}(x; k) − 1 = ∑_{d=1}^{k} ∑_{j=0}^{d−1} \binom{d − 1}{j}x^{j+1}(1 − x)^{d−1−j}F_{21-1}(x; k − j),

which means that

F_{21-1}(x; k) − 1 = ∑_{d=0}^{k−1} (x^{d+1}F_{21-1}(x; k − d) ∑_{i=d}^{k−1} (1 − x)^{i−d}\binom{i}{d}).

Now let us find the formula for F_{21-2}(x; k).

Similarly, we define h_{n,k}(i_{1}, …, i_{d}) to be the number of words w in [k]^{n}(21-2) such that w_{j} = i_{j} for all j = 1, 2, …, d. As before, h_{n,k}(i, j) = h_{n−1,k}(j) if j ≥ i. If j < i and w ∈ [k]^{n}(21-2) starts with (i, j), then w must contain only one i. Thus, deleting i and subtracting 1 from each letter > i is a bijection from the set of words in [k]^{n}(21-2) that start with (i, j) onto the set of words in [k − 1]^{n−1}(21-2) that start with j. Therefore, h_{n,k}(i, j) = h_{n−1,k−1}(j) if j < i, so it is easy to see that h_{n,k}(i) satisfies the same recurrence 3.1 as g_{n,k}(i), i.e.

h_{n,k}(i) = f_{21-2}(n − 1, k) + ∑_{j=1}^{i−1} (h_{n−1,k−1}(j) − h_{n−1,k}(j)).

Noting that g_{n,k}(i) and h_{n,k}(i) are the same when n = 0, 1 or k = 0, 1, we see that F_{21-1}(x; k) = F_{21-2}(x; k) for k ≥ 0. □

Example 3.5.

\begin{aligned}F_{21-2}(x; 0) & = F_{21-1}(x; 0) = 1 \\ F_{21-2}(x; 1) & = F_{21-1}(x; 1) = \frac{1}{1 − x} \\ F_{21-2}(x; 2) & = F_{21-1}(x; 2) = \frac{1}{(1 − x)^{2}} + \frac{x^{2}}{(1 − x)^{3}} \\ F_{21-2}(x; 3) & = F_{21-1}(x; 3) = \frac{1 − 3x + 6x^{2} − 5x^{3} + 3x^{4} − x^{5}}{(1 − x)^{6}} \end{aligned}

Theorem 3.6. Patterns 12-3 and 21-3 are Wilf-equivalent, and for all k ≥ 1,

F_{12-3}(x; k) = F_{21-3}(x; k) = ∏_{j=0}^{k−1} \frac{1}{1 − \frac{x}{(1−x)^{j}}} .

Proof. Let σ = (σ′, k, σ′′) ∈ [k]^{n} such that σ_{j} = k and j is minimal. (Note that there are f_{12-3}(n; k − 1) (respectively, f_{21-3}(n; k − 1)) words avoiding 12-3 (respectively, 21-3) where such j does not exist.) Hence, σ avoids 12-3 (respectively, 21-3) if and only if σ′ ∈ [k − 1]^{j−1} avoids 12 (respectively, 21) and σ′′ ∈ [k]^{n−j} avoids 12-3 (respectively, 21-3). Theorem 2.3 yields for all n ≥ 0 and k ≥ 2,

\begin{aligned}f_{12-3}(n, k) & = f_{12-3}(n, k − 1) + ∑_{j=1}^{n} \binom{j − 1 + k − 2}{k − 2}f_{12-3}(n − j, k), \\ f_{21-3}(n, k) & = f_{21-3}(n, k − 1) + ∑_{j=1}^{n} \binom{j − 1 + k − 2}{k − 2}f_{21-3}(n − j, k). \end{aligned}

Since f_{12-3}(n, 1) = f_{21-3}(n, 1) = 1 as well, we get that F_{12-3}(x; k) = F_{21-3}(x; k) and

F_{12-3}(x; k) = F_{12-3}(x; k − 1) + \frac{x}{(1 − x)^{k−1}} F_{12-3}(x; k).

□

Lemma 3.7. Let a_{n,k}(i) be the number of words σ ∈ [k]^{n}(13-2) such that σ_{1} = i. Then, for n ≥ 1, k ≥ 0

f_{13-2}(n, k) = ∑_{j=1}^{k} a_{n,k}(j), a_{n,k}(j) = ∑_{i=1}^{j+1} a_{n−1,k}(i) + ∑_{i=j+1}^{k−1} a_{n−1,i}(j + 1).

In addition, f_{13-2}(n, 1) = 1 for all n.

Proof. The first identity holds by definition, and

a_{n,k}(j) = ∑_{i=1}^{k} a_{n,k}(j, i) = ∑_{i=1}^{j+1} a_{n,k}(j, i) + ∑_{i=j+2}^{k} a_{n,k}(j, i),

where a_{n,k}(j, i) is the number of σ ∈ [k]^{n}(13-2) such that σ_{1} = j and σ_{2} = i. If i ≤ j + 1, then the first letter j places no restriction on the rest of σ, so a_{n,k}(j, i) = a_{n−1,k}(i). If j + 2 ≤ i ≤ k, then the rest of σ (positions 3 to n) may not contain any letters from j + 1 to i − 1 (for a total of i − j − 1 letters), so a_{n,k}(j, i) = a_{n−1,k+j+1−i}(j + 1). Hence

a_{n,k}(j) = ∑_{i=1}^{j+1} a_{n−1,k}(i) + ∑_{i=j+2}^{k} a_{n−1,k+j+1−i}(j + 1).

The rest is easy to obtain. □

We also note that a_{n,k}(k−1) = a_{n,k}(k) = f(n−1, k) and that the second formula in Lemma 3.7 implies

a_{n,k}(j) − a_{n,k}(j − 1) − a_{n,k−1}(j) + a_{n,k−1}(j − 1) =

= \begin{cases}a_{n−1,k}(j + 1) − a_{n−1,k−1}(j), for 2 ≤ j ≤ k − 1, \\ a_{n−1,k}(j + 1) − a_{n−1,k−1}(j) + a_{n−1,k}(j), for j = 1, \\ 0, for j = k. \end{cases}

From Lemma 3.7, it is easy to obtain explicit formulas for small values of k.

Theorem 3.8.

\begin{aligned}F_{13-2}(x; 1) & = \frac{1}{1 − x}, \\ F_{13-2}(x; 2) & = \frac{1}{1 − 2x}, \\ F_{13-2}(x; 3) & = \frac{(1 − x)^{2}}{(1 − 2x)(1 − 3x + x^{2})}, \\ F_{13-2}(x; 4) & = \frac{1 − 4x + 6x^{2} − 3x^{3}}{(1 − 3x)(1 − 2x)(1 − 3x + x^{2})}. \end{aligned}

3.3. Generalized Patterns without internal dashes. The symmetry class representatives are 111, 122, 212, 123, 213. In the current subsection, we find explicit formulas for F_{τ} (x; k) for each of these representatives τ. Example 2.2 yields the following result for 111.

Theorem 3.9. For all k ≥ 1

F_{111}(x; k) = \frac{1 + x + x^{2}}{1 − (k − 1)x − (k − 1)x^{2}} .

Theorem 3.10.

F_{122}(x; k) = \frac{x}{(1 − x^{2})^{k} − (1 − x)}, k ≥ 0.

Proof. Let σ ∈ [k]^{n}(122) where σ contains j letters k. If j = 0, then there are f_{122}(n, k − 1) such words. Let j ≥ 1, σ = (σ′, k, σ′′), and let σ_{r} = k where r minimal (so σ′ does not contain k). If σ_{r+1} ≠ k then σ avoids 122 if and only if σ′ ∈ [k − 1]^{r−1}(122), and σ′′ ∈ [k]^{n−r}(122) such that σ′′_{1} ≠ k, so there are

∑_{r=1}^{n} f_{122}(r − 1, k − 1)(f_{122}(n − r, k) − f_{122}(n − 1 − r, k))

such words. If σ_{r+1} = k, then σ′ = ∅, and σ avoids 122 if and only if σ′′ avoids 122, so there are f_{122}(n − 2, k) such words. Hence

f_{122}(n, k) = f_{122}(n, k − 1) + f_{122}(n − 2, k)

+ ∑_{i=1}^{n} f_{122}(i − 1, k − 1)(f_{122}(n − i, k) − f_{122}(n − 1 − i, k))

for all n ≥ 2 and k ≥ 1, therefore,

f_{122}(n, k) = f_{122}(n, k − 1) + f_{122}(n − 2, k)

+ ∑_{i=0}^{n−1} f_{122}(i, k − 1)f_{122}(n − 1 − i, k) − ∑_{i=0}^{n−1} f_{122}(i, k − 1)f_{122}(n − 2 − i, k)).

In addition, f_{122}(1, 1) = f_{122}(0, 1) = f_{122}(0, 0) = 1 and f_{122}(n, k) = 0 for n < 0, hence, taking the generating functions, we see that

F_{122}(x; k) = F_{122}(x; k − 1) + x^{2}F_{122}(x; k) + (x − x^{2})F_{122}(x; k)F_{122}(x; k − 1).

Now, after dividing through by F_{112}(x; k)F_{112}(x; k − 1) and some routine manipulations, we see that the theorem holds. □

Example 3.11. Theorem 3.10 yields F_{122}(x; 2) = \frac{1}{(1−x)(1−x−x^{2})}, which means f_{122}(n, 2) = F_{n+3} − 1, where F_{n+3} is the (n + 3)-rd Fibonacci number.

Theorem 3.12.

F_{212}(x; k) = \frac{1}{1 − x ∑_{j=0}^{k−1} \frac{1}{1+jx^{2}}} , k ≥ 0.

Proof. Let d_{212}(n, k) be the number of words σ ∈ [k]^{n+1}(212) such that σ_{1} = k, and let D_{212}(x; k) be the generating function for d_{212}(n, k), that is D_{212}(x; k) = ∑_{n≥0} d_{212}(n, k)x^{n}.

Let σ = (σ′, k, σ′′) ∈ [k]^{n}(212) so that σ′ does not contain k. If σ = σ′, then there are f_{212}(n, k−1) such words. Otherwise, σ′ ∈ [k−1]^{j−1} for some j = 1, …, n, so there are f_{212}(j − 1, k − 1)d_{212}(n − j, k) such words. Therefore, for all n ≥ 1,

f_{212}(n, k) = f_{212}(n, k − 1) + ∑_{j=1}^{n} f_{212}(j − 1, k − 1)d_{212}(n − j, k).

In addition, f_{212}(0, k) = 0 for all k ≥ 1, hence

F_{212}(x; k) = (1 + xD_{212}(x; k))F_{212}(x; k − 1).

Now let σ = (k, σ′′) ∈ [k]^{n+1}(212). The first k is not part of any occurrence of 212, so we can delete it to get any word σ′′ ∈ [k]^{n}(212). We can obtain an occurrence of 212 by adding the first k back only if σ = (k, i, k, σ′′′) for some i < k and (k, σ′′′) ∈ [k]^{n−1}(212). Then neither the second nor the third letter of σ can start 212, so the number of such “bad” words is (k − 1)d_{212}(n − 2, k). Hence,

d_{212}(n, k) = f_{212}(n, k) − (k − 1)d_{212}(n − 2, k), n ≥ 2.

Taking generating functions of both sides, we obtain

D_{212}(x; k) = F_{212}(x; k) − (k − 1)x^{2}D_{212}(x; k).

Now, solving the two generating function recurrences above, we get

\frac{1}{F_{212}(x; k)} = \frac{1}{F_{212}(x; k − 1)} − \frac{x}{1 + (k − 1)x^{2}} ,

which implies the theorem. □

Theorem 3.13.

F_{123}(x; k) = \frac{1}{∑_{j=0}^{k} a_{j}\binom{k}{j}x^{j}} , k ≥ 0,

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

Proof. By definition, f_{123}(n; k) = k^{n} for k = 0, 1, 2, so the formulas for F_{123}(x; k) hold for k = 0, 1, 2. Let d_{123}(n, k) be the number of words σ ∈ [k]^{n}(123) such that (σ, k + 1) also avoids 123, and let D_{123}(x; k) be the generating function for d_{123}(n, k) with k fixed.

Lemma 3.14.

D_{123}(x; 3) = \frac{1 − 3x^{2} + x^{3}}{1 − 3x + x^{3}} , F_{123}(x; 3) = \frac{1}{1 − 3x + x^{3}} .

Proof. Let σ ∈ [3]^{n}(123), and let f_{123}(n, k; a_{1}, …, a_{d}) be the number of words σ ∈ [3]^{n}(123) such that σ_{i} = a_{i} for all i = 1, 2 …, d. Deleting the first letter i ∈ {1, 2, 3} of σ, we get a word σ′ ∈ [3]^{n−1}(123). Adjoining i in front of any word σ′ ∈ [3]^{n−1}(123), we get a word σ ∈ [k]^{n}(123) or σ = (1, 2, 3, σ′′) for some σ′′ ∈ [3]^{n−3}(123). Hence,

f_{123}(n, 3) = 3f_{123}(n − 1, 3) − f_{123}(n − 3, 3), n ≥ 3.

Besides, f_{123}(n, 3) = 3^{n} for n = 0, 1, 2, hence the formula for F_{123}(x; 3) holds. Similarly, we have

d_{123}(n, 3) = 3d_{123}(n − 1, 3) − d_{123}(n − 3, 3), n ≥ 4.

Besides, d_{123}(0, 3) = 1, d_{123}(1, 3) = 3, d_{123}(2, 3) = 6, and d_{123}(3, 3) = 18, hence the formula for D_{123}(x; 3) holds as well. □

Now, we are ready to prove the two main recurrences.

Lemma 3.15. For all k ≥ 4,

F_{123}(x; k) = \frac{F_{123}(x; k − 1)}{1 − xD_{123}(x; k − 1)}, D_{123}(x; k) = \frac{x + (1 − x)D_{123}(x; k − 1)}{1 − xD_{123}(x; k − 1)}.

Proof. Let σ = (σ′, k, σ′′) ∈ [k]^{n}(123) be such that σ_{j} = k and σ′ ∈ [k − 1]^{j−1} (the leftmost k is at position j). If σ = σ′ (i.e. σ has no k), then there are f_{123}(n, k − 1) such words, otherwise, there are d_{123}(j − 1, k − 1)f_{123}(n − j, k) of them. Therefore,

f_{123}(n, k) = f_{123}(n, k − 1) + ∑_{j=1}^{n} d_{123}(j − 1, k − 1)f_{123}(n − j, k),

for all n ≥ 1. Besides, f_{123}(0, k) = 0 for k ≥ 1, hence, taking generating functions, we get

F_{123}(x; k) = \frac{F_{123}(x; k − 1)}{1 − xD_{123}(x; k − 1)}.

Similarly, we have for all n ≥ 1,

d_{123}(n, k) = d_{123}(n, k − 1) + ∑_{i=1}^{n−1} d_{123}(i − 1, k − 1)d_{123}(n − i, k),

or, equivalently,

d_{123}(n, k) = d_{123}(n, k − 1) − d_{123}(n − 1, k − 1) + ∑_{i=1}^{n} d_{123}(i − 1, k − 1)d_{123}(n − i, k)

for all n ≥ 1. Besides, d_{123}(0, k) = 1, and d_{123}(n, k) = 0 for n < 0, hence, taking generating functions, we get

D_{123}(x; k) = \frac{x + (1 − x)D_{123}(x; k − 1)}{1 − xD_{123}(x; k − 1)}.

□

Finally, Lemmas 3.14 and 3.15 together yield us Theorem 3.13. We also note that the same Lemmas yield that

D_{123}(x; k) = \begin{matrix}∑ & {k \atop j=0} & b_{j}\binom{k}{j}x^{j} \\ ∑ & {k \atop j=0} & a_{j}\binom{k}{j}x^{j} \end{matrix} , k ≥ 0,

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

Theorem 3.16.

F_{213}(x; k) = \frac{1}{1 − x − x ∑_{i=0}^{k−2} ∏_{j=0}^{i} (1 − jx^{2})}, k ≥ 1,

and F_{213}(x; 0) = 1.

Proof. For k = 0 the theorem is trivial, so we may assume k ≥ 1. Let d_{213}(n, k) be the number of all σ ∈ [k]^{n}(213) such that (σ, k + 1) also avoids 213, and let D_{213}(x; k) be the generating function for d_{213}(n, k) with k fixed.

Similarly to Lemma 3.15 we have

f_{213}(n, k) = f_{213}(n, k − 1) + ∑_{j=1}^{n} d_{213}(j − 1, k − 1)f_{213}(n − j, k), n ≥ 1.

Also, f_{213}(0, k) = 0 for k ≥ 1, hence, taking generating functions, we get

F_{213}(x; k) = \frac{F_{213}(x; k − 1)}{1 − xD_{213}(x; k − 1)}.

Similarly to Lemma 3.15, we have for all n ≥ 1,

d_{213}(n, k) = d_{213}(n, k − 1) + d_{213}(n − 1, k − 1) + d_{213}(n − 2, k − 1)

+ ∑_{i=1}^{n−2} d_{213}(i − 1, k − 1)d_{213}(n − i, k),

or, equivalently,

d_{213}(n, k) = d_{213}(n, k − 1) − (k − 1)d_{213}(n − 2, k − 1)

+ ∑_{i=1}^{n} d_{213}(i − 1, k − 1)d_{213}(n − i, k),

for all n ≥ 1. Besides, d_{213}(0, k) = 1, and d_{213}(n, k) = 0 for n < 0, hence, taking generating functions, we obtain

D_{213}(x; k) = \frac{(1 − (k − 1)x^{2})D_{213}(x; k − 1)}{1 − xD_{213}(x; k − 1)}.

□

We remark that it would be interesting to see to what extent the proofs of the theorems in this section can be automated by using enumeration schemes introduced by Zeilberger [9].

Acknowledgments. The authors are grateful to the anonymous referee for their helpful comments.

References

[1] E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, B44b:18pp, 2000.

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

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

[4] A. Claesson, Generalized pattern avoidance, European J. of Combinatorics 22 (2001) 961– 971.

[5] A. Claesson, T. Mansour, Enumeting permutations avoiding a pair of Babson-Steingrímsson

   patterns, preprint. Available at www.arXiv.org/ps/math.CO/0107044.

[6] D.E. Knuth, The Art of Computer Programming, vols. 1, 3, Addison-Wesley, NY, 1968, 1973.

[7] A.M. Odlyzko, Asymptotic enumeration methods, in Handbook of Combinatorics, ed. by R.L. Graham, M. Grötchel and L. Lovász, MIT Press, 1995, vol. 2, pp. 1063–1230.

[8] R. Simion, F.W. Schmidt, Restricted Permutations, Europ. J. of Combinatorics 6 (1985), 383–406.

[9] D. Zeilberger, Enumeration schemes, and more importantly, their automatic generation, Annals of Comb. 2 (1998), 185–195.

Department of Mathematics, Iowa State University, Ames, IA 50011-2064 USA

  E-mail address: burstein@math.iastate.edu

Department of Mathematics, Chalmers Univeristy of Technology, S-412 96 Göteborg, Sweden

  E-mail address: toufik@math.chalmers.se