On Growth Rates of Closed Permutation Classes
On Growth Rates of Closed Permutation Classes
复制标题
关于封闭排列类的增长率
DOI：
--
复制
发表时间：
2003
影响因子：
0.7
通讯作者：
Martin Klazar
中科院分区：
文献类型：
--
作者：
Tomás Kaiser;Martin Klazar
如果2蕴涵2，则称为闭置换，其中关系是置换的自然包容。设n为1,2，…的所有排列的集合n .属于；我们研究了计数函数n7 ！b|的封闭课程。我们的主要结果是，如果|n|。这里Fn，k是广义的斐波那契数，它们像x k x k1···1的最大正根的幂一样增长。我们还刻画了闭置换类的常数和多项式增长，并给出了另外两个结果。
A class of permutations is called closed if 2 implies 2 , where the relation is the natural containment of permutations. Let n be the set of all permutations of 1, 2 ,...,n belonging to . We investigate the counting functions n 7! |n| of closed classes. Our main result says that if |n| 0. Here Fn,k are the generalized Fibonacci numbers which grow like powers of the largest positive root of x k x k 1 ··· 1. We characterize also the constant and the polynomial growth of closed permutation classes and give two more results on these.