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

 В комбинаторике числом Стирлинга второго рода из 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 — число Белла.