Stanley-Wilf limits are typically exponential
Stanley-Wilf limits are typically exponential
复制标题
Stanley-Wilf 极限通常是指数级的
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Fox
中科院分区：
文献类型：
--
作者：
J. Fox
对于一个排列$pi$，设$S_{n}（pi）$是在$n$个字母上避开$pi$的排列数。Marcus和Tardos证明了著名的Stanley-Wilf猜想$L（pi）= lim_{n o infty} S_n（pi）^{1/n}$存在且有限。在数值证据的支持下，多年来许多研究人员已经证明，对于$k$个字母上的每个排列$pi$，$L（pi）=Theta（k^2）$。我们反驳了这个猜想，表明$L（pi）=2^{k^{Theta（1）}}$几乎所有的排列$pi$上$k$字母。
For a permutation $pi$, let $S_{n}(pi)$ be the number of permutations on $n$ letters avoiding $pi$. Marcus and Tardos proved the celebrated Stanley-Wilf conjecture that $L(pi)= lim_{n o infty} S_n(pi)^{1/n}$ exists and is finite. Backed by numerical evidence, it has been conjectured by many researchers over the years that $L(pi)=Theta(k^2)$ for every permutation $pi$ on $k$ letters. We disprove this conjecture, showing that $L(pi)=2^{k^{Theta(1)}}$ for almost all permutations $pi$ on $k$ letters.