tailieunhanh - Báo cáo toán học: "Counting segmented permutations using bicoloured Dyck paths"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Counting segmented permutations using bicoloured Dyck paths. | Counting segmented permutations using bicoloured Dyck paths Anders Claesson Division of Mathematics Department of Chemistry and Biomedical Sciences University of Kalmar Sweden Submitted Jun 14 2005 Accepted Aug 9 2005 Published Aug 17 2005 Mathematics Subject Classifications 05A05 05A15 Abstract A bicoloured Dyck path is a Dyck path in which each up-step is assigned one of two colours say red and green. We say that a permutation K is ơ-segmented if every occurrence o of Ơ in K is a segment-occurrence . o is a contiguous subword in k . We show combinatorially the following results The 132-segmented permutations of length n with k occurrences of 132 are in one-to-one correspondence with bicoloured Dyck paths of length 2n 4k with k red up-steps. Similarly the 123-segmented permutations of length n with k occurrences of 123 are in one-to-one correspondence with bicoloured Dyck paths of length 2n 4k with k red up-steps each of height less than 2. We enumerate the permutations above by enumerating the corresponding bicoloured Dyck paths. More generally we present a bivariate generating function for the number of bicoloured Dyck paths of length 2n with k red up-steps each of height less than h. This generating function is expressed in terms of Chebyshev polynomials of the second kind. 1 Introduction Let Sn be the set of permutation of n 1 2 ng. Let w 2 Sn and Ơ 2 Sk with k n. An occurrence of Ơ in w is a subword o of length k in w such that o and Ơ are in same relative order. In this context Ơ is called a pattern. For example an occurrence of the pattern 132 in w is a subword w i w j w k such that w i w k w j so 253 is an occurrence of 132 in 42513. A permutation w that does not contain any occurrence of Ơ is said to avoid Ơ. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R39 1 It is relatively easy to show that numb er of permutations of n avoiding a pattern of length 3 is the Catalan number Cn 2n n 1 e-g- see 9 or 5 . In contrast to count the