On Square-Free Permutations
On Square-Free Permutations
复制标题
关于无平方排列
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Valyuzhenich
中科院分区：
文献类型：
--
作者：
S. Avgustinovich;S. Kitaev;A. Pyatkin;A. Valyuzhenich
一个置换是无平方的，如果它不包含两个长度大于1的连续因子，并且在简化形式（如模式）中重合。我们证明了长度为n的无平方置换的个数为nn（1？“n）其中“n！0当n！1.一个长度为n的置换对于正方形来说是至关重要的，如果它避免了正方形，但是它向右延伸到一个长度为n+1的置换，包含一个正方形。一个置换是最大的关于广场，如果这两个置换和它的逆是至关重要的关于广场。我们证明了存在至关重要的排列相对于任何长度至少为7的平方，并存在最大排列相对于奇数长度的平方8 k +1; 8 k +5; 8 k +7为k 1。
A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1?"n) where "n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respect to squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.