On the number of permutations avoiding a given pattern

Let sigma is an element of S-k and tau is an element of S-n be permutations . We say tau contains sigma if there exist 1 less than or equal to x(1) < x (2)< ... <x(k) less than or equal to n such that tau(x(i)) < tau (x(j)) if and only if sigma(i) < sigma(j). If tau does not contain sigma we say tau a voids sigma. Let F(n, sigma)= \{tau is an element of S-n / tau avoids sigma } \. Stanley and Wilf conjectured that for any sigma is an element of S-k t here exists a constant c=c(sigma) such that F(n, sigma) less than or equal to c(n) for all n. Here we prove the following weaker statement: For every fixed sigma is an element of S-k, F(n,sigma) less than or equal to c(n gamm a*(n)) , where c= c(sigma) and gamma*(n) is an extremely slow growing funct ion, related to the Ackermann hierarchy. (C) 2000 Academic Press.