Séminaire Lotharingien de Combinatoire 46 (2001), Article B46g

PATTERN AVOIDANCE IN COLOURED PERMUTATIONS

TOUFIK MANSOUR

Department of Mathematics, University of Haifa, Haifa, Israel 31905

                          E-mail: tmansur@study.haifa.ac.il

Abstract. Let S_{n} be the symmetric group, C_{r} the cyclic group of order r, and let S_{n}^{(r)} be the wreath product of S_{n} and C_{r}; which is the set of all coloured permutations on the symbols 1, 2, …, n with colours 1, 2, …, r, which is the analogous of the symmetric group when r = 1, and the hyperoctahedral group when r = 2. We prove, for every 2letter coloured pattern ϕ ∈ S_{2}^{(r)}, that the number of ϕ-avoiding coloured permutations in S_{n}^{(r)} is given by the formula ∑_{j=0}^{n} j!(r − 1)^{j}\binom{n}{j}^{2}. Also we prove that the number of Wilf classes of restricted coloured permutations by two patterns with r colours in S_{2}^{(r)} is one for r = 1, is four for r = 2, and is six for r ≥ 3.

1. Introduction

The goal of this note is to give analogies of enumerative results on certain classes of permutations characterized by pattern-avoidance in the symmetric group, and in the hyperoctahedral group. In S_{n}^{(r)}, the natural analogue of the symmetric group and of the hyperoctahedral group, we identify classes of restricted coloured permutations with enumerative properties analogous to results in the symmetric group and hyperoctahedral group. In the remainder of this section we present a brief account of earlier work which motivated out investigation, summarize the main results, and present the basic definitions used throughout the note.

Pattern avoidance in the symmetric group proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting [K, T, W] to the theory of Kazhdan-Lusztig polynomials [Br], singularities of Schubert varieties [LS, Bi], Chebyshev polynomials [CW, MV1, Kr, MV2, MV3], and rook polynomials [MV4]. Signed pattern avoidance in the hyperoctahedral group proved to be a useful language in combinatorial statistics defined in type-B noncrossing partitions, enumerative combinatorics [S, BS], algebraic combinatorics [FK, BK, Be, M, R].

Let π ∈ S_{n} and τ ∈ S_{k} be two permutations. An occurrence of τ in π is a subsequence 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (π_{i_{1}}, …, π_{i_{k}}) is order-isomorphic to τ; in such a context τ is usually called a pattern. We say that π avoids τ, or is τ-avoiding, if there is no occurrence of τ in π. The set of all τ-avoiding permutations in S_{n} is denoted by S_{n}(τ). For an arbitrary finite collection of patterns T, we say that π avoids T if π avoids any τ ∈ T; the corresponding subset of S_{n} is denoted by S_{n}(T). The first case examined was the case of permutations avoiding one pattern of length 3. Knuth [K] found that |S_{n}(τ)| = C_{n} for all τ ∈ S_{3}, where C_{n} is the nth Catalan number. Later, Simion and Schmidt [SS] found the cardinalities of |S_{n}(T)| for all T ⊂ S_{3}.

The hyperoctahedral group B_{n} is an analog of the symmetric group S_{n}. Let us view the elements of B_{n} as signed permutation b = b_{1}b_{2} … b_{n} in which each of the symbols 1, 2, …, n appears once, possibly barred. Thus, the cardinality of B_{n} is n!2^{n}. Simion [S] was looking for the analogs of Knuth’s results for B_{n}; she discovered that for every 2-letter signed pattern τ; the number of τ-avoiding signed permutations in B_{n} is ∑_{j=0}^{n} \binom{n}{j}^{2}j!. Also Simion [S] found the number of all coloured permutations in B_{n} avoiding double 2-letter signed patterns in B_{2}. This invites us to define a further generalizations for avoiding a pattern in the symmetric group S_{n} and avoiding a signed pattern in the hyperoctahedral group B_{n}.

The group S_{n}^{(r)} = S_{n} ≀ C_{r} where C_{r} is the cyclic group of order r, is an analog of the symmetric group (S_{n}) and of the hyperoctahedral group (B_{n}). We will view the elements of the set S_{n}^{(r)} as coloured permutations ϕ = (ϕ_{1}, ϕ_{2}, …, ϕ_{n}) in which each of the symbols 1, 2, …, n appears once, coloured by one of the colours 1, 2, …, r (more generally, we denote by S_{{a_{1},...,a_{n}}}^{{s_{1},...,s_{r}}} the set of all permutations of the symbols a_{1}, …, a_{n} where each symbol appears once and is coloured by one of the colours s_{1}, …, s_{r}). Thus, S_{n}^{(1)} = S_{n}, S_{n}^{(2)} = B_{n}, and the cardinality of S_{n}^{(r)} is n!r^{n}. The absolute value notation means |ϕ| is the permutation (|ϕ_{1}|, …, |ϕ_{n}|) where |ϕ_{j}| is the symbol which appear in ϕ at the position j. An example ϕ = (1^{(1)}, 3^{(2)}, 2^{(1)}) is a coloured permutation in S_{3}^{(2)}, and |ϕ| = (1, 3, 2).

Let ϕ = (τ_{1}^{(s_{1})}, …, τ_{k}^{(s_{k})}) ∈ S_{k}^{(r)}, and ψ = (α_{1}^{(v_{1})}, …, α_{n}^{(v_{n})}) ∈ S_{n}^{(r)}; we say that ψ contains ϕ (or is ϕ-containing) if there is a sequence of k indices, 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that the following two conditions hold:

(i) (α_{i_{1}}, …, α_{i_{k}}) is order-isomorphic to |ϕ|; (ii) v_{i_{j}} = s_{j} for all j = 1, 2, …, k.

Otherwise, we say that ψ avoids ϕ (or is ϕ-avoiding). The set of all ϕ-avoiding coloured permutations in S_{n}^{(r)} is denoted by S_{n}^{(r)}(ϕ), and in this context ϕ is called a coloured pattern. For an arbitrary finite collection of coloured patterns T, we say that ψ avoids T if ψ avoids any ϕ ∈ T; the corresponding subset of S_{n}^{(r)} is denoted by S_{n}^{(r)}(T). As an example, ψ = (3^{(1)}, 2^{(2)}, 1^{(2)}) ∈ S_{3}^{(2)} avoids (2^{(1)}, 1^{(1)}); that is, ψ ∈ S_{3}^{(2)}((2^{(1)}, 1^{(1)})).

Let T_{1}, T_{2} be two subsets of coloured patterns; we say that T_{1}, T_{2} ⊂ S_{k}^{(r)} are in the same Wilf class if |S_{n}^{(r)}(T_{1})| = |S_{n}^{(r)}(T_{2})| for n ≥ 0 (see [W]).

In the symmetric group S_{n}, for every 2-letter pattern τ the number of τ-avoiding permutations is one, and for every pattern τ ∈ S_{3} the number of τ-avoiding permutations is given by the Catalan number [K]. Also Simion [S] proved there are similar results for the hyperoctahedral group B_{n}. Here we are looking for similar results for S_{n}^{(r)}. We show that for every 2-letter coloured pattern ϕ the number of ϕ-avoiding coloured permutations in S_{n}^{(r)} is given by ∑_{j=0}^{n} j!(r−1)^{j}\binom{n}{j}^{2}, which generalizes the results of [S, Sec. 3].

The paper is organized as follows: the elementary definitions, and the symmetric operations, are treated in Section 2. In Section 3 we give two relations between avoidance of patterns in S_{k} and avoidance of coloured patterns in S_{k}^{(r)}. In Section 4 we present two sets of coloured patterns, and produce a bijection which gives a combinatorial geometric explanation for one of these results. Finally, in Sections 5 and 6 respectively, we prove the first and second part of the Main Theorem.

Main Theorem:

(i) For every 2-letter coloured pattern ϕ, the number of ϕ-avoiding coloured permutations in S_{n}^{(r)} is given by the expression: ∑_{j=0}^{n} j!(r − 1)^{j}\binom{n}{j}^{2}. (ii) A double restrictions by 2-letter coloured patterns gives one Wilf class for r = 1, four Wilf classes for r = 2, and six Wilf classes for r ≥ 3.

2. Symmetries on coloured permutations

As on the symmetric group S_{n} there are three natural symmetric operations: the reversal, the complement, and the inversion (see [SS]). On S_{n}^{(r)} we define:

(i) the reversal br : S_{n}^{(r)} → S_{n}^{(r)} by

br : (α_{1}^{(s_{1})}, …, α_{n}^{(s_{n})}) ↦ (α_{n}^{(s_{n})}, …, α_{1}^{(s_{1})});

(ii) the complement bc : S_{n}^{(r)} → S_{n}^{(r)} by

bc : (α_{1}^{(s_{1})}, …, α_{n}^{(s_{n})}) ↦ ((n + 1 − α_{1})^{(s_{1})}, …, (n + 1 − α_{n})^{(s_{n})});

(iii) the colour-complement cc : S_{n}^{(r)} → S_{n}^{(r)} by

cc : (α_{1}^{(s_{1})}, …, α_{n}^{(s_{n})}) ↦ (α_{1}^{(r+1−s_{1})}, …, α_{n}^{(r+1−s_{n})}).

Example 2.1. Let ψ = (1^{(1)}, 3^{(2)}, 2^{(1)}) ∈ S_{3}^{(2)}, then br(ψ) = (2^{(1)}, 3^{(2)}, 1^{(1)}), bc(ψ) = (3^{(1)}, 1^{(2)}, 2^{(1)}), and cc(ψ) = (1^{(2)}, 3^{(1)}, 2^{(2)}). Proposition 2.2. The group < br, bc, cc > is isomorphic to D_{8}. Remark 2.3. More generally, we extend these symmetric operations to T ⊆ S_{n}^{(r)} by g(T) = {g(ψ)|ψ ∈ T }, where g = br, bc, or cc. Therefore for any T ⊆ S_{n}^{(r)}, n ≥ 0

|S_{n}^{(r)}(T)| = |S_{n}^{(r)}(br(T))| = |S_{n}^{(r)}(bc(T))| = |S_{n}^{(r)}(cc(T))|.

Also there are other symmetric operations. The first is the inverse < · >^{−1}: S_{n}^{(r)} → S_{n}^{(r)} defined by

< · >^{−1}: (α_{1}^{(s_{1})}, …, α_{n}^{(s_{n})}) ↦ (β_{1}^{(s_{n})}, …, β_{n}^{(s_{n})});

where β = α^{−1} in S_{n} (see [W]). The second is colour-permutation cp_{δ} : S_{n}^{(r)} → S_{n}^{(r)} where δ ∈ S_{r}, defined by

cp_{δ}(α_{1}^{(s_{1})}, …, α_{n}^{(s_{n})}) = (α_{1}^{(δ_{s_{1}})}, …, α_{n}^{(δ_{sn})}).

More generally, for any T ⊂ S_{n}^{(r)} we define cp_{δ}(T) = {sp_{δ}(ψ)|ψ ∈ T }.

Remark 2.4. Let T ⊂ S_{k}^{(r)}, δ ∈ S_{r}, then |S_{n}^{(r)}(T)| = |S_{n}^{(r)}(cp_{δ}(T))|. An example, for r ≥ 3, |S_{n}^{(r)}((1^{(1)}, 2^{(2)}), (1^{(2)}, 2^{(3)}))| = |S_{n}^{(r)}((1^{(2)}, 2^{(1)}), (1^{(1)}, 2^{(3)}))|, by the symmetric operation cp_{(2,1,3,4,...,r)}.

3. Avoidance patterns and coloured patterns

We say a coloured permutation ϕ ∈ S_{k}^{(r)} is homogeneous if ϕ_{i} = α_{i}^{(u)} for all i = 1, 2, …, k where 1 ≤ u ≤ r; in this case we denote ϕ by [α]_{(u)}. More generally, we write T_{(u)} = {[α]_{(u)}|α ∈ T }, where T ⊂ S_{k}. Theorem 3.1. Let 1 ≤ u ≤ r, T ⊆ S_{k}. For all n ≥ 0

|S_{n}^{(r)}(T_{(u)})| = ∑_{j=0}^{n} j!(r − 1)^{j}|S_{n−j}(T)|\binom{n}{j}^{2}.

Proof. Since all the patterns in T_{(u)} are homogeneous with the same colour, then we can choose a coloured permutation in S_{n}^{(r)}(T_{(u)}) by choosing n − j symbols with colour u, and n − j positions where 0 ≤ j ≤ n, and in the other positions we put any coloured permutation with the other symbols and without colour u. Hence

|S_{n}^{(r)}(T_{(u)})| = ∑_{j=0}^{n} \binom{n}{j}^{2}|S_{\{1,2,...,j\}}^{\{u\}}(T_{(u)})||S_{\{j+1,...,n\}}^{\{1,...,u−1,u+1,...,r\}}|.

□

Example 3.2. (see [S, Eq. 46]) Let a = 1, 2. For r = 2, by Theorem 3.1 we get

|S_{n}^{(2)}((1^{(a)}, 2^{(a)}), (2^{(a)}, 1^{(a)}))| = (n + 1)!,

|S_{n}^{(2)}((1^{(a)}, 2^{(a)}))| = |S_{n}^{(2)}((2^{(a)}, 1^{(a)}))| = ∑_{j=0}^{n} j!\binom{n}{j}^{2}.

Remark 3.3. Let r ≥ 1, τ ∈ S_{k}. For all n ≥ 0, |S_{n}^{(r)}(F_{τ})| = r^{n}|S_{n}(τ)|, where F_{τ} = {(τ_{1}^{(v_{1})}, …, τ_{k}^{(v_{k})})|1 ≤ v_{1}, v_{2}, ⋯, v_{k} ≤ r}. As an example, |S_{n}^{(r)}(T)| = r^{n} for all n ≥ 0, where T = {(1^{(a)}, 2^{(b)})|a, b = 1, 2, …, r}.

4. Restricted sets

In this section, we calculate cardinalities of S_{n}^{(r)}(T) for two special subsets T ⊂ S_{2}^{(r)}. The first special subset is defined by T_{b;a_{1},a_{2},...,a_{l}} = {(1^{(b)}, 2^{(a_{j})})|j = 1, 2, …, l}. Theorem 4.1. Let 1 ≤ l ≤ r, and 1 ≤ b ≤ a_{1} < a_{2} < ⋯ < a_{l} ≤ r. Then

∑_{n≥0} \frac{|S_{n}^{(r)}(T_{b;a_{1},a_{2},...,a_{l}})|}{n!}x^{n} = (\frac{1 − (r − l)x}{(1 − (r − 1)x)^{l}} )^{\frac{1}{l−1}} ;

when l = 1 we take the limit of the right hand side which equals ^{\frac{e^{\frac{x}{1−(r−1)x}}}{1−(r−1)x}}.

Proof. Let ϕ ∈ S_{n}^{(r)}(T_{b;a_{1},...,a_{l}}), p_{r}(n) = |S_{n}^{(r)}(T_{b;a_{1},...,a_{l}})|, and let us consider the possible values of ϕ_{1}:

(1) Let ϕ_{1} = i^{(c)}, c ≠ b, and 1 ≤ i ≤ n; so ϕ ∈ S_{n}^{(r)}(T_{b;a_{1},...,a_{l}}) if and only if (ϕ_{2}, …, ϕ_{n}) is T_{b;a_{1},...,a_{l}} -avoiding, hence in this case there are (r − 1)np_{r}(n − 1) coloured permutations.

(2) Let ϕ_{1} = i^{(b)}; since ϕ is T_{b;a_{1},...,a_{l}}-avoiding, the symbols i + 1, …, n must appear without colours a_{1}, …, a_{l}. Also the symbols 1, …, i − 1 are T_{b;a_{1},...,a_{l}}-avoiding, and can be placed anywhere at positions 2, …, n, hence there are

∑_{i=1}^{n} \binom{n − 1}{i − 1}(n − i)!(r − l)^{n−i}p_{r}(i − 1)

coloured permutations in this case. By the above two cases we obtain a recurrence relation satisfied by p_{r}(n)

p_{r}(n) = (r − 1)np_{r}(n − 1) + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(n − i)!(r − l)^{n−i}p_{r}(i − 1),

for n ≥ 1, and p_{r}(0) = 1. Let q_{n} = p_{r}(n)/n!. By multiplying the recurrence by x^{n−1}/(n − 1)!, and summing up over all n ≥ 1, we obtain

\frac{d}{dx}q(x) = (r − 1)\frac{d}{dx}(xq(x)) + \frac{q(x)}{1 − (r − l)x},

where q(x) = ∑_{n≥0} q_{n}x^{n}. Since q(0) = 1, the theorem holds. □

Corollary 4.2. For all n ≥ 0, |S_{n}^{(r)}(T_{1;1,2,...,r})| = ∏_{j=0}^{n}(j(r − 1) + 1).

Proof. Immediately, Case 1 of the proof of Theorem 4.1 gives (r −1)np_{r}(n−1) coloured permutations, and Case 2 of the proof of Theorem 4.1 (because i = n) gives p_{r}(n − 1) coloured permutations. Then for n ≥ 2,

p_{r}(n) = |S_{n}^{(r)}(T_{1;1,2,...,r})| = ((r − 1)n + 1)p_{r}(n − 1).

Since p_{r}(0) = 1, the corollary holds. □

Example 4.3. (see [S, Eq. 47]) By Corollary 4.2,

|S_{n}^{(2)}(T_{1;1,2})| = |S_{n}^{(2)}((1^{(1)}, 2^{(1)}), (1^{(1)}, 2^{(2)}))| = (n + 1)!.

Now we present the second special subset. Consider a subset T ⊂ S_{k}^{(r)}; we say that T is good if it is the union of disjoint homogeneous subsets; that is, T = ⋃_{j=1}^{p}(T_{j})_{(u_{j})}. As an example, T = {(1^{(1)}, 2^{(1)}, 3^{(1)}), (1^{(1)}, 3^{(1)}, 2^{(1)}), (2^{(2)}, 1^{(2)}, 3^{(2)})} is a good set.

Theorem 4.4. Let T = ⋃_{j=1}^{p}(T_{j})_{(u_{j})} be a good set. Then |S_{n}^{(r)}(T)| for n ≥ 0 is given by

\begin{aligned}∑_{j_{1}=0}^{n} ∑_{j_{2}=0}^{n−j_{1}} ⋯ ∑_{j_{p}=0}^{n−j_{1}···−j_{p−1}}(r − p)^{n−j_{1}···−j_{p}} & \binom{n}{j_{1}, …, j_{p}, n − j_{1} ⋯ − j_{p}}^{2} \\ & ·(n − j_{1} ⋯ − j_{p})! ∏_{i=1}^{p} |S_{j_{i}}(T_{i})|. \end{aligned}

Proof. The theorem holds for p = 1 by Theorem 3.1. Now let p > 1, so by definitions

|S_{n}^{(r)}(T)| = ∑_{j_{1}=0}^{n} |S_{n−j_{1}}^{\{1,...,u_{1}−1,u_{1}+1,...,r\}}(T \(T_{1})_{(u_{1})})||S_{j}(T_{1})|\binom{n}{j_{1}}^{2},

therefore,

|S_{n}^{(r)}(T)| = ∑_{j_{1}=0}^{n} |S_{n−j_{1}}^{(r−1)}(T \(T_{1})_{(u_{1})})||S_{j_{1}}(T_{1})|\binom{n}{j_{1}}^{2}.

Hence, by the inductive assumption, and

|S_{n−j_{1}−···−j_{p}}^{(r−p)}| = (n − j_{1} − ⋯ − j_{p})!(r − p)^{n−j_{1}−···−j_{p}},

the theorem holds. □

Let T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}} be a subset of S_{2}^{(r)} defined by

T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}} = ⋃_{i=1}^{d}{(1^{(a_{i})}, 2^{(a_{i})})} ∪ ⋃_{i=d+1}^{l}{(2^{(a_{i})}, 1^{(a_{i})})},

hence by Theorem 4.4 we obtain the following corollary: Corollary 4.5. Let a_{1}, …, a_{l} be l different numbers integers between 1 and r. Then |S_{n}^{(r)}(T_{l;a_{1},...,a_{d},a_{d+1},...,a_{l}})| for n ≥ 0 is given by

∑_{j_{1}=0}^{n} ∑_{j_{2}=0}^{n−j_{1}} ⋯ ∑_{j_{l}=0}^{n−j_{1}···−j_{l−1}}(r − l)^{n−j_{1}···−j_{l}} \binom{n}{j_{1}, …, j_{l}, n − j_{1} ⋯ − j_{l}}^{2}(n − j_{1} ⋯ − j_{l})!.

Now we build a bijection, which gives for the set S_{n}^{(r)}(T_{l;a_{1},...,a_{d};a_{d+1}...,a_{l}}) a combinatorial geometric explanation. Consider l lines L_{1},…,L_{l} such that L_{i} contains all the points of the form j^{(i)} for all j = 1, 2, …, n. We say L_{i} is good if the points 1^{(i)} to n^{(i)} are decreasing, and the line L_{i} is bad if the points 1^{(i)}, …, n^{(i)} are increasing, otherwise we say the line L_{i} is free.

Now we consider the following collection which represents the set T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}}. Let L_{a_{1}}, …, L_{a_{d}} be good lines, L_{a_{d+1}}, …, L_{a_{l}} be bad lines, and L_{i} be a free line for all 1 ≤ i ≤ r such that i ∉ {a_{1}, …, a_{l}}. For example, the representation of T_{2;3;2} where r = 4, is given by the following diagram.

[figure: n^{(3)}; ...; 3^{(3)}; 2^{(3)}; 1^{(3)}; L_{3}; 1^{(2)}; 2^{(2)}; 3^{(2)}; ...; n^{(2)}; L_{2}; L_{1}; L_{4}]

Figure 1: Representation of T_{2;3;2}

Here the lines L_{1} and L_{4} are free lines.

Now let us define a path between the points on the lines of the representation of T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}}. A path is a collection of steps, starting anywhere, where every step is one of the following steps (such that no two points in the collection have the same symbols):

(i) a decreasing step from a point to another point on a bad, or a good line, (ii) a free step on the free line, or between the lines (from a point to another point).

Proposition 4.6. The set of paths of n steps is exactly the set of T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}}- avoiding coloured permutation in S_{n}^{(r)}.

Proof. By definitions we see that every path of n steps is a T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}}-avoiding coloured permutation in S_{n}^{(r)}. On the other hand, if ϕ is T_{l;a_{1},...,a_{d};a_{d+1},...,a_{l}}-avoiding coloured permutation in S_{n}^{(r)}, then all the symbols in ϕ coloured by a_{i} are decreasing for 1 ≤ i ≤ d and increasing for d + 1 ≤ i ≤ l, and the other symbols appear in any order coloured by any colour u ≠ a_{i} for all 1 ≤ i ≤ l. Therefore, by reading ϕ from the left to the right, we obtain a path of n steps. Hence the proposition holds. □

By using the above proposition we obtain a combinatorial proof of Corollary 4.5. This corollary produces a generalization of certain results in [S], in particular we get the following (because i_{1} + ⋯ + i_{r} = n). Corollary 4.7. Let 0 ≤ d ≤ r; for n ≥ 0,

|S_{n}^{(r)}(T_{r;1,...,d;d+1,...,r})| = ∑_{i_{1}=0}^{n} ∑_{i_{2}=0}^{n−i_{1}} ⋯ ∑_{i_{r−1}=0}^{n−i_{1}−···−i_{r−2}} \binom{n}{i_{1}, …, i_{r−1}, n − i_{1} − ⋯ − i_{r−1}}^{2}.

Example 4.8. (see [S, Eq. 49]) Let r = 2; Corollary 4.7 yields

|S_{n}^{(2)}(T_{2;∅;1,2})| = |S_{n}^{(2)}(T_{2;1;2})| = |S_{n}^{(2)}(T_{2;1,2;})| = ∑_{i=0}^{n} \binom{n}{i}^{2} = \binom{2n}{n}.

5. Single restriction by a 2-letter coloured pattern

The length 2 coloured permutations give rise to some enumeratively interesting classes of coloured permutations, which we examine in this section. In the symmetric group S_{n}, patterns of length 2 are uninterestingly restrictive, and length 3 is the first interesting case. Also in S_{n}^{(r)}, restriction by patterns of length 1 is trivial, and given by the following formula |S_{n}^{(r)}(1^{a})| = n! · (r − 1)^{n}, where 1 ≤ a ≤ r. Let us write

d_{r}(n) = ∑_{j=0}^{n} j!(r − 1)^{j}\binom{n}{j}^{2},

and let d_{r}(x) be the generating function of the sequence d_{r}(n)/n!. From Theorems 4.1

and 4.4 it is easy to see that d_{r}(x) = ^{\frac{e^{\frac{x}{1−(r−1)x}}}{1−(r−1)x}} .

Now we prove the first case of the Main Theorem, that is, that there exists exactly one Wilf class of a single restriction by a 2-letter coloured pattern, for all r ≥ 1. Theorem 5.1. Let r ≥ 1, and 1 ≤ a, b, c, d ≤ r. For n ≥ 0

|S_{n}^{(r)}((1^{(a)}, 2^{(b)}))| = |S_{n}^{(r)}((2^{(c)}, 1^{(d)}))| = d_{r}(n).

Proof. By Section 2 (symmetric operations) we have to verify two cases:

(1) Let 1 ≤ a ≤ r; for n ≥ 0, |S_{n}^{(r)}((1^{(a)}, 2^{(a)}))| = d_{r}(n). But this follows from Theorem 3.1 and because |S_{m}(12)| = 1 for m ≥ 0;

Case  ϕ  ϕ′  |S_{n}^{(5)}(ϕ, ϕ′)| for n = 0, 1, 2, 3, 4, 5 Reference
1 (1^{(1)}, 2^{(1)}) (2^{(1)}, 1^{(1)})  1, 5, 48, 672, 12288, 276480  Theorem 6.1
2 (1^{(1)}, 2^{(1)}) (1^{(1)}, 2^{(2)})  1, 5, 48, 672, 12288, 276480  Theorem 6.1
3 (1^{(1)}, 2^{(2)}) (2^{(1)}, 1^{(2)})  1, 5, 48, 672, 12288, 276480  Theorem 6.1
4 (1^{(1)}, 2^{(2)}) (2^{(2)}, 1^{(1)})  1, 5, 48, 672, 12288, 276480  Theorem 6.1
5 (1^{(1)}, 2^{(2)}) (1^{(1)}, 2^{(3)})  1, 5, 48, 672, 12288, 276480  Theorem 6.1
6 (1^{(1)}, 2^{(1)}) (1^{(2)}, 2^{(2)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
7 (1^{(1)}, 2^{(1)}) (2^{(2)}, 1^{(2)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
8 (1^{(1)}, 2^{(1)}) (1^{(2)}, 2^{(3)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
9 (1^{(1)}, 2^{(1)}) (2^{(2)}, 1^{(3)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
10 (1^{(1)}, 2^{(2)}) (1^{(3)}, 2^{(4)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
11 (1^{(1)}, 2^{(2)}) (2^{(3)}, 1^{(4)})  1, 5, 48, 668, 12046, 265062  Theorem 6.3
12 (1^{(1)}, 2^{(2)}) (2^{(1)}, 1^{(3)})  1, 5, 48, 670, 12168, 270856  Theorem 6.5
13 (1^{(1)}, 2^{(2)}) (2^{(2)}, 1^{(3)})  1, 5, 48, 670, 12168, 270856  Theorem 6.5
14 (1^{(1)}, 2^{(1)}) (2^{(1)}, 1^{(2)})  1, 5, 48, 671, 12288, 273665  Theorem 6.6
15 (1^{(1)}, 2^{(2)}) (1^{(2)}, 2^{(3)})  1, 5, 48, 669, 12106, 267867
16 (1^{(1)}, 2^{(2)}) (1^{(2)}, 2^{(1)})  1, 5, 48, 670, 12166, 270672

Table 1. Pairs of 2-letter coloured patterns

(2) Let b ≤ a; for n ≥ 0, |S_{n}^{(r)}((1^{(a)}, 2^{(b)}))| = |S_{n}^{(r)}((1^{(a)}, 2^{(a)}))|. But this follows from

Theorem 4.1 by |S_{n}^{(r)}(T_{a;b})| = |S_{n}^{(r)}(T_{a;a})|.

□

6. Double restrictions by 2-letter coloured patterns

In this section, we find the number of Wilf classes for r ≥ 1, of double restrictions by 2-letter coloured patterns. In S_{2}^{(r)} there are r^{2}(r^{2}−1) possibilities to choose two elements of the following forms: (1^{(a)}, 2^{(b)}), (1^{(c)}, 2^{(d)}), and there are r^{4} possibilities to choose two elements of the following forms: (1^{(a)}, 2^{(b)}), (2^{(c)}, 1^{(d)}), where 1 ≤ a, b, c, d ≤ r. On the other hand, by symmetric operations (Section 2), the question of determining the S_{n}^{(r)}(ϕ, ϕ′) for r^{2}(2r^{2} − 1) choices for 2-letter coloured patterns ϕ, ϕ′ reduces to the determination of the S_{n}^{(r)}(ϕ, ϕ′) where ϕ, ϕ′ are from Table 1.

Theorem 6.1. For n ≥ 0, |S_{n}^{(r)}(T)| = n!(n + r − 1)(r − 1)^{n−1} where (i) T = {(1^{(1)}, 2^{(1)}), (2^{(1)}, 1^{(1)})} for r ≥ 1; (ii) T = {(1^{(1)}, 2^{(1)}), (1^{(1)}, 2^{(2)})} for r ≥ 2; (iii) T = {(1^{(1)}, 2^{(2)}), (2^{(1)}, 1^{(2)})} for r ≥ 2; (iv) T = {(1^{(1)}, 2^{(2)}), (2^{(2)}, 1^{(1)})} for r ≥ 2;

(v) T = {(1^{(1)}, 2^{(2)}), (1^{(1)}, 2^{(3)})} for r ≥ 3.

Proof. By Theorem 3.1 and because |S_{m}(12, 21)| = 1, 1, 0 where m = 0, m = 1, m ≥ 2 respectively, (i) holds, and Theorem 4.1 immediately yields (ii), and (v) respectively for T_{1;1,2} and T_{1;2,3}. Now let us prove (iii) and (iv).

Case (iii): Let p_{n} = |S_{n}^{(r)}(T)|, ϕ ∈ S_{n}^{(r)}(T), and let us consider the possible values of ϕ_{1}:

(1) Let ϕ_{1} = i^{(c)}, c ≠ 1; ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{2}, …, ϕ_{n}) ∈ S_{{1,...,i−1,i+1,...,n}}^{(r)}(T). Hence in this case there are (r − 1)np_{n−1} coloured permutations.

(2) Let ϕ_{1} = i^{(1)}; since ϕ is T -avoiding, the symbols 1, …, i − 1, i + 1, …, n are not coloured by 2, and can be replaced anywhere at positions 2, …, n for all 1 ≤ i ≤ m. Hence, in this case there are (n−1)!(r−1)^{n−1} coloured permutations.

Therefore by the above two cases p_{n} satisfies the following relation:

p_{n} = n(r − 1)p_{n−1} + n!(r − 1)^{n−1}.

Since p_{0} = 1, (iii) holds.

Case (iv): Let p_{n} = |S_{n}^{(r)}(T)|, ϕ ∈ S_{n}^{(r)}(T) such that ϕ_{j} = n^{(c)}, and let us consider the possible values of j, c:

(1) Let c ≠ 2; ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{1}, …, ϕ_{j−1}, ϕ_{j+1}, …, ϕ_{n}) ∈ S_{n−1}^{(r)}(T). Hence in this case there are (r − 1)np_{n−1} coloured permutations.

(2) Let c = 2; ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{1}, …, ϕ_{j−1}, ϕ_{j+1}, …, ϕ_{n}) is a coloured permutation with symbols 1, 2, …, n − 1 and colours 2, …, r for all 1 ≤ j ≤ n. Hence, in this case there are (n − 1)!(r − 1)^{n−1} coloured permutations.

So we obtain the same relations as for (iii), hence (iv) holds. □

Example 6.2. (see [S, Eq. 46, 47]) As an example we get

\begin{matrix}|S_{n}^{(2)}((1^{(1)}, 2^{(1)}), (2^{(1)}, 1^{(1)}))| = |S_{n}^{(2)}((1^{(1)}, 2^{(1)}), (1^{(1)}, 2^{(2)}))| = \\ |S_{n}^{(2)}((1^{(1)}, 2^{(2)}), (2^{(1)}, 1^{(2)}))| = |S_{n}^{(2)}((1^{(1)}, 2^{(2)}), (2^{(2)}, 1^{(1)}))| = & (n + 1)! \end{matrix}

for n ≥ 0, which was proved in [S]. Theorem 6.3. Let 2 ≤ a ≤ b, and r ≥ b; for all n ≥ 1

|S_{n}^{(r)}(T)| = ∑_{i+j≤n} \binom{n}{i, j, n − i − j}^{2}(n − i − j)!(r − 2)^{n−i−j},

where

\begin{matrix}(i) & T = \{(1^{(1)}, 2^{(1)}), (1^{(a)}, 2^{(b)})\}; & (ii) & T = \{(1^{(1)}, 2^{(1)}), (2^{(a)}, 1^{(b)})\}; \\ (iii) & T = \{(1^{(1)}, 2^{(2)}), (1^{(3)}, 2^{(4)})\}; & (iv) & T = \{(1^{(1)}, 2^{(2)}), (2^{(3)}, 1^{(4)})\}. \end{matrix}

Proof. Cases (i), (ii): Similar to the proof of Theorem 3.1 we find that

|S_{n}^{(r)}(T)| = ∑_{j=0}^{n} \binom{n}{j}^{2}|S_{j}(12)|S_{n−j}^{(r−1)}(ϕ)|,

where either ϕ = (1^{(a)}, 2^{(b)})} or ϕ = (2^{(a)}, 1^{(b)})}. Hence, since S_{j}(12) = 1 for all j ≥ 0, the two claims follow from Theorem 5.1.

Cases (iii), (iv): Let T_{1} = {(1^{(1)}, 2^{(2)}), (1^{(3)}, 2^{(4)})}, T_{2} = {(1^{(1)}, 2^{(2)}), (2^{(3)}, 1^{(4)})}, and let ϕ ∈ S_{n}^{(r)}(T_{1}). Also let us define I_{ϕ} to be the set of all j such that ϕ_{j} is coloured by either 3 or 4. Now we define a function f : S_{n}^{(r)}(T_{1}) → S_{n}^{(r)}(T_{2}) by reversing all the ϕ_{j} where j ∈ I_{ϕ}. Hence by definitions, f is a bijection, which means that |S_{n}^{(r)}((1^{(1)}, 2^{(2)}), (2^{(3)}, 1^{(4)}))| = |S_{n}^{(r)}((1^{(1)}, 2^{(2)}), (1^{(3)}, 2^{(4)}))|.

On the other hand, by Theorem 5.1 there exist bijections, f_{a,b;c} : S_{n}^{(r)}((1^{(a)}, 2^{(b)})) → S_{n}^{(r)}((1^{(c)}, 2^{(c)}), and g_{a,b;c} : S_{n}^{(r)}((2^{(a)}, 1^{(b)})) → S_{n}^{(r)}((2^{(c)}, 1^{(c)}). Now let us define a bijection g : S_{n}^{(r)}((1^{(1)}, 2^{(2)}), (2^{(3)}, 1^{(4)})) → S_{n}^{{1,3,5,6,...,r}}((1^{(1)}, 2^{(1)}), (2^{(3)}, 1^{(3)})), as follows. Let ϕ ∈ S_{n}^{(r)}((1^{(1)}, 2^{(2)}), (2^{(3)}, 1^{(4)})), let I_{ϕ} the set of all j such that ϕ_{j} is coloured by either 1 or 2, and let J_{ϕ} the set of all j such that ϕ_{j} is coloured by either 3 or 4; we define g(ϕ) by operating the bijection f_{1,2;1} on all ϕ_{j} where j ∈ I_{ϕ}, by operating the bijection f_{3,4;3} on all ϕ_{j} where j ∈ J_{ϕ}, and leaving the other ϕ_{j} with j ∉ I_{ϕ} ∪ J_{ϕ} in the same order. Hence, g is a bijection, and by Theorem 4.4 the Cases (iii) and (iv) follow. □

Example 6.4. (see [S, Eq. 47]) As an example, by Theorem 6.3 for n ≥ 0

|S_{n}^{(2)}((1^{(1)}, 2^{(1)}), (2^{(2)}, 1^{(2)}))| = \binom{2n}{n}.

Theorem 6.5. For r ≥ 3,

∑_{n≥0} \frac{S_{n}^{(r)}(T)}{n!}x^{n} = \frac{∫ d_{r−1}^{2}(x)dx}{1 − (r − 1)x},

where

(i) T = {(1^{(1)}, 2^{(2)}), (2^{(1)}, 1^{(3)})}; (ii) T = {(1^{(1)}, 2^{(2)}), (2^{(2)}, 1^{(3)})}.

Proof. Case (i): Let T = {(1^{(1)}, 2^{(2)}), (2^{(1)}, 1^{(3)}))}, p_{n} = S_{n}^{(r)}(T), ϕ ∈ S_{n}^{(r)}(T), and let us consider the possible values of ϕ_{1}:

(1) Let ϕ_{1} = i^{(c)}, c ≠ 1; so ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{2}, …, ϕ_{n}) ∈ S_{{1,...,i−1,i+1,...,n}}^{(r)}(T). Hence in this case there are (r − 1)np_{n−1} coloured permutations.

(2) Let ϕ_{1} = i^{(1)}, 1 ≤ i ≤ n; since ϕ is T -avoiding, the symbols i + 1, …, n are not coloured by 2, and the symbols 1, …, i − 1 are not coloured by 3. Hence there are \binom{n−1}{i−1}|S_{n−i}^{(r−1)}((2^{(1)}, 1^{(3)}))||S_{i−1}^{(r−1)}((1^{(1)}, 2^{(2)}))| coloured permutations, so by Theorem 5.1 there are \binom{n−1}{i−1}d_{r−1}(n − i)d_{r−1}(i − 1) coloured permutations.

Therefore p_{n} satisfies the following relation:

p_{n} = n(r − 1)p_{n−1} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}d_{r−1}(n − i)d_{r−1}(i − 1)

with p_{0} = 1 and p_{1} = r. Let q_{n} = p_{n}/n!, and q(x) = ∑_{n≥0} q_{n}x^{n}; by multiplying the last relation by \frac{x^{n}}{(n−1)!}, and summing over n ≥ 1 we get

∑_{n≥1}(nq_{n} − n(r − 1)q_{n−1})x^{n} = xd_{r−1}^{2}(x),

hence [(1 − (r − 1)x)q(x)]′ = d_{r−1}^{2}(x), which means that Case (i) holds.

Case (ii): Let T = {(1^{(1)}, 2^{(2)}), (2^{(2)}, 1^{(3)}))}, p_{n} = S_{n}^{(r)}(T), and ϕ ∈ S_{n}^{(r)}(T) such that ϕ_{j} = n^{(c)}. Let us consider the possible values of j, c:

(1) Let c ≠ 2; ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{1}, …, ϕ_{j−1}, ϕ_{j+1}, …, ϕ_{n}) ∈ S_{n−1}^{(r)}(T). Hence in this case there are (r − 1)np_{n−1} coloured permutations.

(2) Let c = 2; since ϕ is T -avoiding, all the symbols in (ϕ_{1}, …, ϕ_{j−1}) are not coloured by 1, and the symbols in (ϕ_{j+1}, …, ϕ_{n}) are not coloured by 3. Hence there are \binom{n−1}{j−1}|S_{j−1}^{(r−1)}((2^{(2)}, 1^{(3)}))||S_{n−j}^{(r−1)}((1^{(1)}, 2^{(2)}))| coloured permutations, so by Theorem 5.1 there are \binom{n−1}{j−1}d_{r−1}(j − 1)d_{r−1}(n − j) coloured permutations.

Therefore p_{n} satisfies the following relation:

p_{n} = n(r − 1)p_{n−1} + ∑_{j=1}^{n} \binom{n − 1}{j − 1}d_{r−1}(n − j)d_{r−1}(j − 1)

with p_{0} = 1. Hence, by Case (i) we see that Case (ii) holds. □

Theorem 6.6. For r ≥ 2,

∑_{n≥0} \frac{S_{n}^{(r)}((1^{(1)}, 2^{(1)}), (2^{(1)}, 1^{(2)}))}{n!}x^{n} = \frac{∫ \frac{d_{r−1}(x)}{1−(r−1)x}dx}{1 − (r − 1)x}.

Proof. Let T = {(1^{(1)}, 2^{(1)}), (2^{(1)}, 1^{(2)}))}, p_{n} = S_{n}^{(r)}(T), ϕ ∈ S_{n}^{(r)}(T), and let us consider the possible values of ϕ_{1}:

(1) If ϕ_{1} = i^{(c)} where c ≠ 1, then ϕ ∈ S_{n}^{(r)}(T) if and only if (ϕ_{2}, …, ϕ_{n}) ∈ S_{{1,...,i−1,i+1,...,n}}^{(r)}(T). Hence in this case there are (r − 1)np_{n−1} coloured permutations.

(2) If ϕ_{1} = i^{(1)} then, since ϕ avoids T, the symbols i + 1, …, n are not coloured by 1, and the symbols 1, …, i − 1 are not coloured by 2. Hence there are \binom{n−1}{i−1}|S_{n−i}^{(r−1)}||S_{i−1}^{(r−1)}((1^{(1)}, 2^{(1)}))| coloured permutations, so by Theorem 5.1 there are \binom{n−1}{i−1}(n − i)!(r − 1)^{n−i}d_{r−1}(i − 1) coloured permutations.

Therefore p_{n} satisfies the following relation: p_{0} = 1, and for n ≥ 1

p_{n} = n(r − 1)p_{n−1} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(n − i)!(r − 1)^{n−i}d_{r−1}(i − 1).

Let q_{n} = p_{n}/n!, and q(x) = ∑_{n≥0} q_{n}x^{n}, by multiplying the last relation by \frac{x^{n}}{(n−1)!}, and summing over n ≥ 1 we get

∑_{n≥1}(nq_{n} − n(r − 1)q_{n−1})x^{n} = \frac{xd_{r−1}(x)}{1 − (r − 1)x},

hence [(1 − (r − 1)x)q(x)]′ = \frac{d_{r−1}(x)}{1−(r−1)x}, which proves the theorem. □

Example 6.7. (see [S, Eq. 48]) Let us write a_{n} = |S_{n}^{(2)}((1^{(1)}, 2^{(1)}), (2^{(1)}, 1^{(2)}))|; by sym-

metric operations and by Theorem 6.6, p_{n} = np_{n−1} + (n − 1)! ∑_{j=0}^{n−1} \frac{1}{j!} for n ≥ 1, hence

n! < p_{n} < (n + 1)! for n ≥ 3.

Let wc(r) be the number of Wilf classes of a double restriction by 2-letter coloured patterns with r colours; then by Theorems 6.1–6.6, and by Table 1 we may formulate part (ii) of the Main Theorem as follows.

Corollary 6.8. wc(r) = 1, 4, 6 for r = 1, 2, r ≥ 3 respectively.

Acknowledgements. I am grateful to the anonymous referees for their helpful comments.

References

[Be] D.A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discrete Math. 163 (1997) 13–45.

[Bi] S.C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. in Math. 139 (1998) 141–156.

[BK] S. Billey and T. K. Lam, Vexillary elements in the hyperoctahedral group, J. of Alg. Combin. 8 (1998) 139–152.

[BS] M. Bona and R. Simion, A self-dual poset on objects counted by the Catalan numbers and a Type-B analogue, Discrete Math. 220 (2000) 35–49.

[Br] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math. 126 (1997) 21–51.

[CW] T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999) 119–128.

[FK] S. Fomin and A.N. Kirillov, Combinatorial B_{n}-analogues of Schubert polynomials, Trans. Amer. Math. Soc. 348 no. 9 (1996) 3591–3620.

[K] D.E. Knuth, The Art of Computer Programming, Volume 3, Addison-Wesley, 1973.

[Kr] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. (2001) (to appear), preprint math.CO/0002200.

[LS] V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)/B, Proc. Indian Acad. Sci., 100 (1990) 45–52.

[M] C. Montenegro, The fixed point non-crossing partition lattices, manuscript, (1993).

[MV1] T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (2000) #R17.

[MV2] T. Mansour and A. Vainshtein, Layered restrictions and Chebyshev polynomials, (2000)

    preprint math.CO/0008173.

[MV3] T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. (2001) (to appear), preprint math.CO/0010047.

[MV4] T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of S_{k}, Discrete Math. and Theoretical Computer Science 4:1 (2000) 67–77.

[R] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), no. 1-3, 195–222.

[S] R. Simion, Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations, Electronic Journal of Combinatorics 7 (2000) #R9.

[SS] R. Simion and F. Schmidt, Restricted permutations, Europ. J. Comb. 6 (1985) 383–406.

[W] J. West, Permutations with forbidden subsequences and stacksortable permutations, Ph.Dthesis, Massachusetts Institute of Technology, Cambridge (1990).

[T] R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972) 341–346.