主題
Search

施羅德數


SchroderNumber

施羅德數 S_n 是指在笛卡爾平面上,從 (0, 0) 出發,到 (n,n) 結束,不經過直線 y=x 上方區域,且僅由步長 (0, 1)(向上)、(1, 0)(向右)和 (1, 1)(向右上方)組成的格路數量。生成 S_1S_2S_3 的路徑圖示如上所示。

數字 S_n 由以下遞推關係給出

 S_n=S_(n-1)+sum_(k=0)^(n-1)S_kS_(n-1-k),
(1)

其中 S_0=1,且前幾項為 2, 6, 22, 90, ... (OEIS A006318)。S_(10^n) 的十進位制位數(對於 n=0, 1, ...)為 1, 7, 74, 761, 7650, 76548, 765543, 7655504, ... (OEIS A114472),其中位數接近 log_(10)(3+2sqrt(2))=0.765551... 的位數 (OEIS A114491)。

它們具有生成函式

 G(x)=(1-x-sqrt(1-6x+x^2))/(2x),
(2)

其滿足

 (1-x)G(x)-x[G(x)]^2=1
(3)

並具有閉合形式解

S_n=2_2F_1(-n+1,n+2;2;-1)
(4)
=-1/2C_(n+1)^((-1/2))(3)
(5)
=1/2[-P_(n-1)(3)+6P_n(3)-P_(n+1)(3)],
(6)

其中 _2F_1(a,b;c;z)超幾何函式C_n^((k))(x)Gegenbauer 多項式P_n(z)Legendre 多項式,且 (5) 式對於 n>1 成立。

施羅德數與 Delannoy 數的關係,正如 Catalan 數二項式係數的關係一樣。


另請參閱

二項式係數, Catalan 數, Delannoy 數, 格路, Motzkin 數, p-優良路徑, 超 Catalan 數

使用 探索

參考文獻

Bonin, J.; Shapiro, L.; and Simion, R. "格路組合統計中出現的施羅德數的 q-模擬。" J. Stat. Planning Inference 34, 35-55, 1993.Moser, L. and Zayachkowski, W. "帶對角線步長的格路。" Scripta Math. 26, 223-229, 1963.Pergola, E. and Sulanke, R. A. "施羅德三角形、路徑和平行四邊形多聯骨牌。" J. Integer Sequences 1, No. 98.1.7, 1998. http://www.math.uwaterloo.ca/JIS/VOL1/PergolaSulanke/.Rogers, D. G. "一個施羅德三角形。" Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference. New York: Springer-Verlag, pp. 175-196, 1977.Rogers, D. G. and Shapiro, L. "涉及施羅德數的一些對應關係。" Combinatorial Mathematics: Proceedings of the International Conference, Canberra, 1977. New York: Springer-Verlag, pp. 267-276, 1978.Schröder, E. "Vier kombinatorische Probleme." Z. Math. Phys. 15, 361-376, 1870.Sloane, N. J. A. Sequences A006318/M1659, A114472, and A114491 in "整數數列線上大全"。Stanley, R. P. "喜帕恰斯、普盧塔克、施羅德、霍夫。" Amer. Math. Monthly 104, 344-350, 1997.Sulanke, R. A. "關於施羅德路徑的雙射遞推關係。" Electronic J. Combinatorics 5, No. 1, R47, 1-11, 1998. http://www.combinatorics.org/Volume_5/Abstracts/v5i1r47.html.

在 中被引用

施羅德數

請引用為

Weisstein, Eric W. “施羅德數。” 來自 Web 資源。 https://mathworld.tw/SchroederNumber.html

主題分類