Числа Стирлинга второго рода

 В комбинаторике числом Стирлинга второго рода из n поk, обозначаемым S(n,k) или{nk}, называется количествонеупорядоченных разбиений n-элементного множества на kнепустых подмножеств.

Рекуррентныепредставления


 Числа Стирлинга второго рода удовлетворяют рекуррентным соотношениям:

 1) S(n,k)=S(n1,k1)+kS(n1,k) для 0<kn.
 2) S(n,k)=j=0n1(n1j)S(j,k1).
 при естественных начальных условиях S(0,0)=1, S(n,0)=0 приn>0 и S(j,k)=0 при k>j.

Явнаяформула



S(n,k)=1k!j=0k(1)k+j(kj)jn.

Таблица значений при0n,k9


n\{k0123456789
01
101
2011
30131
401761
5011525101
601319065151
70163301350140211
80112796617011050266281
9012553025777069512646462361

Свойства



  • xn=k=0nS(n,k)(x)k, где (x)k=x(x1)(xk+1).
  • S(m,n)=i=n1m1(m1i)S(i,n1)
  • m=0nS(n,m)=Bn — число Белла.