Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. | On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern Richard Arratia Department of Mathematics University of Southern California Los Angeles CA 90089-1113 email rarratia@ Submitted July 27 1999 Accepted August 25 1999. Abstract. Consider for a permutation Ơ 2 Sk the number F n ơ of permutations in Sn which avoid Ơ as a subpattern. The conjecture of Stanley and Wilf is that for every Ơ there is a constant c ơ 1 such that for all n F n ơ c ơ n. All the recent work on this problem also mentions the stronger conjecture that for every Ơ the limit of F n ơ 1 n exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent with a simple argument involving subadditivity. We also discuss n-permutations containing all Ơ 2 Sk as subpatterns. We prove that this can be achieved with n k we conjecture that asymptotically n k e 2 is the best achievable and we present Noga Alon s conjecture that n k 2 2 is the threshold for random permutations. Mathematics Subject Classification 05A05 05A16. 1. Introduction Consider for a permutation Ơ 2 Sk the set A n ơ of permutations T 2 Sn which avoid Ơ as a subpattern and its cardinality F n ơ A n ơ . Recall that t contains ơ as a subpattern means that there exist 1 X1 x2 xk n such that for 1 i j k 1 T Xi T Xj if and only if ơ i ơ j . An outstanding conjecture is that for every Ơ there is a finite constant c ơ such that for all n F n ơ c ơ n. In the 1997 . thesis of Bóna 2 supervised by The author thanks Noga Alon Béla Bollobas and Miklos Bona for discussions of this problem. 1 2 THE ELECTRONIC JOURNAL OF COMBINATORICS 6 1999 N1 Stanley this conjecture is attributed to Wilf and Stanley oral communication from 1990. All the recent work on this problem also mentions the stronger conjecture that for every Ơ the limit of F n ơ ĩ n exists and is finite. According to Wilf private communication 1999 the original conjecture was of this latter form. In this .
