Page 1 
Save page Remove page  Previous  1 of 12  Next 

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution
All (PDF)

This page
All

Discrete Mathematics 306 (2006) 552 – 563 www.elsevier.com/locate/disc Restricted signed permutations counted by the Schröder numbers Eric S. Egge Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057, USA Received 1 September 2005; received in revised form 8 December 2005; accepted 25 January 2006 Abstract Gire, West, and Kremer have found ten classes of restricted permutations counted by the large Schröder numbers, no two of which are triviallyWilfequivalent. In this paper we enumerate eleven classes of restricted signed permutations counted by the large Schröder numbers, no two of which are triviallyWilfequivalent.We obtain five of these enumerations by elementary methods, five by displaying isomorphisms with the classical Schröder generating tree, and one by giving an isomorphism with a new Schröder generating tree. When combined with a result of Egge and a computer search, this completes the classification of restricted signed permutations counted by the large Schröder numbers in which the set of restrictions consists of two patterns of length 2 and two of length 3. © 2006 Published by Elsevier B.V. Keywords: Restricted permutation; Patternavoiding permutation; Forbidden subsequence; Schröder number; Signed permutation; Generating tree 1. Introduction and notation Let Bn denote the set of permutations of {1, 2, . . . , n}, written in oneline 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 (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 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 patternavoiding 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. Email address: eggee@member.ams.org. 0012365X/$  see front matter © 2006 Published by Elsevier B.V. doi:10.1016/j.disc.2006.01.013
Object Description
Collection Title  Scholarly Publications by Carleton Faculty and Staff 
Journal Title  Discrete Mathematics 
Article Title  Restricted Signed Permutations Counted by the Schroder Numbers 
Article Author  Egge, Eric 
Carleton Author 
Egge, Eric 
Department  Mathematics 
Field  Science and Mathematics 
Year  2006 
Volume  306 
Publisher  Elsevier 
File Name  021_EggeEric_RestrictedSignedPermutationsCountedByTheSchroderNumbers.pdf; 021_EggeEric_RestrictedSignedPermutationsCountedByTheSchroderNumbers.pdf 
Rights Management  This document is authorized for selfarchiving and distribution online by the author(s) and is free for use by researchers. 
RoMEO Color  RoMEO_Color_Green 
Preprint Archiving  Yes (with link to journal home page) 
Postprint Archiving  Yes 
Publisher PDF Archiving  No 
Paid OA Option  Yes 
Contributing Organization  Carleton College 
Type  Text 
Format  application/pdf 
Language  English 
Description
Article Title  Page 1 
FullText  Discrete Mathematics 306 (2006) 552 – 563 www.elsevier.com/locate/disc Restricted signed permutations counted by the Schröder numbers Eric S. Egge Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057, USA Received 1 September 2005; received in revised form 8 December 2005; accepted 25 January 2006 Abstract Gire, West, and Kremer have found ten classes of restricted permutations counted by the large Schröder numbers, no two of which are triviallyWilfequivalent. In this paper we enumerate eleven classes of restricted signed permutations counted by the large Schröder numbers, no two of which are triviallyWilfequivalent.We obtain five of these enumerations by elementary methods, five by displaying isomorphisms with the classical Schröder generating tree, and one by giving an isomorphism with a new Schröder generating tree. When combined with a result of Egge and a computer search, this completes the classification of restricted signed permutations counted by the large Schröder numbers in which the set of restrictions consists of two patterns of length 2 and two of length 3. © 2006 Published by Elsevier B.V. Keywords: Restricted permutation; Patternavoiding permutation; Forbidden subsequence; Schröder number; Signed permutation; Generating tree 1. Introduction and notation Let Bn denote the set of permutations of {1, 2, . . . , n}, written in oneline 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 (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 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 patternavoiding 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. Email address: eggee@member.ams.org. 0012365X/$  see front matter © 2006 Published by Elsevier B.V. doi:10.1016/j.disc.2006.01.013 