Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: On growth rates of closed permutation classes | On growth rates of closed permutation classes Tomás Kaiser1 3 and Martin Klazar2 3 Submitted Apr 26 2002 Accepted Mar 17 2003 Published Apr 10 2003 MR Subject Classifications 05A16 05A05 Abstract A class of permutations n is called closed if n c ơ G n implies n G n where the relation c is the natural containment of permutations. Let nn be the set of all permutations of 1 2 . n belonging to n. We investigate the counting functions n nn of closed classes. Our main result says that if nn 2n-1 for at least one n 1 then there is a unique k 1 such that Fi.c nn Fn k nc holds for all n 1 with a constant c 0. Here Fn k are the generalized Fibonacci numbers which grow like powers of the largest positive root of xk xk-1 1. We characterize also the constant and the polynomial growth of closed permutation classes and give two more results on these. 1 Introduction A permutation Ơ b1 b2 . bn of n 1 2 . n contains a permutation n a1 a2 . ak of k in symbols ơ D n if Ơ has a not necessarily consecutive subsequence of length k whose terms induce the same order pattern as n. For example 3 5 4 2 1 7 8 6 9 contains 2 1 3 as . 5 . 1 . 6 . or as . 4 2 . . . 9 but it does not contain 3 1 2 . Let f n n be the number of the permutations of n not containing n. The following conjecture was made by R. P. Stanley and H. S. Wilf it appeared first in print in Bona 11 12 13 . The Stanley-Wilf conjecture. For every permutation n there is a constant c 0 such that f n n cn for all n 1. 1Department of Mathematics University of West Bohemia Univerzitni 8 306 14 Plzen Czech Republic e-mail kaisert@kma.zcu.cz. Corresponding author. 2Department of Applied Mathematics Charles University Malostranske namesti 25 118 00 Praha 1 Czech Republic e-mail klazar@kam.mff.cuni.cz. 3Institute for Theoretical Computer Science ITI Charles University Praha Czech Republic. Supported by project LN00A056 of the Czech Ministry of Education. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2003 R10 1 It is known to hold for all n .