Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515539 | Journal of Combinatorial Theory, Series A | 2005 | 13 Pages |
Abstract
We show the first known example for a pattern q for which L(q)=limnââSn(q)n is not an integer, where Sn(q) denotes the number of permutations of length n avoiding the pattern q. We find the exact value of the limit and show that it is irrational, but algebraic. Then we generalize our results to an infinite sequence of patterns. We provide further generalizations that start explaining why certain patterns are easier to avoid than others. Finally, we show that if q is a layered pattern of length k, then L(q)⩾(k-1)2 holds.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Miklós Bóna,