# Restricted signed permutations counted by the Schrder numbers

Restricted Signed Permutations Counted by the Schr¨der Numbers? o
Eric S. Egge Department of Mathematics and Computer Science Carleton College North?eld, MN 55057 USA eggee@member.ams.org August 24, 2005
Abstract Gire, West, and Kremer have found ten classes of restricted permutations counted by the large Schr¨der numbers, no two of which are trivially Wilf-equivalent. In this o paper we enumerate eleven classes of restricted signed permutations counted by the large Schr¨der numbers, no two of which are trivially Wilf-equivalent. We obtain ?ve o of these enumerations by elementary methods, ?ve by displaying isomorphisms with the classical Schr¨der generating tree, and one by giving an isomorphism with a new o Schr¨der generating tree. When combined with a result of Egge and a routine computer o search, this completes the classi?cation of restricted signed permutations counted by the large Schr¨der numbers in which the set of restrictions consists of two patterns of o length 2 and two of length 3. Keywords: Restricted permutation; pattern-avoiding permutation; forbidden subsequence; Schr¨der number; signed permutation; generating tree o

1

Introduction and Notation

Let Bn denote the set of permutations of {1, 2, . . . , n}, written in one-line notation, in which each element may or may not have a bar above it. We refer to the elements of Bn as signed permutations. We write Sn to denote the set of elements of Bn with no bars, and we refer to these elements as classical permutations. For any signed permutation π we write |π| to denote the length of π and we write ||π|| to denote the classical permutation obtained by removing the bars from π. For a given signed permutation π we write π(i) to denote the ith entry of π. Suppose π and σ are signed permutations. We say a subsequence of π has type σ whenever it has all of the same pairwise comparisons as σ and an entry in the subsequence of π is barred
?

2000 Mathematics Subject Classi?cation: Primary 05A05, 05A15

1

if and only if the corresponding entry in σ is barred. For example, the subsequence 3471 of the signed permutation 934728516 has type 2341. We say π avoids σ whenever π has no subsequence of type σ. For example, the signed permutation 934728516 avoids 321 and 1432 but it has 925 as a subsequence so it does not avoid 312. In this setting σ is sometimes called a pattern or a forbidden subsequence and π is sometimes called a restricted permutation or a pattern-avoiding permutation. In this paper we will be interested in signed permutations which avoid several patterns, so for any set R of signed permutations we write Bn (R) to denote the set of signed permutations of length n which avoid every pattern in R and we write B(R) to denote the set of all signed permutations which avoid every pattern in R. When R = {π1 , . . . , πr } we often write Bn (R) = Bn (π1 , . . . , πr ) and B(R) = B(π1 , . . . , πr ). When we wish to discuss classical permutations, we replace B with S in the above notation. Suppose R1 and R2 are sets of signed permutations. We say R1 and R2 are Wilf-equivalent whenever |Bn (R1 )| = |Bn (R2 )| for all n ≥ 0. There are four natural operations which preserve Wilf-equivalence classes: ? the bar operator, which replaces each barred entry in a signed permutation with its unbarred counterpart and vice versa; ? the reverse operator, which writes the entries of a signed permutation in reverse order; ? the complement operator, which replaces each entry π(i) of a signed permutation π with |π| + 1 ? π(i); ? the inverse operator, which takes replaces each signed permutation with its grouptheoretic inverse. For example, if π = 2413 then bar(π) = 2413, reverse(π) = 3142, complement(π) = 3142, and inverse(π) = 3142. If we write each signed permutation as a square permutation matrix in which barred entries are represented by ?1s, then the bar operator is multiplication by ?1, the reverse operator is the re?ection over the vertical axis, the complement operator is the re?ection over the horizontal axis, and the inverse operator is both the re?ection over the main diagonal and the usual matrix inverse. From this one can show that the group G generated by these operations is isomorphic to D8 ⊕ Z2 , where D8 is the dihedral group of order 8. We say R1 is trivially Wilf-equivalent to R2 whenever R2 is the image of R1 under some element of G. The focus of this paper is on restricted signed permutations, but it includes a major role for the large Schr¨der numbers. (There are also small Schr¨der numbers, which are, o o up to a shift in index, half of the large Schr¨der numbers.) The large Schr¨der numbers o o (hereafter just the Schr¨der numbers) may be recursively de?ned by r0 = 1 and rn = o rn?1 + n rk?1 rn?k for n ≥ 0. From this de?nition one can show that the generating k=1 function for the Schr¨der numbers is given by o √ ∞ 1 ? x ? x2 ? 6x + 1 n . (1) rn x = 2x n=0

2

The Schr¨der numbers are closely related to the ubiquitous Catalan numbers, and in partico ular one can also show that
n

rn =
d=0

2n ? d Cn?d d

(n ≥ 0).

(2)

1 Here Cn is the nth Catalan number, which may be de?ned by Cn = n+1 2n . For a list n of some of the known combinatorial interpretations of the Schr¨der numbers, see [10, pp. o 239–240]. Gire [5], West [11], and Kremer [6] have found ten classes of classical pattern-avoiding permutations which are enumerated by the Schr¨der numbers. (See [2] for other work along o these lines.) Each of the corresponding sets of forbidden patterns consists of two classical permutations, each of length 4, and no two of these sets are trivially Wilf-equivalent. A computer search reveals that every pair of classical permutations of length 4 whose patternavoiding permutations are enumerated by Schr¨der numbers is trivially Wilf-equivalent to o one of the ten sets found by Gire, West, and Kremer, but to the best of our knowledge it is not known whether there are other classes of classical pattern-avoiding permutations which are enumerated by the Schr¨der numbers. o The enumeration of restricted signed permutations was introduced by Simion [9] and studied further by Mansour and West [7]. In this paper we continue this study, considering in particular the following eleven sets of forbidden signed permutations.

I. 21, 21, 123, 123 II. 21, 21, 123, 132 III. 21, 21, 123, 231

V. 21, 21, 123, 321 VI. 21, 21, 312, 312 VII. 21, 21, 321, 321

IX. 21, 21, 231, 312 X. 21, 21, 132, 132 XI. 21, 21, 321, 312

IV. 21, 21, 123, 312 VIII. 21, 21, 321, 312 We begin by using elementary methods to show that if T is any set of classical permutations then |Bn (21, 21, 123, T )| is a convolution of |Sn (T )| with a certain sequence of binomial coe?cients. Combining this with (2), we conclude that for any set R among I–V we have |Bn (R)| = rn for all n ≥ 0. Next we recall some basic facts concerning generating trees, including the classical Schr¨der tree, and we describe how each set of restricted signed o permutations can be organized into a generating tree in a natural way. For each set R among VI–X we give an isomorphism between the generating tree for B(R) and the classical Schr¨der tree. It follows that for each set R among VI–X we have |Bn (R)| = rn for all n ≥ 0. o We then introduce a new generating tree, which we call the tilted Schr¨der tree. We use o the kernel method to prove that for all n ≥ 0 this tree has exactly rn nodes on level n, and we give an isomorphism between the generating tree for B(21, 21, 321, 312) and the tilted Schr¨der tree. It follows that |Bn (21, 21, 321, 312)| = rn for all n ≥ 0. o Egge has previously shown [4] that |Bn (21, 21, 312, 312)| = rn for all n ≥ 0. It is routine to check that no two of the sets of forbidden signed permutations in I–XI are trivially Wilfequivalent, and that none is trivially Wilf-equivalent to 21, 21, 312, 312. A computer search reveals that if R is any set of signed permutations consisting of two signed permutations of length 2 and two of length 3, and |Bn (R)| = rn for 0 ≤ n ≤ 5, then R is trivially 3

Wilf-equivalent to 21, 21, 312, 312 or to one of the sets in I–XI. In short, up to trivial Wilfequivalence, this paper completes the classi?cation of restricted signed permutations counted by the Schr¨der numbers whose forbidden patterns consist of two patterns of length 2 and o two of length 3. To the best of our knowledge, it is not known whether there are other classes of restricted signed permutations counted by the Schr¨der numbers. o

2

A Convolution with Certain Binomial Coe?cients

Some enumerations of pattern-avoiding signed permutations can be obtained from corresponding enumerations of classical pattern-avoiding permutations. For instance, the fact that |Bn | = 2n |Sn | for n ≥ 0 can be generalized as follows. ? De?nition 2.1 For any set T of classical permutations, we write T to denote the set of signed permutations obtained by putting bars over the entries in the elements of T in all possible ways. ? To illustrate De?nition 2.1, we observe that if T = {12} then T = {12, 12, 12, 12}. Proposition 2.2 For any set T of classical permutations, we have Bn (T ) = Sn (T ) In particular, ? |Bn (T )| = 2n |Sn (T )| (n ≥ 0). (4) (n ≥ 0). (3)

Proof. To prove (3), note that π ∈ Bn (T ) if and only if ||π|| ∈ Sn (T ). Line (4) is immediate from (3). 2 Proposition 2.2 allows us to recover a result of Mansour and West. Corollary 2.3 ([7, Eq. (4.4)]) For all n ≥ 0 we have |Bn (12, 12, 12, 12)| = 2n . Proof. Set T = {12} in (4) and use the fact that |Sn (12)| = 1 for all n ≥ 0. 2 The main result of this section relates enumerations of classical pattern-avoiding permutations with pattern-avoiding signed permutations by a convolution with certain binomial coe?cients. To prove the result, we’ll use the following technical lemma. Lemma 2.4 A signed permutation π avoids 21, 21, and 123 if and only if both of the following hold. (i) The barred entries of π are in increasing order. (ii) If a barred entry of π has an unbarred entry to its right, then the barred entry is less than all unbarred entries of π. Proof. (=?) Suppose π avoids 21, 21, and 123. First observe that (i) follows from the fact that π avoids 21. To prove (ii), suppose π(i) is barred, π(j) is unbarred, and i < j. If there is an unbarred entry a of π to the right of π(i) such that π(i) > a then π(i)a has type 21. If there is an unbarred entry a of π to the left of π(i) such that π(i) > a then aπ(i)π(j) has type 123. Now (ii) follows. 4

(?=) Suppose (i) and (ii) hold for a signed permutation π. By (i), π avoids 21. If π contains a pattern of type 21 or 123 then the entry playing the role of the 2 violates (ii), so π avoids 21 and 123. 2 In our next result, we use Lemma 2.4 to count signed permutations which have a given number of barred entries and which avoid 21, 21, 123, and any set T of classical patterns. Proposition 2.5 Let T denote a set of classical permutations. Then for all n ≥ 0 and all 2n ? d d such that 0 ≤ d ≤ n there are |Sn?d (T )| signed permutations in Bn which avoid d 21, 21, 123, and T and which have exactly d barred entries. Proof. Fix n ≥ 0 and d such that 0 ≤ d ≤ n. We ?rst describe an algorithm for constructing a signed permutation π which avoids 21, 21, 123, and T and which has exactly d barred entries. 1. Choose a classical permutation σ ∈ Sn?d (T ). 2. Construct the graph of σ by placing dots at the points (i, σ(i)) for 1 ≤ i ≤ n ? d.
1 1 3. View the n?d vertical lines x = 2 , x = 3 , . . . , x = n?d? 2 and the n?d+1 horizontal 2 1 lines y = 2 , y = 3 , . . . , y = n ? d + 1 as baskets, and place a total of d indistinguishable 2 2 balls in the 2n ? 2d + 1 baskets.

4. Produce the graph of a signed permutation as follows. (a) Space the points of the graph of σ and the inserted balls in order horizontally, 1 starting with the balls on x = 2 , followed by the dot at (1, σ(1)), followed by the 3 balls on x = 2 , etc., followed by the dot at (n ? d, σ(n ? d)), followed by the balls 3 1 on y = 2 , followed by the balls on y = 2 , etc. (b) Space the points of the graph of σ and the inserted balls in order vertically, 1 starting with the balls on x = 2 , followed by the balls on x = 3 , etc., followed by 2 1 the balls on x = n ? d ? 2 , followed by the balls on y = 1 , followed by the dot at 2 (σ ?1 (1), 1), followed by the balls on y = 3 , followed by the dot at (σ ?1 (2), 2), etc. 2 Observe that step 4 guarantees that this algorithm always produces (the graph of) a signed permutation of length n with exactly d barred entries. In view of Lemma 2.4, the algorithm produces only signed permutations which avoid 21, 21, 123, and T , and each such signed permutation is produced in exactly one way. Steps 2 and 4 may each be performed in just one way, and step 1 may be performed in |Sn?d (T )| ways. In step 3 we are inserting d indistinguishable balls in 2n ? 2d + 1 distinguishable baskets; there are 2n?d ways to do d this. The result follows. 2 Proposition 2.5 gives us two sets of signed permutations counted by the Fibonacci numbers, one of which was previously found by Mansour and West [7, Eq. (3.5)] and later by Egge [4]. Proposition 2.6 For any permutation σ ∈ S2 we have |Bn (21, 21, 123, σ)| = F2n+1 5 (n ≥ 0), (5)

where Fn is the nth Fibonacci number, de?ned by F0 = 0, F1 = 1, and Fn = Fn?1 + Fn?2 for n ≥ 2. Proof. Set T = {σ} in Proposition 2.5 and use the fact that |Sn (T )| = 1 for all n ≥ 0 to obtain n 2n ? d |Bn (21, 21, 123, σ)| = (n ≥ 0). d d=0 This last expression is well-known to be equal to F2n+1 . (See [3, Thm. 7.1.2], for instance.) 2 Proposition 2.5 gives us ?ve new sets of signed permutations counted by the Schr¨der o numbers. Theorem 2.7 For any permutation σ ∈ S3 we have |Bn (21, 21, 123, σ)| = rn (n ≥ 0). (6)

We observe that the sets corresponding to σ = 132 and σ = 213 are trivially Wilf-equivalent. Proof. Set T = {σ} in Proposition 2.5, use the fact that |Sn (σ)| = Cn for n ≥ 0, and use (2) to simplify the result. 2

3

An Interlude on Generating Trees

For our purposes, a generating tree is a rooted, labeled tree in which the label of each node determines that node’s number of children and their labels. We generally specify a particular generating tree by giving two pieces of data: ? the label of the root node; ? a list of succession rules, which state for each label k the number of children a node with label k has and what their labels are. Many generating trees of combinatorial signi?cance are known; [1, 12] contain several examples of interest. We content ourselves here by recalling one which is particularly relevant. Example 3.1 [12, Ex. 5] The classical Schr¨der generating tree is given by o ? Root: (2); ? Rule: (k) → (3)(4) · · · (k ? 1)(k)(k + 1)(k + 1) for k ≥ 2. Given a generating tree, we are often interested in how many nodes it has on level n, where the root is on level 0. The classical Schr¨der tree gets its name from the well-known fact o that it has rn nodes on level n for all n ≥ 0. Signed pattern-avoiding permutations (as well as classical pattern-avoiding permutations) have a natural generating tree structure. To describe this structure, suppose T is a set of forbidden signed permutations. The nodes on level n of the associated generating tree are the elements of Bn (T ), and in the absence of a simpler labeling scheme, we regard each 6

node as being labeled with its associated signed permutation. Each signed permutation π ∈ Bn?1 (T ) has n spaces in which an n or an n may be inserted to produce a signed permutation in Bn , but in general only some of the resulting signed permutations will avoid T . For us the children of π ∈ Bn?1 (T ) are those signed permutations which are obtained from π by inserting n or n and which avoid T . Given π ∈ Bn?1 (T ), we call an insertion space unbar-active (resp. bar-active) whenever insertion of n (resp. n) in that space produces an element of Bn (T ) and we call the space unbar-inactive (resp. bar-inactive) otherwise. Example 3.2 Suppose T = {21, 123} and π = 41523. Then the left-most three spaces of π are unbar-active, the remaining spaces are unbar-inactive, the right-most two spaces of π are bar-active, and the remaining spaces are bar-inactive. Suppose T is a set of forbidden patterns and π ∈ Bn?1 (T ) for some n ≥ 1. We note that if a space is unbar-inactive in π then it retains that status in all of the children of π. Inserting n into an unbar-inactive space of π produces a forbidden pattern, and since π avoids T , the newly inserted entry n must participate in that forbidden pattern. Along the same lines, suppose spaces s1 and s2 in π are unbar-active, but insertion of n in s1 causes s2 to become unbar-inactive. Then the signed permutation obtained from π by inserting n in s1 and n + 1 in s2 contains a forbidden pattern, and n and n + 1 both participate in that pattern. Similar comments hold for bar-active and bar-inactive spaces.

4

Isomorphisms to the Classical Schr¨der Tree o
? T1 = {21, 21, 312, 312} ? T2 = {21, 21, 321, 321} ? T3 = {21, 21, 321, 312} ? T4 = {21, 21, 231, 312} ? T5 = {21, 21, 132, 132}

In this section we consider the following ?ve sets of forbidden signed permutations.

Following [6, 11], for each of T1 ? T5 we give an isomorphism between the generating tree for the associated pattern-avoiding signed permutations and the classical Schr¨der generating o tree. To obtain our isomorphisms, we analyze the behavior of the unbar-active and bar-active spaces of a signed permutation when n or n is inserted. We begin by observing that if π avoids any of T1 ? T5 then just one space in π can be unbar-active. Lemma 4.1 Suppose n ≥ 2 and T is one of T1 ? T5 above. Fix π ∈ Bn?1 (T ). Then the right-most space of π is unbar-active and all other spaces of π are unbar-inactive. Proof. Observe that no forbidden pattern ends with its largest entry, so the right-most space of π is unbar-active. However, inserting n into any other space will produce a subsequence of type 21 or a subsequence of type 21, depending on whether the right-most entry of π is barred. Both patterns are forbidden, so no other space in π is unbar-active. 2 Next we analyze the e?ect inserting n has on the bar-active spaces. Lemma 4.2 Suppose n ≥ 2 and T is one of T1 ? T5 above. Fix π ∈ Bn?1 (T ) and let π + denote the signed permutation obtained by appending n to the right end of π. Then the following hold. 7

(i) The right-most two spaces of π + are bar-active. (ii) Suppose s is a space in π + which is not one of the right-most two spaces. Abusing notation, we identify s with the corresponding space in π. Then s is bar-active in π + if and only if it is bar-active in π. Proof. (i) None of the forbidden patterns of length 2 contains 2 and none of the forbidden patterns of length 3 ends with 3, so the right-most space of π + is bar-active. Similarly, none of the forbidden patterns of length 3 contains 32, so the second space from the right end of π + is bar-active. (ii) If s is bar-inactive in π then it remains so in π + , so suppose by way of contradiction that s is bar-active in π and bar-inactive in π + . Then inserting n + 1 in π + at s produces a forbidden pattern in which both n and n + 1 participate. But none of the forbidden patterns of length 2 contains 2 and none of the forbidden patterns of length 3 contains 2. This is a contradiction, so s must be bar-active in π + . 2 We now give an isomorphism between the generating tree for B(T1 ) and the classical Schr¨der generating tree. This example illustrates one of the simpler ways the classical o Schr¨der tree can appear as a tree of pattern-avoiding permutations. o Theorem 4.3 For each signed permutation π ∈ B(T1 ), let f1 (π) denote one plus the number of spaces in π with no subsequence of type 12 or 12 to their right. Then the map π → f1 (π) is an isomorphism of generating trees between the generating tree for B(T1 ) and the classical Schr¨der generating tree. In particular, o |Bn (21, 21, 312, 312)| = rn (n ≥ 0).

Proof. To begin, observe that f1 (?) = 2 and f1 (1) = f1 (1) = 3, so both trees have the same ?rst two levels, and it is su?cient to show they have the same succession rules. Fix n ≥ 2 and suppose π ∈ Bn?1 (T1 ). Observe that since 2 does not appear in the forbidden patterns of length 2, and since the other two forbidden patterns are 312 and 312, a space in π is bar-active if and only if it has no subsequence of type 12 or 12 to its right. In view of Lemma 4.1, the signed permutation π has f1 (π) ? 1 spaces which are bar-active and 1 space which is unbar-active, so π has f1 (π) children. In view of Lemma 4.2, the child of π obtained by inserting n has f1 (π)+1 children, so its image under f1 is f1 (π)+1. To count the children of the signed permutations obtained by inserting n into π, observe that the inserted n and the entry immediately to its left form a subsequence of type 12 or 12. Therefore the bar-active spaces in the new signed permutation are the spaces to the right of n and the space immediately to the left of n. Hence the children of π have 3, 4, . . . , f1 (π), f1 (π) + 1, f1 (π) + 1 children, and the result follows. 2 Next we describe an isomorphism between the generating tree for B(T2 ) and the classical Schr¨der generating tree. Here the classical Schr¨der tree appears in a slightly more o o complicated way. Theorem 4.4 For each signed permutation π ∈ B(T2 ), let f2 (π) denote one plus the number of spaces in π with no subsequence of type 21 or 21 to their right. Then the map π → f2 (π)

8

is an isomorphism of generating trees between the generating tree for B(T2 ) and the classical Schr¨der generating tree. In particular, o |Bn (21, 21, 321, 321)| = rn (n ≥ 0).

Proof. To begin, observe that f2 (?) = 2 and f2 (1) = f2 (1) = 3, so both trees have the same ?rst two levels, and it is su?cient to show they have the same succession rules. Fix n ≥ 2 and suppose π ∈ Bn?1 (T2 ). Observe that since 2 does not appear in the forbidden patterns of length 2, and since the other two forbidden patterns are 321 and 321, a space in π is bar-active if and only if it has no subsequence of type 21 or 21 to its right. In view of Lemma 4.1, the signed permutation π has f2 (π) ? 1 spaces which are bar-active and 1 space which is unbar-active, so π has f2 (π) children. In view of Lemma 4.2, the child of π obtained by inserting n has f2 (π) + 1 children, so its image under f2 is f2 (π) + 1. To count the children of the signed permutations obtained by inserting n into π, ?rst observe that if n is inserted in the right-most space, all bar-active spaces remain bar-active. If n is inserted in any other space, it forms a subsequence of type 21 or 21 with the entry immediately to its right. In this case all spaces to the left of n become bar-inactive, while those to the right of n remain bar-active. Therefore the children of π have f2 (π) + 1, 3, 4, . . . , f2 (π), f2 (π) + 1 children, and the result follows. 2 The generating tree for B(T3 ) is the classical Schr¨der tree in an even more complicated o way. Theorem 4.5 For each signed permutation π ∈ B(T3 ), let f3 (π) denote one plus the number of spaces in π with no subsequence of type 21 or 12 to their right. Then the map π → f3 (π) is an isomorphism of generating trees between the generating tree for B(T3 ) and the classical Schr¨der generating tree. In particular, o |Bn (21, 21, 321, 312)| = rn (n ≥ 0).

Proof. To begin, observe that f3 (?) = 2, and f3 (1) = f3 (1) = 3, so both trees have the same ?rst two levels, and it is su?cient to show they have the same succession rules. Fix n ≥ 2 and suppose π ∈ Bn?1 (T3 ). Observe that since 2 does not appear in the forbidden patterns of length 2, and since the other two forbidden patterns are 321 and 312, a space in π is bar-active if and only if it has no subsequence of type 21 or 12 to its right. In view of Lemma 4.1, the signed permutation π has f3 (π) ? 1 spaces which are bar-active and 1 space which is unbar-active, so π has f3 (π) children. In view of Lemma 4.2, the child of π obtained by inserting n has f3 (π) + 1 children, so its image under f3 is f3 (π) + 1. To count the children of the signed permutations obtained by inserting n into π, ?rst observe that all of the spaces to the right of the left-most bar-active space are also bar-active, and that the subsequence σ enclosed by the bar-active spaces avoids 21, 21, 21, and 12. Hence σ consists of a sequence of barred entries, in increasing order, followed by a sequence of unbarred entries, in increasing order. We consider three cases. Case One: σ has no barred entries. Observe that when we insert n into σ, we create a pattern of type 12 consisting of n and the necessarily unbarred entry immediately to its left. It follows that the bar-active spaces in 9

the new signed permutation are those to the right of n and the space immediately to the left. Therefore the children of π obtained by inserting n have 3, 4, . . . , f3 (π), f3 (π) + 1, f3 (π) + 1 children. Case Two: σ has no unbarred entries. First observe that when we insert n into the right-most space in σ, the spaces immediately left and right of n are bar-active. Moreover, since no bar-active space in π has an unbarred entry to its right and the only forbidden pattern which ends with its second largest entry barred is 312, all spaces which are bar-active in π are bar-active in the new signed permutation. Now suppose we insert n into a bar-active space other than the right-most space in σ. In this case we create a pattern of type 21 consisting of n and the entry immediately to its right. Therefore the bar-active spaces in the new signed permutation are those to the right of n. It follows that the children of π obtained by inserting n have f3 (π) + 1, 3, 4, . . . , f3 (π), f3 (π) + 1 children. Case Three: σ has both barred and unbarred entries. Observe that when we insert n into the bar-active space between the last barred entry and the ?rst unbarred entry in σ we create no subsequence of type 21 or 12 in σ, so the resulting signed permutation has f3 (π) + 1 children. Now suppose we insert n among the unbarred entries of σ. Then n, together with the unbarred entry immediately to its left, forms a 12 pattern. It follows that the bar-active spaces in the new signed permutation are those to the right of n and the space immediately to the left of n. Finally, suppose we insert n among the barred entries of σ. Then n, together with the barred entry immediately to its right, forms a 21 pattern. It follows that the bar-active spaces in the new signed permutation are those to the right of n. Combining these observations, we ?nd that the children of π obtained by inserting n have 3, 4, . . . , k + 2, f3 (π) + 1, k + 3, . . . , f3 (π), f3 (π) + 1 children, where k is the number of unbarred entries in σ. In all cases the children of π have 3, 4, . . . , f3 (π), f3 (π) + 1, f3 (π) + 1 children, and the result follows. 2 Next we describe an isomorphism between the generating tree for B(T4 ) and the classical Schr¨der generating tree. In contrast to our previous three isomorphisms, this map does not o include a detailed description of the locations of the bar-active spaces in a given permutation. Nevertheless, the proof of the theorem restricts these locations somewhat. Theorem 4.6 For each signed permutation π ∈ B(T4 ), let f4 (π) denote one plus the number of bar-active spaces in π. Then the map π → f4 (π) is an isomorphism of generating trees between the generating tree for B(T4 ) and the classical Schr¨der generating tree. In o particular, |Bn (21, 21, 231, 312)| = rn (n ≥ 0). Proof. To begin, observe that f4 (?) = 2 and f4 (1) = f4 (1) = 3, so both trees have the same ?rst two levels. In view of Lemma 4.1, the quantity f4 (π) is the number of children of π, so it is su?cient to verify these children have the correct labels. Fix n ≥ 2 and suppose π ∈ Bn?1 (T4 ). We consider two cases. 10

Case One: π ends with a (possibly empty) sequence σu of unbarred entries, which is immediately preceded by a nonempty sequence σb of barred entries. We ?rst claim that no space to the left of the right-most entry left of σb , which we denote by a, is bar-active. To see this, ?rst observe that a and the barred entry to its right form a sequence of type 21 or 12. The ?rst case is forbidden. If we insert n to the left of the right-most unbarred entry in the second case we produce a sequence of type 312, which is forbidden, and the claim follows. Suppose we insert n into a bar-active space in σu , so that n has an unbarred entry to its left. The only forbidden pattern of length 3 which has 2 and 3 adjacent is 231 and no entry to the right of n in the new signed permutation is barred, so the spaces immediately left and right of n are bar-active in the new signed permutation. Since 312 is forbidden, all other spaces to the left of n are bar-inactive in the new signed permutation. Since no forbidden pattern of length 3 has 1, 2, and 3 with 2 and 3 in increasing order, all spaces to the right of n which were bar-active in π are bar-active in the new signed permutation. Now suppose we insert n in the space between σb and σu . As above, the spaces immediately left and right of n are bar-active in the new signed permutation. Moreover, if a space was bar-active in π then it is also bar-active in the new signed permutation, since inserting n + 1 in σb cannot create a subsequence of type 312 and inserting n + 1 in σu cannot create a subsequence of type 231. Finally, suppose we insert n in a bar-active space in σb , so that n has a barred entry to its right. As above, the space immediately left of n is bar-active, but the space immediately right of n is not, since inserting n + 1 in that space produces a 231 pattern, which is forbidden. Similarly, every space to the right of n in σb is bar-inactive in the new signed permutation. All other spaces which were bar-active in π remain bar-active in the new signed permutation, since inserting n + 1 to the left of n cannot create a subsequence of type 312 and inserting n + 1 in σu cannot create a subsequence of type 231. Combining the observations above, and using the fact that the space between σb and σu is always bar-active, we ?nd the children of π have 3, 4, . . . , k + 2, f4 (π) + 1, f4 (π), . . . , k + 3, f4 (π) + 1 children, where k is the number of bar-active spaces in σu . Case Two: All entries in π are unbarred. First observe that since π avoids 21, we have π = 12 · · · n ? 1, and every space is baractive. Now suppose we insert n. As in Case One, the spaces immediately left and right of n are bar-active in the new signed permutation, the rest of the spaces to the left of n are bar-inactive, and all spaces to the right of n are bar-active. Therefore the children of π have 3, 4, . . . , f4 (π), f4 (π) + 1, f4 (π) + 1 children. Observe that in both cases the children of π have 3, 4, . . . , f4 (π), f4 (π) + 1, f4 (π) + 1 children, and the result follows. 2 We conclude this section by describing an isomorphism between the generating tree for B(T5 ) and the classical Schr¨der generating tree. o Theorem 4.7 For each signed permutation π ∈ B(T5 ), let f5 (π) denote one plus the number of bar-active spaces in π. Then the map π → f5 (π) is an isomorphism of generating trees between the generating tree for B(T5 ) and the classical Schr¨der generating tree. In o 11

particular, |Bn (21, 21, 132, 132)| = rn (n ≥ 0). Proof. To begin, observe that f5 (?) = 2 and f5 (1) = f5 (1) = 3, so both trees have the same ?rst two levels. In view of Lemma 4.1, the quantity f5 (π) is the number of children of π, so it is su?cient to verify these children have the correct labels. Fix n ≥ 2 and suppose π ∈ Bn?1 (T5 ). First observe that since no forbidden pattern begins with 2 or 3, the left-most space in π is bar-active. Suppose we insert n into the left-most space of π. Since 2 does not appear before 3 in any forbidden pattern, the spaces immediately left and right of n in the new signed permutation are bar-active, as are all spaces which were bar-active in π. Now suppose we insert n in a bar-active space of π other than the left-most space. Since 132 and 132 are both forbidden, the only bar-active space left of n in the new signed permutation is the left-most space. But since 2 does not appear before 3 in any forbidden pattern, the space immediately right of n is bar-active, as are all spaces to the right of n which were bar-active in π. Combining the above observations, we ?nd that the children of π have 3, 4, . . . , f5 (π), f5 (π)+ 1, f5 (π) + 1 children, and the result follows. 2

5

An Isomorphism to a New Schr¨der Tree o

So far we have studied ten sets of forbidden signed permutations, no two of which are trivially Wilf-equivalent, such that if T is any of these sets then |Bn (T )| = rn for all n ≥ 0. Egge has given [4, Eq. (8)] another such set, which is not trivially Wilf-equivalent to any of our sets. All eleven of these sets consist of two patterns of length 2 and two patterns of length 3, so it is natural to seek a list T1 , . . . , Tk such that the following hold. ? Ti consists of two signed permutations of length 2 and two signed permutations of length 3 for 1 ≤ i ≤ k. ? |Bn (Ti )| = rn for all n ≥ 0 and all i such that 1 ≤ i ≤ k. ? No two of T1 , . . . , Tk are trivially Wilf-equivalent. ? If T satis?es the ?rst two conditions above then T is trivially Wilf-equivalent to Ti for some i such that 1 ≤ i ≤ k. A computer search suggests that adding the set T12 = {21, 21, 321, 312} to our collection will give us the desired list. It is routine to verify that T12 is not trivially Wilf-equivalent to any of our sets, so in this section we prove that |Bn (T12 )| = rn for all n ≥ 0. To accomplish this, we ?rst introduce a new generating tree. De?nition 5.1 The tilted Schr¨der tree is the generating tree given by o ? Root: (2); ? Rules: (2) → (2)(4) (k) → (2)(4)(5) · · · (k)(k + 1)(k + 1) for k ≥ 4. 12

A preliminary examination of the tilted Schr¨der tree suggests it has rn nodes on level n. o We prove this next. Theorem 5.2 For all n ≥ 0, the tilted Schr¨der generating tree has exactly rn nodes on o level n. Proof. We use the kernel method. (See [1, 8] for more information on the kernel method.) For any node ν in the tilted Schr¨der tree, let level(ν) denote the level of ν and let label(ν) o denote the label of ν. Now let G(x, y) be given by G(x, y) =
ν

xlevel(ν) y label(ν) ,

where the sum on the right is over the nodes in the tilted Schr¨der tree. For all k ≥ 2 de?ne o Gk (x) by writing G(x, y) = Gk (x)y k . (7)
k≥2

We wish to obtain G(x, 1). To this end, count the children of each node in the tilted Schr¨der o tree to obtain G(x, y) = y 2 + G2 (x)x(y 2 + y 4 ) + x
k≥3

Gk (x)(y 2 + y 4 + y 5 + · · · + y k + 2y k+1 ).

(8)

Since every node has exactly one child with label 2, and the root has label 2, we also have G2 (x) = 1 + xG(x, 1). Use (9) to eliminate G2 (x) in (8) and use (7) to simplify the result and obtain xy 2 ? xy 4 xy 2 ? xy G(x, y) = y 2 + x(y 2 + y 4 ) + y?1 y?1 x2 y 4 + (1 ? x)xy 2 +G(x, 1) x2 (y 2 + y 4 ) ? ? x2 y 3 ? xy 3 (1 ? x) . y?1 √ 1 + x ? 1 ? 6x + x2 Now set y = and solve the resulting equation for G(x, 1) to obtain 4x √ 1 ? x ? x2 ? 6x + 1 G(x, 1) = . 2x 1? Now the result follows from (1). 2 Remark Julian West has found an ‘adoption’ procedure which converts the tilted Schr¨der o tree to the classical Schr¨der tree without changing the number of nodes on any level. o To show that the generating tree for B(T12 ) is isomorphic to the tilted Schr¨der tree, we o study the bar-active and unbar-active spaces in a signed permutation which avoids T12 . We begin by characterizing the bar-active spaces. Lemma 5.3 Fix n ≥ 2 and suppose π ∈ Bn?1 (T12 ). Then the following hold. 13 (9)

(i) If π(n ? 1) is unbarred then the right-most space in π is bar-active and all other spaces in π are bar-inactive. (ii) If π(n ? 1) is barred then the right-most two spaces in π are bar-active and all other spaces in π are bar-inactive. Proof. (i) Since no forbidden pattern ends with its largest entry, the right-most space in π is bar-active. However, if we insert n in any space other than the right-most, then n and π(n ? 1) form a subsequence of type 21, which is forbidden. (ii) Since no forbidden pattern ends with its largest entry, the right-most space in π is bar-active. Similarly, since no forbidden pattern ends with its largest two entries barred, the second space from the right in π is bar-active. Now suppose we insert n in a space which is not one of the right-most two spaces in π. If π(n ? 2) is barred then n, π(n ? 2), and π(n ? 1) form a subsequence of type 321 or 312, both of which are forbidden. If π(n ? 2) is unbarred then n and π(n ? 2) form a subsequence of type 21, which is also forbidden. 2 Next we characterize the unbar-active spaces. Lemma 5.4 Fix n ≥ 2 and suppose π ∈ Bn?1 (T12 ). Let σ denote the (possibly empty) sequence of barred entries at the right end of π. Then the following hold. (i) If σ is empty then the right-most space in π is unbar-active and all other spaces in π are unbar-inactive. (ii) Suppose σ is nonempty. Then a space in π is unbar-active if and only if it is adjacent to at least one entry of σ. Proof. (i) Since no forbidden pattern ends with its largest entry, the right-most space in π is unbar-active. However, if we insert n in any space other than the right-most, then n and π(n ? 1) form a subsequence of type 21, which is forbidden. (ii) This is immediate, since the only forbidden subsequence whose largest entry is unbarred is 21. 2 We conclude the paper by using Lemmas 5.3 and 5.4 to give an isomorphism between the generating tree for B(T12 ) and the tilted Schr¨der tree. o Theorem 5.5 For each signed permutation π ∈ B(T12 ), let g(π) = 2 if the right-most entry of π is unbarred, and let g(π) denote three plus the number of barred entries at the right end of π otherwise. Then the map π → g(π) is an isomorphism of generating trees between the generating tree for B(T12 ) and the tilted Schr¨der generating tree. In particular, o |Bn (21, 21, 321, 312)| = rn (n ≥ 0).

Proof. To begin, observe that g(?) = 2, g(1) = 2, and g(1) = 4, so both trees have the same ?rst two levels, and it is su?cient to show they have the same succession rules. Fix n ≥ 2 and suppose π ∈ Bn?1 (T12 ). We consider two cases. Case One: π(n ? 1) is unbarred, so that g(π) = 2.

14

In view of Lemmas 5.3 and 5.4, the signed permutation π has 2 = g(π) children, one of which is obtained by inserting n at the right end of π and the other of which is obtained by inserting n at the right end of π. By the same Lemmas, the child obtained by inserting n has 2 children and the child obtained by inserting n has 4 children. Case Two: π(n ? 1) is barred, so that g(π) ≥ 4. In view of Lemmas 5.3 and 5.4, the signed permutation π has g(π) children, two of which are obtained by inserting n and g(π) ? 2 of which are obtained by inserting n. By the same Lemmas, both children obtained by inserting n have g(π) + 1 children, and the children obtained by inserting n have 2, 4, 5, . . . , g(π) children. These results correspond with the succession rules for the tilted Schr¨der generating tree, o and the result follows from Theorem 5.2. 2

References
[1] C. Banderier, M. Bousquet-M?lou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyoue Beauchamps. Generating functions for generating trees. Discrete Math., 246:29–55, 2002. [2] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. Permutations avoiding an increasing number of length-increasing forbidden subsequences. Discrete Math. Theor. Comput. Sci., 4(1):31–44, 2000. [3] R. A. Brualdi. Introductory Combinatorics. Pearson Prentice Hall, 4th edition, 2004. [4] E. S. Egge. Restricted colored permutations and Chebyshev polynomials. preprint. [5] S. Gire. Arbres, permutations ` motifs exclus et cartes planaire: quelques probl`mes a e algorithmiques et combinatoires. PhD thesis, Universit? Bordeaux I, 1993. e [6] D. Kremer. Permutations with forbidden subsequences and a generalized Schr¨der o number. Discrete Math., 218:121–130, 2000. [7] T. Mansour and J. West. Avoiding 2-letter signed patterns. S?m. Lothar. Combin., e 49:Article B49a, 2002. [8] H. Prodinger. The kernel method: A collection of examples. S?m. Lothar. Combin., e 50:Article B50f, 2003. [9] R. Simion. Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations. Electron. J. Combin., 7:#R9, 2000. [10] R. P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, 1999. [11] J. West. Generating trees and the Catalan and Schr¨der numbers. Discrete Math., o 146:247–262, 1995. 15

[12] J. West. Generating trees and forbidden subsequences. Discrete Math., 157:363–374, 1996.

16