Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Permutations with Ascending and Descending Blocks"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Permutations with Ascending and Descending Blocks. | Permutations with Ascending and Descending Blocks Jacob Steinhardt jacob.steinhardt@gmail.com Submitted Aug 29 2009 Accepted Jan 4 2010 Published Jan 14 2010 Mathematics Subject Classification 05A05 Abstract We investigate permutations in terms of their cycle structure and descent set. To do this we generalize the classical bijection of Gessel and Reutenauer to deal with permutations that have some ascending and some descending blocks. We then provide the first bijective proofs of some known results. We also extend the work done in 4 by Eriksen Freij and Wastlund who study derangements that descend in blocks of prescribed lengths. In particular we solve some problems posed in 4 and also obtain a new combinatorial sum for counting derangements with ascending and descending blocks. 1 Introduction We consider permutations in terms of their descent set and conjugacy class equivalently cycle structure . Let n be a permutation on 1 . n . An ascent of n is an index i 1 i n such that n i n i 1 . A descent of n is such an index with n i n i 1 . The study of permutations by descent set and cycle structure goes back at least as far as 1993 when Gessel and Reutenauer enumerated them using symmetric functions 5 . In their proof they obtained a bijection from permutations with at most a given descent set to multisets of necklaces with certain properties. By a necklace we mean a directed cycle where the vertices are usually assigned colors or numbers. Multisets of necklaces are usually referred to as ornaments. Figure 1 illustrates these terms. The Gessel-Reutenauer bijection preserves cycle structure. It also forgets other structure that is not so relevant making it easier to study permutations by cycle structure and descent set. We will restate Gessel s and Reutenauer s result to bring it closer to the language of more recent work 6 4 . Choose a1 . ak with a1 ak n and partition 1 . n into consecutive blocks A1 . Ak with ỊAiỊ ai. An a1 . ak -ascending permutation is a .