主題
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.tw/Stanley-WilfConjecture.html

主題分類