Page 1 
Save page Remove page  Previous  1 of 11  Next 

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

This page
All

Restricted Colored Permutations and Chebyshev Polynomials Eric S. Egge Department of Mathematics Carleton College Northfield, MN 55057 USA eggee@member.ams.org July 25, 2006 Abstract Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schr¨oder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation. Keywords: Restricted permutation; restricted involution; patternavoiding permutation; patternavoiding involution; forbidden subsequence; Chebyshev polynomial; colored permutation 1 Introduction and Notation Let c denote a nonnegative integer and let CSn denote the set of permutations of {1, 2, . . . , n}, written in oneline notation, in which each element has an associated color from among the integers 0, 1, . . . , c. We refer to the elements of CSn as colored permutations, and we write the colors of their entries as exponents, as in 233110 and 2010. For each 2 CSn and each i, 1 i n, we write (i) to denote the ith entry of . When c = 0 we identify CSn with the 2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 30B70, 42C05 1
Object Description
Collection Title  Scholarly Publications by Carleton Faculty and Staff 
Journal Title  Discrete Mathematics 
Article Title  Restricted Colored Permutations and Chebyshev Polynomials 
Article Author  Egge, Eric 
Carleton Author 
Egge, Eric 
Department  Mathematics 
Field  Science and Mathematics 
Year  2007 
Volume  307 
Publisher  Elsevier 
File Name  030_EggeEric_RestrictedColoredPermuationsAndChebyshevPolynomials.pdf; 030_EggeEric_RestrictedColoredPermuationsAndChebyshevPolynomials.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  Restricted Colored Permutations and Chebyshev Polynomials Eric S. Egge Department of Mathematics Carleton College Northfield, MN 55057 USA eggee@member.ams.org July 25, 2006 Abstract Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schr¨oder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation. Keywords: Restricted permutation; restricted involution; patternavoiding permutation; patternavoiding involution; forbidden subsequence; Chebyshev polynomial; colored permutation 1 Introduction and Notation Let c denote a nonnegative integer and let CSn denote the set of permutations of {1, 2, . . . , n}, written in oneline notation, in which each element has an associated color from among the integers 0, 1, . . . , c. We refer to the elements of CSn as colored permutations, and we write the colors of their entries as exponents, as in 233110 and 2010. For each 2 CSn and each i, 1 i n, we write (i) to denote the ith entry of . When c = 0 we identify CSn with the 2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 30B70, 42C05 1 