COLOURED PERMUTATIONS CONTAINING AND AVOIDING CERTAIN PATTERNS

Toufik Mansour ^{1}

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

                              toufik@math.chalmers.se

Abstract

Following [M2], let S_{n}^{(r)} be 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. Let I ⊆ {1, 2, …, r} be subset of d colours; we define T_{k,r}^{m}(I) be the set of all coloured

permutations ϕ ∈ S_{k}^{(r)} such that ϕ_{1} = m^{(c)} where c ∈ I. We prove that, the number T_{k,r}^{m}(I)-avoiding

coloured permutations in S_{n}^{(r)} equals (k − 1)!r^{k−1} ∏_{j=k}^{n} h_{j} for n ≥ k where h_{j} = (r − d)j + (k − 1)d. We then prove that for any ϕ ∈ T_{k,r}^{1}(I) (or any ϕ ∈ T_{k,r}^{k}(I)), the number of coloured permutations

in S_{n}^{(r)} which avoid all patterns in T_{k,r}^{1}(I) (or in T_{k,r}^{k}(I)) except for ϕ and contain ϕ exactly once equals ∏_{j=k}^{n} h_{j} · ∑_{j=k}^{n} \frac{1}{h_{j}} for n ≥ k. Finally, for any ϕ ∈ T_{k,r}^{m}(I), 2 ≤ m ≤ k − 1, this number equals ∏_{j=k+1}^{n} h_{j} for n ≥ k + 1. These results generalize recent results due to Mansour [M1], Mansour and West [MW], and due to Simion [S].

2000 Mathematics Subject Classification: 05A05, 05A15.

1. Introduction

The main goal of this note is to give analogies of enumerative results on certain classes of permutations characterized by pattern-avoidance in the symmetric group (see [M1]), and in the hyperoctahedral group (see [S, MW]). In S_{n}^{(r)} (see [M2]), 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, Mo, R].

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

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!. Besides, Simion [S] found the number of all signed permutations in B_{n} avoiding double 2-letter signed patterns in B_{2}. Recently, Mansour and West [MW] studied the number of signed permutations in B_{n} avoiding a set of 2-letter signed patterns in B_{2}. This invites us to define a further generalizations for avoiding a pattern in S_{n} and avoiding a signed pattern in B_{n}.

Following [M2] (see also [St]), 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 |ϕ|, and (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, ψ = (1^{(1)}, 2^{(2)}, 3^{(2)}) ∈ S_{3}^{(2)} avoids (1^{(1)}, 2^{(1)}); that is, ψ ∈ S_{3}^{(2)}((1^{(1)}, 2^{(1)})).

In this note, we extend Mansour’s (see [M1]) results for avoiding and containing certain patterns in S_{n}, and Simion’s (see [S, Section 3]) results for avoiding signed patterns in B_{n} (also, see [MW]).

2. Coloured permutations avoiding T_{k}^{m}(I_{d})

Let I_{d} be any subset of {1, 2, …, r} of d elements, and let us define T_{k,r}^{m}(I_{d}) be the set of all coloured

permutations ϕ ∈ S_{k}^{(r)} such that ϕ_{1} = m^{(c)} where c ∈ I_{d}; that is,

T_{k,r}^{m}(I_{d}) = ⋃_{c∈I_{d}}{ϕ ∈ S_{k}^{(r)}|ϕ_{1} = m^{(c)}}.

Theorem 2.1. Let k, r ≥ 1, n ≥ k, and k ≥ m ≥ 1. Then

|S_{n}^{(r)}(T_{k,r}^{m}(I_{d}))| = (k − 1)!r^{k−1} ∏_{j=k}^{n}((k − 1)d + (r − d)j).

Proof. Let G_{n} = S_{n}^{(r)}(T_{k,r}^{m}(I_{d})), and define the functions f_{h,c} : S_{n}^{(r)} → S_{n+1}^{(r)} by:

[f_{h,c}(ϕ)]_{i} = \{ \begin{matrix}h^{(c)}, & when i = 1 \\ ϕ_{i−1}, & when |ϕ_{i−1}| < h \\ (|ϕ_{i−1}| + 1)^{(a_{i−1})}, & when |ϕ_{i−1}| ≥ h \end{matrix}

for every i = 1, ..., n + 1, ϕ ∈ S_{n}^{(r)}, 1 ≤ c ≤ r and h = 1, ..., n + 1, where a_{i} is the colour of the symbol |ϕ_{i}| in ϕ. From this we see that if ϕ ∈ G_{n} then

f_{n+1,c_{j}}(ϕ), f_{n,c_{j}}(ϕ), ..., f_{n+m−k+2,c_{j}}(ϕ), f_{1,c_{j}}(ϕ), ..., f_{m−1,c_{j}}(ϕ) ∈ G_{n+1}

for all j = 1, 2, …, d, and f_{h,c}(ϕ) ∈ G_{n+1} for all c ∉ I_{d} and h = 1, 2, …, n + 1. So we have that ((k − 1)d + (r − d)(n + 1))|G_{n}| ≤ |G_{n+1}| where n ≥ k.

Assume that ((k − 1)d + (r − d)(n + 1))|G_{n}| < |G_{n+1}|. Then there exists a coloured permutation ψ ∈ G_{n+1} such that m ≤ |ψ_{1}| ≤ n+m−k+1 and the symbol |ψ_{1}| coloured by c ∈ I_{d}, so there exist k−1 positions 1 < i_{1} < ⋯ < i_{k−1} ≤ n+1 such that the subsequence ϕ_{1}, ϕ_{i_{1}}, …, ϕ_{i_{k−1}} contains η ∈ T_{k,r}^{m}(I_{d}), which contradicts the definition of G_{n+1}. So we have that |G_{n+1}| = ((k − 1)d + (r − d)(n + 1))|G_{n}| for all n ≥ k. Besides |G_{k}| = (rk − d)(k − 1)!r^{k−1} (from the definitions), hence the theorem holds. □

Example 2.2. (see [M1, Theorem 1]) Let T_{k}^{m} = T_{k,1}^{m}(1) and k ≥ m ≥ 1. Theorem 2.1 yields for all n ≥ k that |S_{n}(T_{k}^{m})| = (k − 1)!(k − 1)^{n−k+1}.

Example 2.3. Theorem 2.1 yields for all n ≥ k ≥ m ≥ 1 that |S_{n}^{(2)}(T_{k,2}^{m}(1))| = \frac{(n+k−1)!}{∏_{i=1}^{k−1}(2i−1)}. For k = 2 see [S, Equation 47] and [MW, Equation 2.2].

Example 2.4. Theorem 2.1 for k = 2, m = 1, and I_{1} = {1} gives |S_{n}^{(r)}(T_{2,r}^{1}(1))| = ∏_{j=0}^{n}(1+j(r−1)). For r = 2 see [MW, Equation 4.2].

Corollary 2.5. Let k, r ≥ 1, and k ≥ b ≥ a ≥ 1. For all n ≥ k,

|S_{n}^{(r)}(∪_{m=a}^{b}T_{k,r}^{m}(I_{d}))| = (k − 1)!r^{k−1} ∏_{j=k}^{n}(d(k + a − b − 1) + j(r − d)).

Proof. Let G_{n} = S_{n}^{(r)}(T_{k,r}^{m}(I_{d})). From Theorem 2.1 we get that ϕ ∈ G_{n} if and only if either

f_{1,c_{j}}(ϕ), …, f_{a−1,c_{j}}(ϕ), f_{n+b−(k−2),c_{j}}(ϕ), …, f_{n+1,c_{j}}(ϕ) ∈ G_{n+1}

where j = 1, 2, …, d, or f_{h,c}(ϕ) ∈ G_{n+1} where h = 1, 2, …, n + 1 and c ∉ I_{d}. So we have that |G_{n+1}| = (d(k + a − b − 1) + (r − d)(n + 1))|G_{n}|. Besides |G_{k}| = (rk + d(a − b − 1))(k − 1)!r^{k−1}, hence the theorem holds. □

Example 2.6. Corollary 2.5 gives |S_{n}^{(2)}(T_{k,2}^{1}(1) ∪ T_{k,2}^{2}(1))| = \frac{2^{k−1}(k−1)!}{(2k−3)!}(n + k − 2)! where n ≥ k. For k = 2 see [MW, Equation 4.5].

This example invite us to generalize. By using Corollary 2.5 we get the following result.

Corollary 2.7. Let k, r ≥ 1 and n ≥ k. Then |S_{n}^{(r)}(∪_{m=1}^{k}T_{k,r}^{m}(I_{d}))| = r^{k−1}(r − d)^{n+1−k}n!.

3. Avoiding T_{k,r}^{1}(I_{d})\{ϕ} and containing ϕ exactly once

Let M_{k,r}^{m}(ϕ, I_{d}) = T_{k,r}^{m}(I_{d})\{ϕ}, for ϕ ∈ T_{k,r}^{m}(I_{d}). We denote by S_{n}^{(r)}(T_{k,r}^{m}(I_{d}); τ) the set of all permu-

tations in S_{n}^{(r)} that avoid M_{k,r}^{m}(ϕ, I_{d}) and contain ϕ exactly once.

Theorem 3.1. Let k, r ≥ 1, and n ≥ k. Then

|S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ)| = ∏_{j=k}^{n}((k − 1)d + (r − d)j) ∑_{j=k}^{n} \frac{1}{(k − 1)d + (r − d)j} ,

for all ϕ ∈ T_{k,r}^{1}(I_{d}).

Proof. Let ψ ∈ S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ), and let us consider the possible values of ψ_{1}:

(1) |ψ_{1}| is coloured by colour c ∉ I_{d}. Evidently ψ ∈ S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ) if and only if (ψ_{2}, …, ψ_{n}) avoids M_{k,r}^{m}(ϕ, I_{d}) and contains ϕ exactly once.

(2) |ψ_{1}| ≥ n−k+2 is coloured by c ∈ I_{d}. Evidently ψ ∈ S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ) if and only if (ψ_{2}, …, ψ_{n}) avoids M_{k,r}^{m}(ϕ, I_{d}) and contains ϕ exactly once.

(3) |ψ_{1}| ≤ n − k is coloured by c ∈ I_{d}. Then there exist 1 < i_{1} < ⋯ < i_{k} ≤ n such that (ψ_{1}, ψ_{i_{1}}, …, ψ_{i_{k}}) is a coloured permutation of the symbols n, …, n−k +1, ψ_{1} coloured by any colours such that ψ_{1} coloured by c ∈ I_{d}. For any choice of k − 1 positions out of i_{1}, …, i_{k}, the corresponding coloured permutations proceeded by |ψ_{1}|, is containing some coloured pattern in T_{k,r}^{1}(I_{d}). Since ψ avoids M_{k,r}^{m}(ϕ, I_{d}), it is, in fact, order-isomorphic to ϕ. We thus get at least k occurrences of ϕ in ψ, a contradiction.

(4) |ψ_{1}| = n − k + 1. Then there exist 1 < i_{1} < ⋯ < i_{k−1} ≤ n such that η = (ψ_{1}, ψ_{i_{1}}, …, ψ_{i_{k−1}}) is a coloured permutation of the symbols n, …, n − k + 1. As above, we get that η is orderisomorphic to ϕ. Let A_{n} be the set of all coloured permutations β ∈ S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ) such

that the symbol |β_{1}| is n−k +1 and coloured by c ∈ I_{d}. Define the functions f_{h,c} : A_{n} → S_{n+1}^{(r)} by:

[f_{h,c}(β)]_{i} = \{ \begin{matrix}1^{(c)}, & when i = h \\ (|β_{i}| + 1)^{(a_{i})}, & when i < h \\ (|β_{i−1}| + 1)^{(a_{i})}, & when i > h, \end{matrix}

for every i = 1, ..., n + 1, β ∈ A_{n}, h = 1, ..., n + 1 and c = 1, …, r, where the symbol |β_{i}| coloured by the colour a_{i}. It is easy to see that for all β ∈ A_{n},

f_{n+1,c_{j}}(β), …, f_{n−k+3,c_{j}}(β) ∈ A_{n+1},

and f_{h,c}(β) ∈ A_{n+1} for c ∉ I_{d} and h = 2, …, n (for h = 1 we added in the first case), hence ((k − 1)d + (r − d)n)|A_{n}| ≤ |A_{n+1}|. Now we define another function g : A_{n+1} → S_{n}^{(r)} by:

[g(β)]_{i} = \{ \begin{matrix}(|β_{i}| − 1)^{(a_{i})}, & when i < h \\ (|β_{i+1}| − 1)^{(a_{i})}, & when i + 1 > h, \end{matrix}

where |β_{h}| = 1, i = 1, ..., n, β ∈ A_{n+1}.

Observe that h ≥ n − k + 3 such that |β_{h}| coloured by c ∈ I_{d}, since otherwise already (β_{h}, β_{h+1}, …, β_{n+1}) contains a pattern from T_{k}^{1}(I_{d}), a contradiction. Therefore g(β) ∈ A_{n} for all β ∈ A_{n+1}, so |A_{n+1}| ≤ ((k − 1)d + (r − d)n)|A_{n}|. Hence, using the fact that |A_{k}| = 1 we get that |A_{n+1}| = (d(k − 1) + n(r − d))|A_{n}| = ∏_{j=k}^{n}((k − 1)d + (r − d)j).

COLOURED PERMUTATIONS CONTAINING AND AVOIDING CERTAIN PATTERNS 5

Since the above cases 1-4 are disjoint we obtain

|S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ)| = ((k − 1)d + (r − d)n)|S_{n−1}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ)| + ∏_{j=k}^{n−1}((k − 1)d + (r − d)j).

Besides |S_{k}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ)| = 1, hence the theorem holds. □ Example 3.2. If ϕ ∈ T_{k,2}^{1}(1) then Theorem 3.1 for n ≥ k gives

|S_{n}^{(2)}(T_{k,2}^{1}(1); ϕ)| = \frac{(n + k − 1)!}{(2k − 2)!} ∑_{j=k}^{n} \frac{1}{k − 1 + j} .

Using the natural bijection between the set S_{n}^{(r)}(T_{k,r}^{1}(I_{d}); ϕ) and the set S_{n}^{(r)}(T_{k,r}^{k}(I_{d}); ϕ′) for all ϕ ∈ T_{k,r}^{1}(I_{d}), where ϕ′_{i} = (k +1−|ϕ_{i}|)^{(a_{i})} and a_{i} is a colour of the symbol |ϕ_{i}| in ϕ, together with Theorem 3.1 we get as follows. Corollary 3.3. Let k, r ≥ 1 and n ≥ k. Then

|S_{n}^{(r)}(T_{k,r}^{k}(I_{d}); ϕ)| = ∏_{j=k}^{n}((k − 1)d + (r − d)j) ∑_{j=k}^{n} \frac{1}{(k − 1)d + (r − d)j} ,

for all ϕ ∈ T_{k,r}^{k}(I_{d}).

4. Avoiding T_{k,r}^{m}(I_{d})\{ϕ} and containing ϕ exactly once, 2 ≤ m ≤ k − 1

Now we find the cardinalities of the sets S_{n}^{(r)}(T_{k,r}^{m}(I_{d}); ϕ) where 2 ≤ m ≤ k − 1, ϕ ∈ T_{k,r}^{m}(I_{d}). Theorem 4.1. Let r ≥ 1, k ≥ 3, and n ≥ k + 1. Then

|S_{n}^{(r)}(T_{k,r}^{m}(I_{d}); ϕ)| = ∏_{j=k+1}^{n}((k − 1)d + (r − d)j),

for all 2 ≤ m ≤ k − 1 and ϕ ∈ T_{k,r}^{m}(I_{d}).

Proof. Let G_{n} = S_{n}^{(r)}(T_{k,r}^{m}(I_{d}); ϕ), ψ ∈ G_{n}, and let us consider the possible values of ψ_{1}:

(1) |ψ_{1}| ≤ m − 1 and coloured by c ∈ I_{d}. Evidently ψ ∈ G_{n} if and only if (ψ_{2}, …, ψ_{n}) avoids M_{k,r}^{m}(ϕ, I_{d}) and contains ϕ exactly once.

(2) |ψ_{1}| ≥ n − k + m + 1 and coloured by c ∈ I_{d}. Evidently ψ ∈ G_{n} if and only if (ψ_{2}, …, ψ_{n}) avoids M_{k,r}^{m}(ϕ, I_{d}) and contains ϕ exactly once.

(3) m ≤ |ψ_{1}| ≤ n − k + m and coloured by one of the colours c_{1}, …, c_{d}. By definition we have that |G_{k}| = 1, so let n ≥ k + 1. If m + 1 ≤ |ψ_{1}| then ψ contains at least m ≥ 2 occurrences of a pattern from T_{k,r}^{m}(I_{d}), and If |ψ_{1}| ≤ n − k + m − 1 then ψ contains at least k − m + 1 ≥ 2 occurrences of a pattern from T_{k,r}^{m}(I_{d}), a contradiction.

(4) |ψ_{1}| coloured by a colour c ∉ I_{d}. Evidently ψ ∈ G_{n} if and only if (ψ_{2}, …, ψ_{n}) avoids M_{k,r}^{m}(ϕ, I_{d})

and contains ϕ exactly once. Since the above cases 1-4 are disjoint we obtain |G_{n}| = ((k − 1)d + (r − d)n)|G_{n−1}| for all n ≥ k + 1. Besides |G_{k}| = 1, hence the theorem holds. □

Example 4.2. Let ϕ ∈ T_{k,2}^{m}(1) where 2 ≤ m ≤ k − 1 and k ≥ 3. Then Theorem 4.1 gives

|S_{n}^{(2)}(T_{k,2}^{m}(1); ϕ)| = \frac{(n+k−1)!}{(2k−1)!} for n ≥ k.

Acknowledgments. The author is grateful to the anonymous referee for his helpful comments.

References

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

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

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

[BS] M. Bona and R. Simion, A self-dual poset on objects counted by the Catalan numbers and a Type-B analogue, Discr. 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, Discr. Math. 204 (1999) 119–128.

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

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

[Kr] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001) 510–530.

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

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

[M1] T. Mansour, Permutations containing and avoiding certain patterns, Proc. 12th Conference on Formal Power Series and Algebraic Combinatorics (Moscow, 2000), 2000.

[M2] T. Mansour, Pattern avoidance in coloured permutations, Séminaire Loth. Combin. 46 (2001) Article B46g.

[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, Ann. Combin. 5 (2001) 451–458.

[MV3] T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 26 (2001) 258–269.

[MV4] T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of S_{k}, Discr. Math. and Theor. Comp. Sci. 4 (2000) 67–77.

[MW] T. Mansour and J. West, Avoiding 2-letter signed patterns, Séminaire Loth. Combin. 49 (2002) Article B49a.

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

[S] R. Simion, Combinatorial statistics on type-B analogies of noncrossing partitions and restricted permutations, Elect. J. Combin. 7 (2000) #R9.

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

[St] E. Steingrimsson, Permutation statistics of indexed permutations, Europ. J. of Combin. 15 (1994) 187–205.

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

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