Using functional equations to enumerate 1324-avoiding permutations
Using functional equations to enumerate 1324-avoiding permutations
复制标题
DOI：
10.1016/j.aam.2014.01.006
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Fredrik Johansson;Brian Nakamura
中科院分区：
文献类型：
--
作者：
Fredrik Johansson;Brian Nakamura
我们考虑了对模式1324正好出现r次的排列进行枚举的问题，并针对这种一般情况以及对于模式避免(r=0)的情况推导出函数方程。该函数方程导致了一种新的算法，用于枚举避免1324的长度n排列。这种方法被用来枚举直到n=31的1324个逃避者。我们还将这些函数方程推广到考虑反演次数的情况，并推导出类似的算法。
We consider the problem of enumerating permutations with exactly r occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance (r= 0) case. The functional equations lead to a new algorithm for enumerating length n permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to n= 31. We also extend those functional equations to account for the number of inversions and derive analogous algorithms.