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: Counting words by number of occurrences of some patterns. | Counting words by number of occurrences of some patterns Zhicheng Gao Andrew MacFie Daniel Panario School of Mathematics and Statistics Carleton University Ottawa Canada Submitted Dec 1 2010 Accepted Jun 28 2011 Published Jul 15 2011 Mathematics Subject Classification 05A05 Abstract We give asymptotic expressions for the number of words containing a given number of occurrences of a pattern for two families of patterns with two parameters each. One is the family of classical patterns in the form 22 212 22 and the other is a family of partially ordered patterns. The asymptotic expressions are in terms of the number of solutions to an equation and for one subfamily this quantity is the number of integer partitions into qth order binomial coefficients. Keywords classical pattern occurrence asymptotics word partially ordered pattern This paper is DEDICATED TO THE MEMORY OF Philippe Flajolet 1948-2011 . 1 Introduction Let k 1 2 . k be a totally ordered alphabet on k letters. A k-ary word of length n is an element of k n. Given a word w W1 wn G k n the reduction of w denoted n w is the word obtained by replacing the ith smallest letters of w with i s for all i. For example n 46632 34421. Given words Ơ of length n and T n T of length l t is called the pattern an occurrence of T in Ơ is a sequence of indices 1 i1 i n and the corresponding letter subsequence Ơi1 ơil that satisfy certain conditions related to T classical patterns zgao@ THE electronic journal of combinatorics 18 2011 P143 1 require n aix ail T and subword patterns are classical patterns that require i-1 1 1 il. If there are no occurrences of T in a then a is said to avoid the pattern T. As in 12 a partially ordered pattern POP is one in which not all letters are comparable. The letters in a POP are from a partially ordered alphabet letters shown with the same number of primes are comparable to each other . 1 and 2 while letters shown .
