Séminaire Lotharingien de Combinatoire 49 (2002), Article B49a

AVOIDING 2-LETTER SIGNED PATTERNS

T. MANSOUR^{A} AND J. WEST^{B}

A LaBRI (UMR 5800), Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France

                            toufik@labri.fr

B University of Victoria, PO Box 1700 STN CSC, Victoria, BC V8W 2Y2 Canada

                           westj@mala.bc.ca

Abstract. Let B_{n} be the hyperoctahedral group, the set of all signed permutations on n letters, and let B_{n}(T) be the set of all signed permutations in B_{n} which avoid a set T of signed patterns. In this paper, we find all the cardinalities of the sets B_{n}(T) where T ⊆ B_{2}. Some of the cardinalities encountered involve inverse binomial coefficients, binomial coefficients, Catalan numbers, and Fibonacci numbers.

1. Introduction

Pattern avoidance has proven 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 [MV1, and references therein], and rook polynomials [MV2]. On the other hand, signed pattern avoidance has proven to be a useful language in combinatorial statistics defined in type-B noncrossing partitions, enumerative combinatorics, algebraic combinatorics, geometric combinatorics and singularities of Schubert varieties; see [Be, BK, Mo, FK, BS, S, R].

Restricted permutations. Let S_{{a_{1},...,a_{n}}} be the set of all permutations of the numbers a_{1}, …, a_{n}. For simplicity, let us denote by S_{n} the set S_{{1,2,...,n}}. 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 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 S_{n}(T).

Restricted signed permutations. We will regard the elements of the hyperoctahedral group B_{n} as signed permutations written as α = α_{1}α_{2} … α_{n} in which each of the symbols 1, 2, …, n appears, possibly barred. Clearly, the cardinality of B_{n} is 2^{n}n!. We define the barring operation as the one which changes the symbol α_{i} to \overline{α_{i}} and \overline{α_{i}} to α_{i}. It is thus an involution, i.e., \overline{\overline{α_{i}}} = α_{i}. Furthermore, we define the absolute value |α_{i}| of α_{i} to be α_{i} if the symbol α_{i} is not barred, and \overline{α_{i}} otherwise.

Now let τ ∈ B_{k} and α ∈ B_{n}; we say α contains the signed pattern τ, if there is a sequence of k indices, 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that two conditions hold: (1) α with all bars removed has an occurrence of the pattern τ with all bars removed, i.e., |α_{i_{p}}| > |α_{i_{q}}| if and only if |τ_{p}| > |τ_{q}|, for all k ≥ p > q ≥ 1; and (2) in this occurrence, α_{i_{j}} is barred if and only if τ_{j} is barred, for all 1 ≤ j ≤ k. For example, α = 21\overline{3}\overline{4} ∈ B_{4} contains the signed patterns \overline{1}\overline{2} and 21. If α does not contain the signed pattern τ, then we say that α avoids the signed pattern τ or, alternatively, that α is a τ-avoiding signed permutation. The set of τ-avoiding signed permutations in B_{n} will be denoted by B_{n}(τ). More generally we define B_{n}(T) = ⋂_{τ∈T} B_{n}(τ). We denote the cardinality of B_{n}(T) by b_{n}(T).

Proposition 1.1. (see [S, Section 3]) We define three simple operations on signed permutations: the reversal (i.e., reading the permutation right-to-left: α_{1}α_{2} ⋯ α_{n} ↦ α_{n}α_{n−1} ⋯ α_{1}), the barring (i.e., α_{1}α_{2} ⋯ α_{n} ↦ \overline{α_{1}}\overline{α_{2}} ⋯ \overline{α_{n}}) and the complement (i.e., α_{1}α_{2} ⋯ α_{n} ↦ β_{1}β_{2} ⋯ β_{n} where β_{i} = n + 1 − α_{i} if α_{i} not barred, otherwise β_{i} = \overline{n + 1 − |α_{i}|}). Let us denote by G_{b} the group which is generated by these three operations. Then every element g ∈ G_{b} is a bijection, which shows that if T and T′ are both sets of signed patterns in B_{n} such that T′ = g(T) = {g(α) | α ∈ T }, then b_{n}(T) = b_{n}(T′).

In the symmetric group S_{n}, for every 2-letter pattern τ the number of τ-avoiding permutations is 1, and for every pattern τ ∈ S_{3} the number of τ-avoiding permutations is given by the Catalan numbers [K]. Simion [S, Section 3] proved that there are similar results for the hyperoctahedral group B_{n} (generalized by Mansour [M]): for every 2-letter signed pattern τ the number of τ-avoiding signed permutations is given by ∑_{j=0}^{n} \binom{n}{j}^{2}j!. In the present note, we find all the cardinalities b_{n}(T) where T ⊆ B_{2}. (This exhaustive treatment of cases was suggested by the influential paper of Simion and Schmidt [SS], which followed a similar program for the cardinalities s_{n}(T) where T ⊆ S_{3}).

The paper is organized as follows. In Section 2 we find the cardinalities b_{n}(T) where T ⊆ B_{2} and |T | ≤ 2. In Section 3 we deal with the case that |T | = 3; in Section 4 we deal with the case that |T | = 4; and, finally, in Section 5 we deal with the case that 5 ≤ |T | ≤ 8.

2. Two signed patterns

By taking advantage of Proposition 1.1, the question of determining the values b_{n}(τ) for the 8 choices of one 2-letter signed pattern, can be reduced to 2 cases, which are τ = 12 and τ = 1\overline{2}. Simion [S, Proposition 3.2] proved for any n ≥ 0 that

(2.1)  b_{n}(12) = b_{n}(1\overline{2}) = ∑_{k=0}^{n} \binom{n}{k}^{2}k!.

Similary, the second question of determining the values b_{n}(τ, τ′) for the 28 choices of two 2-letter signed patterns reduces to 8 cases.

Remark 2.1. [S, Proposition 3.4] asserted that b_{n}(\{12, 21\}) = 2n! and b_{n}(\{1\overline{2}, \overline{1}2\}) = (n + 1)!. However, in fact, b_{2}(\{12, 21\}) = 6 and b_{3}(\{1\overline{2}, \overline{1}2\}) = 22. Below we present the correction of Simion’s assertions.

Theorem 2.2. Given two 2-letter signed patterns τ, τ′, the value b_{n}(τ, τ′) for n ≥ 1 can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which the pair τ, τ′ belongs:

(2.2)  b_{n}(\{12, 21\}) = b_{n}(\{12, 1\overline{2}\}) = b_{n}(\{2\overline{1}, 1\overline{2}\}) = b_{n}(\{2\overline{1}, \overline{1}2\}) = (n + 1)!;
(2.3)  b_{n}(\{12, \overline{1}\overline{2}\}) = b_{n}(\{12, \overline{2}\overline{1}\}) = \binom{2n}{n};

(2.4)  b_{n}(\{12, \overline{2}1\}) = n! + n! ∑_{i=1}^{n} (\frac{1}{i} ∑_{j=0}^{i−1} \frac{1}{j!});

(2.5)  b_{n}(\{1\overline{2}, \overline{1}2\}) = 2 ∑_{l=1}^{n} ∑_{i_{1}+i_{2}+···+i_{l}=n, i_{j}≥1} ∏_{j=1}^{l} i_{j}!.

Proof. The assertion that b_{n}({12, 21}) = (n + 1)! follows immediately from [M, Theorem 1]. The other results in (2.2) follow from [S, Proposition 3.4]. By [M, Example 4.8] we get (2.3).

To verify (2.4), let us consider the number of signed permutations α ∈ B_{n}(\{12, \overline{2}1\}). If α_{n} is barred then α avoids \{12, \overline{2}1\} if and only if (α_{1}, …, α_{n−1}) avoids \{12, \overline{2}1\}. Hence, there are nb_{n−1}(\{12, \overline{2}1\}) such signed permutations. If α_{n} = i is unbarred then the smaller symbols 1, …, i − 1 must be barred in α and the larger symbols i + 1, …, n must be unbarred, hence the smaller symbols can be permuted and placed in any of the positions 1, 2, …, n − 1. This gives b_{n}(\{12, \overline{2}1\}) = nb_{n−1}(\{12, \overline{2}1\}) + ∑_{i=0}^{n−1} \binom{n−1}{i}i! for n ≥ 1. With the base case b_{0}(T) = 1, Equation (2.4) follows by induction on n.

To verify (2.5), let us consider α ∈ B_{n}(1\overline{2}, \overline{1}2). By induction on n, it is easy to prove there exists a partition α = (α^{1}, …, α^{l}) such that the following conditions hold:

(1) Every absolute symbol in α^{j} is greater than every absolute symbol in α^{j+1} for all j = 1, …, l − 1;

(2) Either all the symbols of α^{j} are barred, or else all are unbarred;

(3) The symbols in α^{j} are barred if and only if the symbols in α^{j+1} are unbarred.

Equation (2.5) follows now immediately. □

3. Three signed patterns

By taking advantage of Proposition 1.1, the question of determining the values b_{n}(T) where T ⊂ B_{2} and |T | = 3, for the 56 choices of three 2-letter signed patterns, can be reduced to the following 10 cases:

T_{1} = \{12, 1\overline{2}, \overline{1}2\}; T_{2} = \{12, 1\overline{2}, \overline{1}\overline{2}\}; T_{3} = \{12, 1\overline{2}, 21\}; T_{4} = \{12, 1\overline{2}, 2\overline{1}\};
T_{5} = \{12, 1\overline{2}, \overline{2}1\}; T_{6} = \{12, 1\overline{2}, \overline{2}\overline{1}\}; T_{7} = \{12, \overline{1}\overline{2}, 21\}; T_{8} = \{12, \overline{1}\overline{2}, 2\overline{1}\};
T_{9} = \{12, 2\overline{1}, \overline{2}1\}; T_{10} = \{1\overline{2}, \overline{1}2, 2\overline{1}\}.

Theorem 3.1. Given a set T of three 2-letter signed patterns, the value b_{n}(T) for n ≥ 1 can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which T belongs:

(3.1)  b_{n}(T_{1}) = ∑_{d=0}^{n} ∑_{i_{0}+i_{1}+···+i_{d}=n−d} ∏_{j=0}^{d} i_{d}!;

(3.2)  b_{n}(T_{2}) = C_{n+1};
(3.3)  b_{n}(T_{3}) = n! + n! ∑_{j=1}^{n} \frac{1}{j};

(3.4)  b_{n}(T_{4}) = b_{n}(T_{5}) = n! ∑_{j=0}^{n} \frac{1}{j!};

(3.5)  b_{n}(T_{6}) = F_{2n+1};
(3.6)  b_{n}(T_{7}) = n^{2} + 1;
(3.7)  b_{n}(T_{8}) = 2^{n+1} − (n + 1);
(3.8)  b_{n}(T_{9}) = b_{n}(T_{10}) = n! ∑_{j=0}^{n} \binom{n}{j}^{−1},

where C_{m} and F_{m} are the mth Catalan and Fibonacci numbers, respectively.

Proof of Equation (3.1). Let α ∈ B_{n}(T_{1}), and let m_{0} be the first unbarred symbol, reading α from left-to-right. Since α ∈ B_{n}(T_{1}) we see that α = (α^{0}, m_{0}, β), where β ∈ B_{m_{0}−1}(T_{1}) and α^{0} is a permutation of the symbols \overline{m_{0} + 1}, …, \overline{n}. By induction it follows that for any α ∈ B_{n}(T_{1}) there exist 0 ≤ d ≤ n and permutations α^{j} of the symbols \overline{m_{j} + 1}, \overline{m_{j} + 2}, …, \overline{m_{j−1} − 1} for all 0 ≤ j ≤ d+1, where m_{−1} = n+1, m_{d+1} = 0, 0 ≤ m_{d} < m_{d−1} < ⋯ < m_{0} ≤ n such that α = (α^{0}, m_{0}, α^{1}, m_{1}, …, α^{d}, m_{d}, α^{d+1}). Equation (3.1) follows now immediately. □

Corollary 3.2. We have that b_{n}(T_{1} ∪ \{\overline{1}\overline{2}\}) = 2^{n} for all n ≥ 0, and b_{n}(T_{1} ∪ \{\overline{2}\overline{1}\}) = 1 + \binom{n+1}{2} for all n ≥ 2.

Proof. This follows immediately, following the argument of the proof of (3.1). □

Proof of Equation (3.2). A split permutation is a permutation π = (π′, π′′) ∈ S_{n}, where π′ and π′′ are nonempty such that every entry of π′ is greater than every entry of π′′. For example, 231, 312, and 321 are the split permutations in S_{3}.

We first check that the number of non-split 123-avoiding permutations in S_{n} (which we denote by N_{n}) is the (n − 1)th Catalan number, C_{n−1}. We do this by using induction on n.

It is easy to check the base case. Now, suppose that N_{j} = C_{j−1} for j < n. Take the C_{n} 123-avoiding permutation (see [K]) and classify them according to the first place where they split. Since each permutation in S_{n} thus decomposes into a direct sum of a non-split 123-avoiding permutation and an arbitrary 123-avoiding permutation, we have that

C_{n} = ∑_{j=1}^{n} N_{j}C_{n−j} = N_{n} + ∑_{j=0}^{n−2} C_{j}C_{n−1−j}.

By the well-known standard Catalan recurrence C_{n} = ∑_{j=0}^{n−1} C_{j}C_{n−1−j}, it follows that N_{n} = C_{n−1}, which completes the induction step.

Now, suppose we have a signed permutation π which avoids T_{2}. Then the permutation |π| must avoid 123.

Thus it remains to consider all 123-avoiding permutations and assign signs to their elements, respecting the condition that if one element precedes and is smaller than a second element, then the first one must be barred while the second one is unbarred.

Take a 123-avoiding permutation π, and suppose that one of its elements can be coloured freely, either barred or not. Then this element cannot be both to the left of and smaller than any other element; neither can it be both to the right of and larger than any other element. That is, if our freely-colourable element is denoted by s, we have π = (π′, s, π′′) where each element of π′ is greater than s, and each element of π′′ is less than s. But this means that each element of the block π′ is greater than each element of the block s, π′′, which means that the permutation splits at s.

Since the existence of a freely-colourable element leads to a split of the permutation, it follows that any permutation which is non-split is also uniquely colourable. There is one exception, which is that the single 1-permutation can be coloured in two ways, i.e., either barred or unbarred.

Now we are ready to find b_{n}(T_{2}) by induction on n. For the induction step we assume that b_{j}(T_{2}) = C_{j+1} for j < n.

We count b_{n}(T_{2}) according to the position of the first split. Let a_{n} be the number of non-split signed permutations which avoid T_{2}; so, a_{1} = 2, while a_{j} = N_{j} = C_{j−1} for j > 1.

Note that if such a signed permutation splits, then each “half” can be assigned signs independently according to the pattern-avoidance conditions. This implies that

b_{n}(T_{2}) = ∑_{j=1}^{n−1} a_{j}b_{n−j} + a_{n} = 2C_{n} + ∑_{j=1}^{n−2} C_{j}C_{n−j} + C_{n−1} = ∑_{j=0}^{n} C_{j}C_{n−j} = C_{n+1}.

□

Proof of Equation (3.3). Let α ∈ B_{n}(T_{3}); if the symbol n is unbarred in α, then since α avoids 12 and 21 we get that all other symbols of α are barred. Thus there are n! such signed permutations. Now let α_{j} = \overline{n}. Since α avoids 1\overline{2}, the symbol α_{i} is barred for i ≤ j. Thus, in this case there are ∑_{j=1}^{n} \binom{n−1}{j−1}(j − 1)! b_{n−j}(T_{3}) such signed permutations. Hence, we have

b_{n}(T_{3}) = n! + (n − 1)! ∑_{j=1}^{n} \frac{b_{n−j}(T_{3})}{(n − j)!}.

Now let b′_{n} = b_{n}(T_{3})/n!. Thus we have b′_{n} = 1+\frac{1}{n} ∑_{j=0}^{n−1} b′_{j}, which implies that b′_{n}−b′_{n−1} = \frac{1}{n}. Because of b′_{1} = 2, we infer b′_{n} = 1 + ∑_{j=1}^{n} \frac{1}{j}, hence (3.3) follows. □

Corollary 3.3. We have that b_{n}(T_{3} ∪ \{\overline{1}\overline{2}\}) = 1 + \binom{n+1}{2} for all n ≥ 0.

Proof. This is immediate if one uses the argument of the proof of (3.3). □

Proof of Equation (3.4), first case. Let α ∈ B_{n}(T_{4}). Since α avoids 12 and 1\overline{2} we have α_{1} = n or α_{1} = \overline{i} for some i. In the first case, since α also avoids 2\overline{1}, we must have α = (n, n − 1, …, 1). In the second case there are b_{n−1}(T_{4}) such signed permutations. Therefore, b_{n}(T_{4}) = 1 + nb_{n−1}(T_{4}) for all n ≥ 3, with b_{2}(T_{4}) = 5. Hence, by induction on n, we obtain the formula for b_{n}(T_{4}). □

Corollary 3.4. We have that b_{n}(T_{4} ∪ \{\overline{1}\overline{2}\}) = b_{n}(T_{4} ∪ \{\overline{2}\overline{1}\}) = 2^{n} and b_{n}(T_{4} ∪ \{21\}) = 2 · n! for all n ≥ 1.

Proof. By the above argument (proof of the formula for b_{n}(T_{4})) we obtain the following:

(1) b_{n}(T_{4} ∪ {21}) = nb_{n−1}(T_{4} ∪ {21}) for all n ≥ 2, with b_{1}(T_{4} ∪ {21}) = 2. Hence, b_{n}(T_{4} ∪ {21}) = 2 · n! for n ≥ 1.

(2) Suppose α avoids T_{4} and \{\overline{1}\overline{2}\}. Again there are two cases. In the first case α = (n, …, 2, 1). In the second case, we have that α = (\overline{i}, β, n, …, i + 1, γ), where all symbols of β are barred and decreasing, and all symbols of γ are unbarred and decreasing. So b_{n}(T_{4} ∪ \{\overline{1}\overline{2}\}) = 1 + ∑_{i=1}^{n} 2^{i−1}, which implies that b_{n}(T_{4} ∪ \{\overline{1}\overline{2}\}) = 2^{n}.

(3) In a manner similar to the second case, we get that b_{n}(T_{4} ∪ \{\overline{2}\overline{1}\}) = 2^{n}.

□

Proof of Equation (3.4), second case. Let α ∈ B_{n}(T_{5}). As in the proof of the first case of (3.4), we obtain that either α_{1} = n or α_{1} = \overline{i} for some i. In the first case there are b_{n−1}(T_{5}) such signed permutations. In the second case, since α avoids \overline{2}1, all the symbols 1, 2, …, i − 1 are barred, so that there are ∑_{i=1}^{n} \binom{n−1}{i−1}(i − 1)!b_{n−i}(T_{5}) such signed permutations. Hence

b_{n}(T_{5}) = b_{n−1}(T_{5}) + (n − 1)! ∑_{i=0}^{n−1} \frac{b_{i}(T_{5})}{i!}

for n ≥ 1. Let b′_{n} = b_{n}(T_{5})/n!, so that n(b′_{n} −b′_{n−1}) = b′_{n−1} −b′_{n−2} for all n ≥ 2. Because of b′_{1} = 2 and b′_{0} = 1, we obtain that b′_{n} = ∑_{j=0}^{n} \frac{1}{j!}, as claimed in the second part of (3.4). □

Corollary 3.5. We have that b_{n}(T_{5} ∪ \{\overline{2}\overline{1}\}) = 2^{n} for all n ≥ 0.

Proof. By using the argument in the proof of the formula for b_{n}(T_{5}), we get that

b_{n}(T_{5} ∪ \{\overline{2}\overline{1}\}) = b_{n−1}(T_{5} ∪ \{\overline{2}\overline{1}\}) + b_{n−1}(T_{5} ∪ \{\overline{2}\overline{1}\}).

If this is combined with the initial condition b_{1}(T_{5} ∪ \{\overline{2}\overline{1}\}) = 2, the corollary follows immediately. □

Proof of Equation (3.5). Let α ∈ B_{n}(T_{6}). It is easy to see that α_{1} = n or α_{1} = \overline{i} for some i. In the first case there are b_{n−1}(T_{6}) such signed permutations. In the second case, since α avoids \overline{2}\overline{1}, all the symbols 1, …, i − 1 must be unbarred, and since α avoids 12, α contains (i − 1, i − 2, …, 1). Furthermore, since α avoids 12 and 1\overline{2}, we get that α = (\overline{i}, β, i − 1, …, 1). Hence there are b_{n−i}(T_{6}) such signed permutations for 1 ≤ i ≤ n. Therefore, for all n ≥ 3, we have

b_{n}(T_{6}) = b_{n−1}(T_{6}) + b_{n−1}(T_{6}) + b_{n−2}(T_{6}) + ⋯ + b_{0}(T_{6}).

This implies that b_{n}(T_{6}) = 3b_{n−1}(T_{6}) − b_{n−2}(T_{6}). If this is combined with the initial condition b_{2}(T_{6}) = 5, Equation (3.5) follows immediately. □

Proof of Equation (3.6). This follows from [M, Theorem 4.4]. □

Proof of Equation (3.7). Let α ∈ B_{n}(T_{8}). If α_{1} unbarred, then it is easy to see that (α_{2}, …, α_{n}) decomposes into two decreasing subsequences such that all the symbols |α_{1}| + 1, …, n are barred and the other symbols are unbarred. Hence, there are 2^{n−1} such signed permutations. If |α_{1}| < n and α_{1} is barred, then (similarly) there are ∑_{i=1}^{n−1} 2^{i−1} such signed permutations. Finally, if α_{1} = \overline{n} then by definition there are b_{n−1}(T_{8}) such signed permutations. Everything combined, we have b_{n}(T_{8}) = b_{n−1}(T_{8})+ 2 · 2^{n−1} − 1. The initial conditions are b_{2}(T_{8}) = 5, b_{1}(T_{8}) = 2, and b_{0}(T_{8}) = 1, hence (3.7) follows. □

Corollary 3.6. Let τ ∈ \{21, \overline{2}1\}. Then b_{n}(T_{8} ∪ \{τ\}) = 2n for all n ≥ 1.

Proof. This is immediate if one uses the argument in the proof of (3.7). □

Proof of Equation (3.8), first case. Let α ∈ B_{n}(T_{9}). Let α_{i} be the first unbarred entry in α (i minimal), and let α_{j} be the last unbarred entry in α (j maximal). Since α avoids 12, all the symbols which are not barred are decreasing, and since α avoids 2\overline{1} and \overline{2}1, we can write α = (β, γ, δ), where β is a permutation of the numbers \overline{1}, …, \overline{i}, γ = (n−j, n−1−j, …, i+1), and β is a permutation of the numbers \overline{n − j + 1}, …, \overline{n}. Hence b_{n}(T_{9}) = ∑_{j=0}^{n}(n − j)!j!, as claimed in the first part of (3.8). □

Proof of Equation (3.8), second case. Let α ∈ B_{n}(T_{10}). Let j be maximal such that α_{j} is barred. Since α avoids T_{10}, we can write α = (β, γ), where all symbols of β are barred, all symbols of γ are unbarred, and |β_{j}| > |γ_{i}| for all i and j. Hence b_{n}(T_{10}) = ∑_{j=0}^{n}(n − j)!j!, as claimed in the second part of (3.8). □

4. Four signed patterns

The 70 choices of four 2-letter signed patterns reduce to the following 16 cases:

U_{1} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}\}; U_{2} = \{12, 1\overline{2}, \overline{1}2, 21\}; U_{3} = \{12, 1\overline{2}, \overline{1}2, 2\overline{1}\};
U_{4} = \{12, 1\overline{2}, \overline{1}2, \overline{2}\overline{1}\}; U_{5} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21\}; U_{6} = \{12, 1\overline{2}, \overline{1}\overline{2}, 2\overline{1}\};
U_{7} = \{12, 1\overline{2}, \overline{1}\overline{2}, \overline{2}1\}; U_{8} = \{12, 1\overline{2}, 21, 2\overline{1}\}; U_{9} = \{12, 1\overline{2}, 21, \overline{2}1\};
U_{10} = \{12, 1\overline{2}, 21, \overline{2}\overline{1}\}; U_{11} = \{12, 1\overline{2}, 2\overline{1}, \overline{2}1\}; U_{12} = \{12, 1\overline{2}, 2\overline{1}, \overline{2}\overline{1}\};
U_{13} = \{12, 1\overline{2}, \overline{2}1, \overline{2}\overline{1}\}; U_{14} = \{12, \overline{1}\overline{2}, 21, \overline{2}\overline{1}\}; U_{15} = \{12, \overline{1}\overline{2}, 2\overline{1}, \overline{2}1\};
U_{16} = \{1\overline{2}, \overline{1}2, 2\overline{1}, \overline{2}1\}.

Theorem 4.1. Given n and a set T of 2-letter signed patterns such that |T | = 4, the value b_{n}(T) for n ≥ 3 can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which T belongs:

\begin{matrix}(4.1) & b_{n}(U_{14}) = 0; \\ (4.2) & b_{n}(U_{10}) = b_{n}(U_{15}) = 2n; \\ (4.3) & b_{n}(U_{4}) = b_{n}(U_{5}) = b_{n}(U_{7}) = 1 + \binom{n+1}{2}; \\ (4.4) & b_{n}(U_{1}) = b_{n}(U_{6}) = b_{n}(U_{12}) = b_{n}(U_{13}) = 2^{n}; \\ (4.5) & b_{n}(U_{8}) = b_{n}(U_{9}) = b_{n}(U_{16}) = 2n!; \\ (4.6) & b_{n}(U_{3}) = b_{n}(U_{11}) = ∑_{j=0}^{n} j!; \\ (4.7) & b_{n}(U_{2}) = n! (1 + ∑_{j=1}^{n} \frac{1}{j} \binom{n}{j}^{−1}) . \end{matrix}

Proof. Equation (4.1) is obvious, while Equation (4.2) follows by Corollary 3.6, and Equation (4.4) holds by Corollaries 3.4 and 3.5.

To verify (4.3), by Corollaries 3.2 and 3.3 it is sufficient to prove b_{n}(U_{7}) = 1+\binom{n+1}{2}. Let α ∈ B_{n}(U_{7}). If α_{1} is unbarred, then since α avoids \{12, 1\overline{2}\} we have α_{1} = n, and in this case there are b_{n−1}(U_{7}) such signed permutations. If α_{1} is barred, then since α avoids \overline{1}\overline{2}, all the symbols |α_{1}| + 1, …, n are unbarred and decreasing (since α avoids 12), and since α avoids \overline{2}1 all the symbols |α_{1}|−1, …, 1 are barred and decreasing (since α avoids \overline{1}\overline{2}). Therefore, since α avoids 1\overline{2} and \overline{2}1, we have α = (\overline{i}, n, …, i+1, \overline{i − 1}, …, \overline{1}). Thus there are n such signed permutations. This implies the recurrence b_{n}(U_{7}) = b_{n−1}(U_{7})+n for n ≥ 1. If this is combined with the initial conditions b_{0}(U_{7}) = 1 and b_{1}(U_{7}) = 2, Equation (4.3) follows.

To find b_{n}(U_{9}), note that α ∈ B_{n}(U_{9}) has two cases. The first case occurs when the symbol n is unbarred in α; since α avoids {12, 21} all symbols of α are barred, so there are n! signed permutations. The second case occurs when the symbol n is barred in α; since α avoids \{\overline{2}1, 1\overline{2}\}, all other symbols are barred, so there are n! signed permutations. Therefore b_{n}(U_{9}) = 2n! for n ≥ 1. Similarly b_{n}(U_{16}) = 2n! for n ≥ 1. By Corollary 3.4 b_{n}(U_{8}) = 2n! for n ≥ 1, yielding (4.5).

To find b_{n}(U_{3}), we distinguish again between two cases. Let α ∈ B_{n}(U_{3}). The first case arises if α_{n} is unbarred. Then, since α avoids \{12, \overline{1}2\}, we must have α_{n} = 1. Thus, there are b_{n−1}(U_{3}) such signed permutations. The second case arises if α_{n} is barred. Since α avoids \{1\overline{2}, 2\overline{1}\}, all symbols of α are barred, which implies that there are n! such signed permutations. Accordingly, b_{n}(U_{3}) = b_{n−1}(U_{3}) + n! for n ≥ 1. Since b_{0}(U_{3}) = 1, it follows that b_{n}(U_{3}) = ∑_{j=0}^{n} j!.

To find b_{n}(U_{11}), note that for any α ∈ B_{n}(U_{11}) we can write α = (β, γ), where γ = (n, …, n−j+1) and β is a permutation of \overline{1}, \overline{2}, …, \overline{n − j}. Thus b_{n}(U_{11}) = 0!+1!+⋯+n! for all n ≥ 0, as claimed in (4.6).

To verify (4.7), we distinguish again between two cases. Let α ∈ B_{n}(U_{2}). Either α contains one unbarred symbol, or all the symbols of α are barred. In the second case there are n! such signed permutations. In the first case, let α = (β, i, γ), where β and γ are permutations of subsets of \overline{1}, \overline{2}, …, \overline{n}. By definition, we get that |β_{p}| > i > |γ_{j}|, hence there are

∑_{i=1}^{n}(n − i)!(i − 1)! = n! ∑_{i=1}^{n} \frac{1}{i}\binom{n}{i}^{−1}

such signed permutations. Thus, Equation (4.7) is established. □

Corollary 4.2. We have that b_{n}(U_{7} ∪ \{21\}) = b_{n}(U_{7} ∪ \{2\overline{1}\}) = n + 1 for all n ≥ 0.

Proof. Let τ ∈ \{21, 2\overline{1}\}. By the proof of Theorem 4.1 (Case b_{n}(U_{7})), we obtain b_{n}(U_{7} ∪ {τ}) = b_{n−1}(U_{7} ∪ {τ}) + 1. Furthermore, b_{n}(U_{7} ∪ {τ}) = n + 1 for n = 0, 1, 2, hence the corollary follows. □

5. More than four signed patterns

The 56 choices of five 2-letter signed patterns reduce to the following 10 cases:

W_{1} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 21\}; W_{2} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 2\overline{1}\}; W_{3} = \{12, 1\overline{2}, \overline{1}2, 21, 2\overline{1}\};
W_{4} = \{12, 1\overline{2}, \overline{1}2, 21, \overline{2}\overline{1}\}; W_{5} = \{12, 1\overline{2}, \overline{1}2, 2\overline{1}, \overline{2}1\}; W_{6} = \{12, 1\overline{2}, \overline{1}2, 2\overline{1}, \overline{2}\overline{1}\};
W_{7} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21, 2\overline{1}\}; W_{8} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21, \overline{2}1\}; W_{9} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21, \overline{2}\overline{1}\};
W_{10} = \{12, 1\overline{2}, \overline{1}\overline{2}, 2\overline{1}, \overline{2}1\}.

Theorem 5.1. Given n and a set T of 2-letter signed patterns such that |T | = 5, the value b_{n}(T) can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which T belongs:

\begin{matrix}(5.1) & b_{n}(W_{9}) = 0 for n > 2; \\ (5.2) & b_{n}(W_{4}) = 3; \\ (5.3) & b_{n}(W_{1}) = b_{n}(W_{2}) = b_{n}(W_{6}) = b_{n}(W_{7}) = b_{n}(W_{8}) = b_{n}(W_{10}) = n + 1; \\ (5.4) & b_{n}(W_{5}) = 1 + n!; \\ (5.5) & b_{n}(W_{3}) = (n + 1)(n − 1)!. \end{matrix}

Proof. Equation (5.1) follows from the simple observation that no signed permutation containing more than one unbarred symbol can avoid both 12 and 21, and similarly no signed permutation containing more than one barred symbol can avoid both \overline{1}\overline{2} and \overline{2}\overline{1}. Equation (5.2) can be established by checking that

B_{n}(W_{4}) = \{(\overline{1}, \overline{2}, …, \overline{n}), (\overline{2}, …, \overline{n}, 1), (\overline{1}, \overline{2}, …, \overline{n − 1}, n)\}.

Now we address Equation (5.3). We found b_{n}(W_{8}) and b_{n}(W_{10}) already in Corollary 4.2. A permutation in B_{n}(W_{1}) can only contain one unbarred symbol, while all the symbols must decrease in absolute value from left to right in order to avoid 12, 1\overline{2}, \overline{1}2 and \overline{1}\overline{2}. There are n + 1 ways to put at most one bar on the all-decreasing permutation. The remaining three cases are similarly easy to check. Next we address Equation (5.4). The set W_{5} contains all four patterns combining one barred symbol with one unbarred symbol. This means that any permutation avoiding W_{5} must be entirely barred or entirely unbarred. The restriction 12 reduces the possibilities on the “unbarred side” to just one, the all-descending permutation; while on the “barred side” there is no restriction. Thus we have n! possibilities. To verify Equation (5.5), let α ∈ B_{n}(W_{3}) such that |α_{j}| = 1. If α_{j} = 1, then, since α avoids \{12, 21\}, all symbols of α except 1 are barred, and since α avoids 1\overline{2}, we get j = n. Thus there are (n − 1)! such signed permutations. If α_{j} = \overline{1}, then, since α avoids \{\overline{1}2,2\overline{1}\}, all symbols of α are barred. Thus there are n! such signed permutations. Hence, b_{n}(W_{3}) = (n + 1)(n − 1)!. □

The question of determining the values b_{n}(T) where T ⊂ B_{2} and |T | = 6, with 28 possible choices for T, reduces to the following 8 cases:

V_{1} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 21, 2\overline{1}\}; V_{2} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 21, \overline{2}\overline{1}\}; V_{3} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 2\overline{1}, \overline{2}1)\};
V_{4} = \{12, 1\overline{2}, \overline{1}2, 21, 2\overline{1}, \overline{2}1\}; V_{5} = \{12, 1\overline{2}, \overline{1}2, 21, 2\overline{1}, \overline{2}\overline{1}\}; V_{6} = \{12, 1\overline{2}, \overline{1}2, 2\overline{1}, \overline{2}1, \overline{2}\overline{1}\};
V_{7} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21, 2\overline{1}, \overline{2}\overline{1}\}; V_{8} = \{12, 1\overline{2}, \overline{1}\overline{2}, 21, \overline{2}1, \overline{2}\overline{1}\}.

Theorem 5.2. Given n and set T of 2-letter signed patterns such that |T | = 6, the value b_{n}(T) for n ≥ 2 can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which T belongs:

\begin{matrix}(5.6) & b_{n}(V_{2}) = b_{n}(V_{7}) = b_{n}(V_{8}) = 0; \\ (5.7) & b_{n}(V_{1}) = b_{n}(V_{3}) = b_{n}(V_{5}) = b_{n}(V_{6}) = 2; \\ (5.8) & b_{n}(V_{4}) = n! for all n ≥ 2. \end{matrix}

Proof. Equation (5.6) is an immediate consequence of Equation (5.1) in Theorem 5.1.

In order to prove Equation (5.7), we verify that

B_{n}(V_{1}) = \{(\overline{n}, …, \overline{2}, \overline{1}), (\overline{n}, …, \overline{2}, 1)\},
B_{n}(V_{3}) = \{(\overline{n}, …, \overline{2}, \overline{1}), (n, …, 2, 1)\},
B_{n}(V_{5}) = \{(\overline{1}, \overline{2}, …, \overline{n}), (\overline{2}, …, \overline{n}, 1)\},
B_{n}(V_{6}) = \{((n, …, 2, 1), (\overline{1}, \overline{2}, …, \overline{n})\},

which is easy to do.

Finally, Equation (5.8) follows from the argument given in the proof of Theorem 5.1, Equation (5.4). □

Finally, the 8 choices of seven patterns reduce to 2, which we present together with the final case, in which we forbid all eight patterns:

U_{1} = B_{2}, U_{2} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 21, 2\overline{1}, \overline{2}\overline{1}\}, U_{3} = \{12, 1\overline{2}, \overline{1}2, \overline{1}\overline{2}, 21, 2\overline{1}, \overline{2}1\}.

Theorem 5.3. Given n and set T of 2-letter signed patterns such that |T | = 7, 8, the value b_{n}(T) for n ≥ 3 can be determined from one of the following relations, depending on the orbit (under reversal, barring, complementation) to which T belongs:

\begin{matrix}(5.9) & b_{n}(U_{1}) = b_{n}(U_{2}) = 0; \\ (5.10) & b_{n}(U_{3}) = 1. \end{matrix}

Proof. Equation (5.9) follows from the same arguments as above. Equation (5.10) follows easily from the fact that B_{n}(U_{3}) = \{\overline{n}, …, \overline{2}, \overline{1}\}. □

Acknowledgments. The authors are grateful to the referees for careful reading of the manuscript. The final version of this paper was written during the first author’s (T.M.) stay at Chalmers University of Technology in Göteborg, Sweden. T.M. wants to express his gratitude to Chalmers University of Technology for the support.

References

[Be] D.A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discr. 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, 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.

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

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

[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).

[M] T. Mansour, Pattern avoidance in coloured permutations, Séminaire Lotharingien de Combinatoire, 46 (2001), Article B46g.

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

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

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

[Ri] J. Riordan, Combinatorial Identities, John Wiley, New York, 1968.

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

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

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

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