🔀 Дискретка

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

Q: Чему равны S(n, n−1) и S(n, 2)?

$S(n, n-1) = \binom{n}{2}$: чтобы получить $n-1$ блоков, ровно один блок обязан быть парой, остальные — одиночки, а пару выбираем $\binom{n}{2}$ способами. Далее $S(n,2) = 2^{n-1}-1$: фиксируем элемент $a$, каждый из остальных либо с $a$, либо на другой стороне — и пустая сторона запрещена. Такие частные значения стоит помнить: они дают мгновенные проверки рекурренты и готовые ответы в задачах.

англ. Stirling number of the second kind

S(n,k) — число способов разложить n различных предметов в k неразличимых непустых коробок; то есть число разбиений множества на k блоков.

Число Стирлинга второго рода $S (n, k)$ отвечает на вопрос: сколькими способами $n$ различных предметов можно разложить в $k$ неразличимых непустых коробок? Иначе говоря — сколько у $n$ -элементного множества разбиений на $k$ блоков. Проверим на малых числах: $S (3, 2) = 3$ — тройку ${a, b, c}$ делим на пару и одиночку тремя способами. Основной инструмент — рекуррента $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ : новый элемент либо открывает свою коробку, либо встаёт в одну из $k$ существующих. Техника рекуррентных подсчётов — в уроке рекуррентные соотношения.

Вокруг $S (n, k)$ собраны классические ответы комбинаторики. Число сюръекций из $n$ -элементного множества в $k$ -элементное равно $k! S (n, k)$ : сначала разбиваем на блоки, потом раздаём блоки адресатам. Через формулу включений-исключений получается и явное выражение $S (n, k) = \frac{1}{k !} \sum_{j = 0}^{k} (- 1)^{k - j} (j k) j^{n}$ . Важная гигиена: не путать с приближением Стирлинга для факториала — там та же фамилия, но совсем другая формула и другой смысл.

S (n, k) = S (n - 1, k - 1) + k S (n - 1, k), # сюръекций = k! S (n, k)

рекуррента разбиений: k-я коробка либо забирает n-й элемент себе, либо он попадает в одну из k уже открытых

Частые вопросы

Чем числа Стирлинга второго рода отличаются от первого?

Второй род считает разбиения множества на непересекающиеся блоки — без всякой структуры внутри. Первый род считает перестановки с заданным числом циклов: например, $(13) (2) (45)$ имеет три цикла. Связь двойственная: числа первого рода — коэффициенты произведения $x (x + 1) \dots (x + n - 1)$ , а вторые переводят обычную степень $x^{n}$ в падающие факториалы. В стандартных задачах о коробках и сюръекциях встречается именно второй род.

Чему равны S(n, n−1) и S(n, 2)?

$S (n, n - 1) = (2 n)$ : чтобы получить $n - 1$ блоков, ровно один блок обязан быть парой, остальные — одиночки, а пару выбираем $(2 n)$ способами. Далее $S (n, 2) = 2^{n - 1} - 1$ : фиксируем элемент $a$ , каждый из остальных либо с $a$ , либо на другой стороне — и пустая сторона запрещена. Такие частные значения стоит помнить: они дают мгновенные проверки рекурренты и готовые ответы в задачах.