tailieunhanh - Báo cáo toán học: "Counting 1324-avoiding Permutations"

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í toán học quốc tế đề tài: Counting 1324-avoiding Permutations | Counting 1324-avoiding Permutations Darko Marinov Rados Radoicic Laboratory for Computer Science Department of Mathematics Massachusetts Institute of Technology Massachusetts Institute of Technology Cambridge MA 02139 USA Cambridge MA 02139 USA marinov@ rados@ Submitted Apr 23 2003 Accepted May 23 2003 Published May 29 2003 MR Subject Classifications 05A05 05A15 Abstract We consider permutations that avoid the pattern 1324. By studying the generating tree for such permutations we obtain a recurrence formula for their number. A computer program provides data for the number of 1324-avoiding permutations of length up to 20. 1 Introduction Let Sn denote the set of all permutations of length n. A permutation n p1 p2 . pn E Sn contains a pattern T t1 t2 . tk E Sk if there is a sequence 1 it1 it2 itk n such that pi1 pi2 pik. A permutation n avoids a pattern T in other words n is T-avoiding if n does not contain T. We write Sn T for the set of all T-avoiding permutations of length n and sn T for the cardinality of Sn T . Patterns T1 and T2 are Wilf-equivalent if sn n sn T2 Wil02 . A permutation n is fl T2 . Tn -avoiding if n does not contain any of the patterns from the set. It is a natural and easy-looking question to ask for the exact formula for sn T . However this problem turns out to be very difficult. Although a lot of results on this and related problems have been discovered in the last thirty years exact answers are only known in a few cases. For all patterns T of length 3 sn T Cn Knu73 where Cn n ĩỢn is the n-th Catalan number a classical sequence Sta99 . When T is of length 4 it has been shown that the only essentially different patterns are 1234 1342 and 1324 all other patterns of length 4 are Wilf-equivalent to one of these three Sta94 Sta96 BW00 . Regev Reg81 showed that sn 1234 asymptotically equals cn where c is a constant given by a multiple integral. Gessel Ges90 later used theory of symmetric functions to give a generating function