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

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

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

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

1)

S (n, k) = S (n - 1, k - 1) + k \cdot S (n - 1, k)

для

0 < k \leq n

.

2)

S (n, k) = \sum_{j = 0}^{n - 1} (\binom{n - 1}{j}) S (j, k - 1)

.

при естественных начальных условиях

S (0, 0) = 1

,

S (n, 0) = 0

при

n > 0

и

S (j, k) = 0

при

k > j

.

S (n, k) = \frac{1}{k!} \sum_{j = 0}^{k} (- 1)^{k + j} (\binom{k}{j}) j^{n} .

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