Grid Classes and the Fibonacci Dichotomy for Restricted Permutations
Grid Classes and the Fibonacci Dichotomy for Restricted Permutations
复制标题
网格类和受限排列的斐波那契二分法
DOI：
--
复制
发表时间：
2006
影响因子：
0.7
通讯作者：
Vincent Vatter
中科院分区：
文献类型：
--
作者：
Sophie Huczynska;Vincent Vatter
我们介绍和表征网格类，这些网格类是其他经过良好研究的排列类别的自然概括。这种表征使我们能够给出斐波那契二分法的新简短证明：置换类中长度$ n $的排列数量至少与$ n $ th fibonacci数字一样大，或者最终是多项式的。
We introduce and characterise grid classes, which are natural generalisations of other well-studied permutation classes. This characterisation allows us to give a new, short proof of the Fibonacci dichotomy: the number of permutations of length $n$ in a permutation class is either at least as large as the $n$th Fibonacci number or is eventually polynomial.