Что считает S(n, k)
Число Стирлинга второго рода S(n, k) показывает, сколькими способами можно разбить n различимых элементов ровно на k непустых неупорядоченных групп. Люди, карточки или файлы различаются, а группы не имеют названий. Для четырёх элементов и двух групп получается S(4, 2) = 7.
Число Стирлинга второго рода считает разбиения множества на заданное число непустых подмножеств. Каждый элемент входит ровно в одну группу, группы не пересекаются, а их перестановка не меняет результат.
Ключевая рекурсия рассматривает последний, n-й элемент. Его можно добавить в одну из k уже существующих групп либо выделить ему место в новой группе рядом с разбиением остальных элементов на k - 1 групп:
Определение, специальные значения и рекурсия приведены в NIST DLMF, §26.8. Калькулятор применяет ту же формулу динамически в одной строке BigInt. Обновление идёт справа налево, поэтому старое S(n - 1, k - 1) не затирается раньше времени.
Как читать рекуррентную формулу
Возьмём S(5, 3). Если пятый элемент попадает в одну из трёх готовых групп, есть 3 × S(4, 3) = 3 × 6 = 18 вариантов. Если он образует новую группу, остальные четыре элемента нужно разбить на две группы, что даёт S(4, 2) = 7 вариантов. Итого S(5, 3) = 18 + 7 = 25.
Границы следуют из определения. S(0, 0) = 1, потому что пустое множество имеет одно пустое разбиение. Для n > 0 значение S(n, 0) = 0. Разбить n элементов на n непустых групп можно одним способом, по одному элементу в каждой, поэтому S(n, n) = 1. При k > n допустимых разбиений нет, и калькулятор показывает ошибку вместо молчаливого нуля.
Внутри алгоритма хранится только k + 1 больших целых. Для каждой строки j обновляется от min(i, k) до 1 по формуле row[j] = j × row[j] + row[j - 1], затем row[0] становится нулём. Это требует O(nk) операций и O(k) памяти. S(1000, 500) содержит 1527 цифр, но результат остаётся точным.
Примеры разбиения на заданное число групп
👥 Четыре человека в две команды. S(4, 2) = 7, если команды не имеют названий. Состав «Анна и Борис» рядом с составом «Вера и Глеб» не становится новым вариантом после перестановки команд местами.
📚 Пять разных книг в три стопки. S(5, 3) = 25. Каждая стопка должна получить хотя бы одну книгу, а порядок книг внутри стопки и расположение самих стопок не учитываются. Если важен порядок книг, модель нужно расширить.
🧩 Шесть сервисов в три пакета запуска. S(6, 3) = 90 способов сформировать непустые неименованные пакеты. Число помогает оценить пространство вариантов, но зависимости между сервисами могут запретить часть разбиений.
🔬 Восемь образцов в два кластера. S(8, 2) = 127. Для двух групп действует короткое равенство S(n, 2) = 2ⁿ⁻¹ - 1, поэтому 2⁷ - 1 = 127. Оно удобно как независимая проверка динамического расчёта.
🧪 Десять тестировщиков в три неименованные группы. S(10, 3) = 9330. Если три группы получают названия «браузер», «мобильная версия» и «API», назначения становятся различимыми, и ответ увеличивается в 3! = 6 раз до 55 980.
📦 Семь предметов в семь групп. S(7, 7) = 1: каждый предмет остаётся один. На противоположной границе S(7, 1) тоже равно 1, потому что все предметы входят в одну общую группу.
Чем группы отличаются от сочетаний и назначений
Число сочетаний C(n, k) выбирает одну группу из k элементов и оставляет остальные за её пределами. S(n, k) распределяет все n элементов по k группам. Например, C(5, 2) = 10 выбирает пару из пяти, а S(5, 2) = 15 разбивает все пять элементов на две непустые части.
Если группы подписаны, после разбиения их можно назначить k названиям k! способами. Поэтому количество распределений n различимых элементов по k различимым непустым контейнерам равно k! × S(n, k). Для пяти предметов и трёх подписанных коробок получаем 3! × 25 = 150.
Не путайте второе и первое семейства чисел Стирлинга. Второй род работает с разбиениями множества на группы. Первый род связан с перестановками и числом циклов. Одинаковая фамилия в названии не делает формулы взаимозаменяемыми.
Как S(n, k) связано с числами Белла
Число Белла снимает ограничение на количество групп. Для фиксированного n нужно сложить S(n, k) по всем k от 0 до n. При n = 4 получаем 0 + 1 + 7 + 6 + 1 = 15, поэтому B₄ = 15.
Если задача говорит «ровно три команды», нужен S(n, 3). Если разрешено любое число непустых команд, нужен калькулятор числа Белла Bₙ. Эта разница меняет ответ радикально: для n = 10 значение S(10, 3) равно 9330, а B₁₀ равно 115 975.
Треугольник значений записан в OEIS A008277. Первые строки дают S(3, 1..3) = 1, 3, 1 и S(4, 1..4) = 1, 7, 6, 1. Эти короткие строки вместе с S(0, 0), S(n, 0) и S(n, n) подходят для проверки собственной реализации.
Важно! Калькулятор считает группы непустыми и неименованными. Ограничения на размер, совместимость элементов, порядок внутри группы или разные роли групп требуют другой модели.
Вопросы о числах Стирлинга второго рода
Ответы помогают проверить нулевые случаи, различить именованные и неименованные группы и понять, когда результат нужно умножить на факториал.
Чему равно S(0, 0)?
S(0, 0) = 1. Пустое множество можно разбить на ноль групп одним способом: оставить пустое разбиение.
Почему S(n, 0) равно нулю при n больше 0?
Ни один из n элементов нельзя разместить, если групп нет. Поэтому допустимых разбиений не существует.
Почему S(n, n) равно 1?
При n непустых группах каждый из n элементов обязан оказаться в собственной группе. Состав разбиения определяется однозначно.
Что происходит при k больше n?
Нельзя создать больше непустых групп, чем есть элементов. Калькулятор сохраняет введённое k и показывает понятную ошибку, чтобы условие задачи не маскировалось.
Учитывается ли порядок групп?
Нет. Перестановка двух групп не создаёт новый вариант. Если группы подписаны, количество назначений равно k! × S(n, k).
Чем S(n, k) отличается от C(n, k)?
C(n, k) выбирает k элементов из n, а остальные не входят в выбранную группу. S(n, k) распределяет все n элементов по k непустым группам.
Как получить число Белла из строки S(n, k)?
Сложите значения S(n, k) для всех k от 0 до n. Например, для n = 4 сумма 0 + 1 + 7 + 6 + 1 даёт B₄ = 15.
Округляется ли длинный результат?
Нет. Одномерная динамика использует BigInt, поэтому результат выводится целиком. Пробелы между группами цифр служат только для чтения.
Похожие калькуляторы
Возможно вам пригодятся ещё несколько калькуляторов по данной теме:
- Калькулятор числа Белла. Введите количество различимых элементов n от 0 до 1000. Калькулятор найдёт число всех разбиений множества.
- Число сочетаний. Введите общее число элементов n и размер выборки k. Калькулятор найдёт точное количество сочетаний без учёта порядка.
- Калькулятор числа разбиений p(n). Введите целое n от 0 до 10 000. Калькулятор посчитает разбиения на положительные слагаемые без учёта порядка.
- Обычный калькулятор. Просто посчитайте чего вы там хотели.
- Рандомайзер: генератор случайных чисел. Выберите случайное число в нужном диапазоне для любых целей, в частности для розыгрышей и онлайн-лотерей в соцсетях.
- Бросить монетку онлайн. С помощью данной формы вы можете подбросить монетку онлайн любое количество раз.
- Калькулятор корней. Найдите правильное решение корней n-степени, включая квадратные и кубические.
- Калькулятор дробей. Выполните сложение, умножение, сокращение обыкновенных дробей.
- Калькулятор квадратных уравнений. Решите квадратные уравнения с помощью специальных формул, через дискриминант и по теореме Виета. Все способы решения сопровождаются примерами.
- Калькулятор сложного процента. Рассчитайте на инвесткалькуляторе сумму, полученную в результате применения сложного процента с реинвестированием, регулярным пополнением, капитализацией и с примерами.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.