WikiSort.ru - Не сортированное

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

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

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

1) ${\displaystyle S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)}$ для ${\displaystyle 0<k\leq n}$ .

2) ${\displaystyle S(n,k)=\sum \limits _{j=0}^{n-1}{\binom {n-1}{j}}S(j,k-1)}$ .

при естественных начальных условиях ${\displaystyle S(0,0)=1}$ , ${\displaystyle S(n,0)=0}$ при ${\displaystyle n>0}$ и ${\displaystyle S(j,k)=0}$ при ${\displaystyle k>j}$ .

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

${\displaystyle S(n,k)={\frac {1}{k!}}\sum \limits _{j=0}^{k}(-1)^{k+j}{\binom {k}{j}}j^{n}.}$

Свойства

• ${\displaystyle x^{n}=\sum _{k=0}^{n}S(n,k)\cdot (x)_{k},}$ где ${\displaystyle (x)_{k}=x(x-1)\cdots (x-k+1).}$
• ${\displaystyle S(m,n)=\sum _{i=n-1}^{m-1}{\binom {m-1}{i}}\,S(i,n-1)}$
• ${\displaystyle \sum _{m=0}^{n}S(n,m)=B_{n}}$ — число Белла.

См. также

• Число Стирлинга первого рода
• Число Белла

Ссылки

Имеется викиучебник по теме
«Программное вычисление чисел Стирлинга второго рода»

• Weisstein, Eric W. Stirling Number of the Second Kind (англ.) на сайте Wolfram MathWorld.
• Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.