Разбиения n-множества на k непустых блоков без имён
Число Стирлинга второго рода S(n,k) считает, сколькими способами разрезать n различных объектов на k непустых куч. Кучи не подписаны: { {1,2},{3} } то же, что { {3},{1,2} }. Раздел: комбинаторика.
Контроль: S(5,2) = 15, S(5,3) = 25, S(4,2) = 7, S(3,3) = 1.
n, k целые 0…20, для ненулевых 1 ≤ k ≤ n. Родитель математика.
S(n, k) = k S(n − 1, k) + S(n − 1, k − 1)
S(n, k) = k S(n − 1, k) + S(n − 1, k − 1)
Новый элемент либо вступает в один из k уже существующих блоков (k вариантов), либо открывает свой блок (тогда остальные n−1 режутся на k−1). Искомое — S.
Не C(n,k) и не сюръекции
Не выбор k из n. Не функции на k меток: там блоки покрашены. Не кратности букв в слове — там состав задан заранее. Не скобки Каталана.
Как пользоваться
n человек, k неподписанных комнат, ни одна не пуста, комнаты одинаковые. Получите число заселений. Если комнаты с номерами — умножьте на k! на странице сюръекций.
Примеры
1. Пять на два. 15.
2. Пять на три. 25.
3. Четыре на два. 7.
4. Все одиночки. S(3,3) = 1.
5. Запрет. k = 5 при n = 4.
Ещё задачи
S(4,1) = 1, S(4,3) = 6, S(4,4) = 1. Проверка суммы (Белл B_4): 1+7+6+1 = 15.
Три объекта на два блока: S(3,2) = 3. Пары {ab|c}, {ac|b}, {bc|a}.
Связь с N: N(5,2) = 2!·15 = 30. Не пишите 15, если ящики красный и синий.
Не кладите пустые комнаты: это уже Стирлинг с другим соглашением или «не больше k блоков».
C(5,2) = 10 — выбрать двоих, не разрезать пятёрку.
S(n,2) = 2^{n−1} − 1. Проверка: 2^4 − 1 = 15. Страница рекурсию, эту явную можно сверить в тетради.
S(n,n−1) = C(n,2): ровно одна пара в блоке, остальные одиночки.
Одна размерность: число разбиений.
Два независимых множеств — произведение, не S(n+m, k).
Метки внутри блока не упорядочены. Если внутри блока очередь — уже не Стирлинг 2.
Куда класть n-й элемент
Чертёж: n точек, k овалов без подписей, каждая точка в одном овале, овалы непусты.
Памятка: кучи без имён, рекурсия «в старый блок / новый блок».
Хаб комбинаторики рядом с сюръекциями, чтобы не забыть k!.
Итог: 1 ≤ k ≤ n, S(n,1)=S(n,n)=1.
Числа Белла
B_n = Σ_k S(n,k) — все разбиения без фиксации k. Страница одно k. Сумму наберите несколькими запросами. B_3 = 5, B_4 = 15, B_5 = 52.
Первый род Стирлинга считает циклы, не блоки. Его нет на сайте: не подставляйте знаковые c(n,k) сюда.
Родитель математика. Сосед по заданному составу размеров блоков: M, если ещё и размеры куч фиксированы, а кучи подписаны иначе.
Итог журнала: S(n,k) неподписанные блоки, не C, не k!S.
Контроль: 15; 25; 7; 1. k > n нельзя.
Пример: S(6,2) = 31 = 2^5 − 1.
Не подставляйте 6².
Рабочий пример: S(6,3) = 90. Не путать с мультиномиалом 90 от [2,2,2] — совпадение числа, другой смысл.
Связь с k!: только при переходе к сюръекциям.
Итог для отчёта: элементов n, блоков k, без имён комнат.
Финальный якорь: S(5,2) = 15. k = 6 при пяти нельзя.
Добор: не называйте это сочетаниями «команда из k».
Ещё якорь: S(2,1) = 1, S(2,2) = 1. Двое вместе или порознь.
Журнал: рабочие группы на проекте из 7 человек в 3 безымянных подгруппы: S(7,3) = 301.
Не путайте с мультимножествами: там элементы видов не различны как люди.
Финальный блок: второй род, непустые блоки, n ≤ 20, без пустых урн.
Ещё контроль: S(5,4) = C(5,2) = 10. S(5,5) = 1.
Почему плюс S(n−1,k−1)? Новый человек один в новой комнате, остальные уже разбиты на k−1.
Итог абзаца: разрезать множество, комнаты неотличимы.
Связь с P: внутри блока порядка нет.
Два цвета блоков вернут сюръекции, не это поле.
Финальный добор: S(n,k), не C(n,k), не N = k!S, не Каталан.
Отчёт: «пятнадцать разбиений» без 5 и 2 не проверить.
Стык с N(5,2): 30 подписанных.
Не кладите 0 блоков при n > 0: ошибка, не ноль в ответе.
Якорь: 15; 25; 7; 1. k > n нельзя.
Приложение: разложить 8 ключей на 3 связки без бирок: S(8,3) = 966.
Одинаковые объекты (монеты) ломают «множество» — тогда другие модели.
Повторный расчёт после того, как комнаты подписали этажами: умножьте на k! у соседа.
Сумма S(n,k) по k от 1 до n есть число Белла: все разбиения без фиксации числа комнат. Страница одну клетку таблицы, не Белла. S(n,1) = 1: все вместе. S(n,n) = 1: каждый сам.
Не путайте с первым родом |s(n,k)| — там циклы в перестановке, не блоки множества. Сосед C_n про скобки, не про разбиения людей.
Типичные ошибки
- Считать C(n,k).
- Забыть, что блоки без имён, и выдать k! S.
- Путать с первым родом (циклы).
- k > n.
- Пустые блоки.
Соседи: сюръекции, сочетания, мультиномиал, факториал, размещения.
Итог добора: S(n,k) — разбиения на k непустых неподписанных блоков, рекурсия, 1 ≤ k ≤ n ≤ 20.
Частые вопросы
- Чему равно S(5,2)?
- 15. Пять элементов на два непустых неподписанных блока.
- S(n,n) и S(n,1)?
- Оба равны 1: все одиночки или одна общая куча.
- Это сочетания?
- C(n,k) выбирает k элементов, не режет всё множество на k куч.
- Если блоки назвать (красные ящики)?
- Сюръекции N = k! S(n,k). Имена блоков умножают на k!.
- k больше n?
- Ошибка. Пустых блоков в определении второго рода нет, элементов не хватит.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).