主题
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.net.cn/SchroederNumber.html

主题分类