主题
Search

Stanley-Wilf 猜想

Stanley 和 Wilf 猜想 (Bona 1997, Arratia 1999)，对于每个 排列模式 sigma，存在一个常数 c(sigma)<infty 使得对于所有 n，

F(n,sigma)<=[c(sigma)]^n.

一个相关的猜想指出，对于每个 sigma，极限

lim_(n->infty)[F(n,sigma)]^(1/n)

存在且是有限的。

Arratia (1999) 表明这两个猜想是等价的。该猜想由 Marcus 和 Tardos (2004) 证明。

另请参阅

排列模式

使用 探索

参考文献

Alon, N. and Friedgut, E. "关于避免给定模式的排列数量。" J. Combin. Th. Ser. A. 89, 133-140, 2000.Arratia, R. "关于避免给定模式的排列数量的 Stanley-Wilf 猜想。" Electronic J. Combinatorics 6, No. 1, N1, 1-4, 1999. http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html.Bona, M. "具有子序列条件的排列的精确和渐近计数。" Ph.D. 博士论文。 Cambridge, MA: MIT, 1997.Bona, M. "所有分层模式的 Stanley 和 Wilf 猜想的解。" J. Combin. Th. Ser. A 85, 96-104, 1999.Marcus, A. and Tardos, G. "排除的排列矩阵和 Stanley-Wilf 猜想。" J. Combin. Th. Ser. A. 107, 153-160, 2004.Wilf, H. "关于交叉数和一些未解决的问题。" 在 组合数学、几何学和概率论：向 Paul Erdős 致敬。1993 年 3 月在剑桥三一学院举行的纪念 Erdős 80 岁生日会议论文集 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.

在 上被引用

Stanley-Wilf 猜想

请引用为

Weisstein, Eric W. "Stanley-Wilf 猜想。" 来自 ——Wolfram 网络资源。 https://mathworld.net.cn/Stanley-WilfConjecture.html

主题分类