Непустые группы без подписей
Элементы различимы, группы нет. Поэтому разложить четыре предмета по двум непустым кучкам можно семью способами, если кучки не имеют имён.
S(n, k) = k × S(n − 1, k) + S(n − 1, k − 1)
S(4, 2) = 7
Число Стирлинга второго рода считает, сколькими способами разложить n разных предметов по k непустым группам, если сами группы между собой не различаются. S(4, 2) = 7. Пустых групп нет. Если группы подписаны («команда А и команда Б»), способов больше, их надо умножать на k!.
Рекурсия S(n, k) = k × S(n−1, k) + S(n−1, k−1). На экране итог, не дерево. Разбиение числа, где предметы одинаковые, — это разбиения.
Откуда брать числа
- Элементов
- Групп
Пример
S(4, 2) = 7.
Вопросы
S(n, n) и S(n, 1)?
Оба равны 1: либо все по одному, либо все в одной группе.
S(n, 0)?
Ноль при n больше нуля. S(0, 0) равно 1.
Потолок?
25 элементов и 25 групп: дальше числа становятся очень большими для этого экрана.