On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern
On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern
复制标题
关于避免给定模式的排列数的斯坦利-威尔夫猜想
DOI：
--
复制
发表时间：
1999
影响因子：
0.7
通讯作者：
R. Arratia
中科院分区：
文献类型：
--
作者：
R. Arratia
考虑，对于{\cal S}_k$中的一个排列$\sigma \, ${\cal S}_n$中避免$\sigma$作为子模式的排列$F(n,\sigma)$的个数。Stanley和Wilf的猜想是，对于每一个$\sigma$存在一个常数$c（\sigma）。我们还讨论了$n$-排列，其中包含{\cal S}_k$中的所有$\sigma \作为子模式。我们证明了这可以用$n=k^2$来实现，我们猜想渐近的$n \sim (k/e)^2$是可实现的最佳值，并且我们提出了Noga Alon关于$n \sim (k/2)^2$是随机排列的阈值的猜想。
Consider, for a permutation $\sigma \in {\cal S}_k$, the number $F(n,\sigma)$ of permutations in ${\cal S}_n$ which avoid $\sigma$ as a subpattern. The conjecture of Stanley and Wilf is that for every $\sigma$ there is a constant $c(\sigma) We also discuss $n$-permutations, containing all $\sigma \in {\cal S}_k$ as subpatterns. We prove that this can be achieved with $n=k^2$, we conjecture that asymptotically $n \sim (k/e)^2$ is the best achievable, and we present Noga Alon's conjecture that $n \sim (k/2)^2$ is the threshold for random permutations.