主题
Search

第二类斯特林数

下载 Mathematica Notebook 图标下载 Wolfram Notebook

将一个包含 n 个元素的集合划分为 m 个非空集合（即，m 集块）的方法数，也称为斯特林集数。例如，集合 {1,2,3} 可以用一种方式划分为三个子集：{{1},{2},{3}}；用三种方式划分为两个子集：{{1,2},{3}}，{{1,3},{2}}，和 {{1},{2,3}}；以及用一种方式划分为一个子集：{{1,2,3}}。

第二类斯特林数有多种表示法，包括 S(n,m) (Riordan 1980, Roman 1984), S_n^((m)) (Fort 1948; Abramowitz and Stegun 1972, p. 822), S_n^m (Jordan 1965), s_n^((m)), S_2(n,m), 或 Knuth 的符号 {n; m} (Graham et al. 1994; Knuth 1997, p. 65)。Abramowitz 和 Stegun (1972, p. 822) 总结了各种符号约定，这些约定可能有点令人困惑。第二类斯特林数在 Wolfram 语言 中实现为StirlingS2[n, m]，并表示为 S_n^((m))。

三个元素的第二类斯特林数是

S(3,1)=1
(1)
S(3,2)=3
(2)
S(3,3)=1.
(3)

由于一个包含 n 个元素的集合只能以一种方式划分为 1 个或 n 个子集，

S(n,1)=S(n,n)=1.
(4)

其他特殊情况包括

S(n,0)=delta_(n0)
(5)
S(n,2)=2^(n-1)-1
(6)
S(n,3)=1/6(3^n-3·2^n+3)
(7)
S(n,n-1)=(n; 2).
(8)

第二类斯特林数三角形是

1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 1 31 90 65 15 1
(9)

(OEIS A008277)，其第 n 行对应于 贝尔多项式 phi_n(x) 的系数。

第二类斯特林数可以通过以下求和公式计算

S(n,k)=1/(k!)sum_(i=0)^k(-1)^i(k; i)(k-i)^n,
(10)

其中 (n; k) 是一个二项式系数，或者使用生成函数

x^n=sum_(m=0)^(n)S(n,m)(x)_m
(11)
=sum_(m=0)^(n)S(n,m)x(x-1)...(x-m+1),
(12)

其中 (x)_m 是降阶乘 (Roman 1984, pp. 60 和 101)，

sum_(n=k)^inftyS(n,k)(x^n)/(n!)=1/(k!)(e^x-1)^k,
(13)

以及

sum_(n=1)^(infty)S(n,k)x^n=sum_(n=k)^(infty)S(n,k)x^n
(14)
=(x^k)/((1-x)(1-2x)...(1-kx))
(15)
=((-1)^k)/(((x-1)/x)_k)
(16)

对于 z<1/m (Abramowitz 和 Stegun 1972, p. 824; Stanley 1997, p. 57)，其中 (x)_m 是一个 波赫哈默尔符号。另一个生成函数由下式给出

sum_(k=1)^nS(n,k)(k-1)!z^k=(-1)^nLi_(1-n)(1+1/z)
(17)

对于 n>=2，其中 Li_n(z) 是多对数函数。

第二类斯特林数通过 Dobiński 公式 与 泊松分布 密切相关

B_n(x)=sum_(k=0)^nx^kS(n,k)
(18)

其中 B_n(x) 是一个 贝尔多项式。

StirlingNumberSecondKind

以上图表 (Dickau) 说明了第二类斯特林数 S(n,m) 对于 n=3 和 4 的定义。第二类斯特林数遵循以下递推关系

S(n,k)=S(n-1,k-1)+kS(n-1,k)
(19)
S(n,k)=sum_(m=k)^(n)k^(n-m)S(m-1,k-1).
(20)

第一类斯特林数 s(n,m) 与第二类斯特林数 S(n,m) 相关联。例如，矩阵 (s)_(i,j) 和 (S)_(i,j) 互为逆矩阵，其中 (A)_(ij) 表示第 (i,j) 项为 aAi,j) 的矩阵，对于 i,j=1, ..., n (G. Helms，私人通讯，2006 年 4 月 28 日)。

其他公式包括

s(n,i)=sum_(k=i)^nsum_(j=0)^ks(n,k)s(k,j)S(j,i)
(21)
S(n,i)=sum_(k=i)^nsum_(j=0)^kS(n,k)S(k,j)s(j,i)
(22)

(Roman 1984, p. 67)，以及

S(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)s(k-m+n,k)
(23)
s(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)S(k-m+n,k)
(24)
sum_(l=0)^(max(k,j)+1)s(l,j)S(k,1)=delta_(jk)
(25)
sum_(l=0)^(max(k,j)+1)s(k,l)S(l,j)=delta_(jm).
(26)

涉及第二类斯特林数的恒等式由下式给出

sum_(m=1)^n(-1)^m(m-1)!S(n,m)=0
(27)
sum_(k=0)^nk!(m+1; k+1)S(n,k)=H_(m,-n),
(28)

其中 H_(n,r) 是一个广义调和数，并且

f(m,n)=sum_(k=1)^(infty)k^n(m/(m+1))^k
(29)
=(m+1)sum_(k=1)^(n)k!S(n,k)m^k.
(30)

序列 f(1,n) 由 2, 6, 26, 150, 1082, 9366, 94586, 1091670, ... (OEIS A000629; Konhauser et al. 1996, p. 174) 给出，并且最后一位数字只能是 0、2 或 6 (Riskin 1995)。K. A. Penson（私人通讯，2002 年 4 月 10 日）提出的另一个有趣的恒等式由下式给出

sum_(k=0)^inftyk^n[k+1-(Gamma(k+2,1))/(Gamma(k+1))]=sum_(k=0)^n(S(n,k))/(k+2)
(31)

对于 n=0, 1, ..., 其中 Gamma(a,x) 是一个不完全伽玛函数，Gamma(x) 是一个 伽玛函数，并且 k^n 在 k,n=0 时取值为 1。

第二类斯特林数也出现在涉及微分算子 theta=zd/dz 的恒等式中。

另请参阅

贝尔数, 贝尔多项式, 组合锁, 互补贝尔数, 微分算子, Lengyel 常数, 最小覆盖, 泊松分布, 第一类斯特林数, 斯特林多项式, 斯特林变换

相关的 Wolfram 网站

http://functions.wolfram.com/IntegerFunctions/StirlingS2/

使用 Wolfram|Alpha 探索

参考文献

Abramowitz, M. 和 Stegun, I. A. (编). "第二类斯特林数." §24.1.4 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. 纽约: Dover, pp. 824-825, 1972.Butzer, P. L. 和 Hauss, M. "第一类和第二类斯特林函数；一些新的应用." Israel Mathematical Conference Proceedings: Approximation, Interpolation, and Summability, in Honor of Amnon Jakimovski on his Sixty-Fifth Birthday (编 S. Baron 和 D. Leviatan). Ramat Gan, Israel: IMCP, pp. 89-108, 1991.Carlitz, L. "关于 Nörlund 的 [原文如此] 多项式 B_n^((z))." Proc. Amer. Math. Soc. 11, 452-455, 1960.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. 多德雷赫特，荷兰: Reidel, 1974.Conway, J. H. 和 Guy, R. K. In The Book of Numbers. 纽约: Springer-Verlag, pp. 91-92, 1996.Dickau, R. M. "第二类斯特林数." http://mathforum.org/advanced/robertd/stirling2.html.Dickau, R. "可视化组合枚举." Mathematica in Educ. Res. 8, 11-18, 1999.Fort, T. Finite Differences and Difference Equations in the Real Domain. 牛津，英格兰: Clarendon Press, 1948.Gould, H. W. "斯特林数表示问题." Proc. Amer. Math. Soc. 11, 447-451, 1960.Graham, R. L.; Knuth, D. E.; 和 Patashnik, O. "斯特林数." §6.1 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. 雷丁，马萨诸塞州: Addison-Wesley, pp. 257-267, 1994.Jordan, C. Calculus of Finite Differences, 3rd ed. 纽约: Chelsea, 1965.Knuth, D. E. "关于符号的两个注释." Amer. Math. Monthly 99, 403-422, 1992.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. 雷丁，马萨诸塞州: Addison-Wesley, 1997.Konhauser, J. D. E.; Velleman, D.; 和 Wagon, S. Which Way Did the Bicycle Go? And Other Intriguing Mathematical Mysteries. 华盛顿特区: Math. Assoc. Amer., p. 174, 1996.Riordan, J. Combinatorial Identities. 纽约: Wiley, 1979.Riordan, J. An Introduction to Combinatorial Analysis. 纽约: Wiley, 1980.Riskin, A. "问题 10231." Amer. Math. Monthly 102, 175-176, 1995.Roman, S. The Umbral Calculus. 纽约: Academic Press, pp. 59-63, 1984.Sloane, N. J. A. 序列 A000629 和 A008277 in "整数序列在线百科全书."Stanley, R. P. Enumerative Combinatorics, Vol. 1. 剑桥，英格兰: Cambridge University Press, 1997.Stirling, J. Methodus differentialis, sive tractatus de summation et interpolation serierum infinitarium. 伦敦, 1730. 英文翻译由 Holliday, J. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series. 1749.Young, P. T. "伯努利数、欧拉数和斯特林数的同余式." J. Number Th. 78, 204-227, 1999.

在 Wolfram|Alpha 中引用

第二类斯特林数

请引用为

Weisstein, Eric W. "第二类斯特林数." 来自 MathWorld--Wolfram Web 资源. https://mathworld.net.cn/StirlingNumberoftheSecondKind.html

主题分类