Математика · объяснение и практика
Числа Стирлинга второго рода: разбиваем различимые элементы на группы
Доказываем рекурсию по положению последнего элемента, различаем состав групп и размеры частей, затем связываем неподписанные непустые группы с подписанными ящиками.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Число S(n,k) считает разбиения множества из n различимых элементов на k непустых неподписанных блоков. Последний элемент либо образует отдельный блок, либо входит в один из k существующих. Поэтому S(n,k)=S(n−1,k−1)+kS(n−1,k).
Имена элементов сохраняются, имена блоков отсутствуют
В разбиении множества каждый элемент входит ровно в один блок. Блоки не пересекаются и вместе дают всё множество. Порядок блоков и порядок элементов внутри блока не учитываются. Записи {А,Б}|{В} и {В}|{Б,А} обозначают один объект, но {А,В}|{Б} обозначает другой: изменился состав группы, хотя размеры остались теми же.
Это отличает S(n,k) от числа разбиений целого n на k слагаемых. Для трёх именных карточек есть три разбиения на два блока: отдельно лежит А, Б или В. Все три имеют один размерный рисунок 2+1. Забывание имён склеивает их; по одному списку размеров восстановить исходное распределение нельзя. Неподписанный блок тоже не означает, что его содержимое стало неразличимым.
Удаляем последний элемент и получаем два непересекающихся случая
Если элемент n стоит отдельно, удалим его одноэлементный блок. Останется разбиение n−1 элементов на k−1 блоков. Обратное действие единственно: добавить {n}. Если n не одинок, удалим только его. Число блоков останется k, а для возвращения n можно выбрать любой из этих k блоков. Это даёт kS(n−1,k).
Случаи не пересекаются, потому что размер блока, содержащего n, либо равен единице, либо больше неё. Они исчерпывают все разбиения, поэтому количества складываются. Начальные значения S(0,0)=1, S(n,0)=0 при n>0 и S(0,k)=0 при k>0 завершают рекурсию. Также S(n,k)=0 при k>n: непустых блоков не может быть больше элементов. Для n≥1 на краях S(n,1)=S(n,n)=1.
Пример
Найдите S(5,3), зная S(4,2)=7 и S(4,3)=6. Сколько соответствующих назначений в три подписанных непустых ящика?
Отдельный блок {5} даёт семь разбиений. В остальных пятый элемент добавляется в один из трёх блоков каждого из шести разбиений, то есть даёт восемнадцать. Всего S(5,3)=25. Назначение трёх подписей даёт 3!·25=150. Числа 25 и 150 отвечают разным соглашениям о различимости групп.
Подписи блоков возвращают факториал, а не дополнительное размещение элементов
Каждому разбиению на k непустых блоков можно назначить k разных подписей ровно k! способами. Ни одна перестановка подписей не оставляет распределение прежним: в каждом блоке есть элемент, и его ящик сменился бы. Поэтому число назначений в k подписанных ящиков без пустых равно k!S(n,k). Дополнительного множителя n! здесь нет: имена элементов уже учтены в самом разбиении.
Например, S(4,2)=7, а подписанные два ящика дают 2·7=14 назначений. Это согласуется с 2⁴−2: из всех двоичных назначений исключены два постоянных. Если же ящики могут оставаться пустыми, простое деление общего числа kⁿ на k! неверно: перестановки пустых подписей создают повторы. Связь с факториалом доказана именно для ровно k непустых блоков.
Ещё одна проверяемая граница — разбиение n элементов на n−1 блок. Ровно один блок должен содержать пару, а остальные остаются одноэлементными: более крупная группа уменьшила бы число блоков сильнее. Пару выбирают C(n,2) способами. Поэтому S(n,n−1)=C(n,2). Здесь выбор относится к конкретным именам двух элементов; одного рисунка размеров 2+1+…+1 было бы недостаточно для правильного ответа.
От чтения к действию
А теперь — вы
Частые вопросы
Почему в рекурсии множитель k, а не n−1?
Выбирается существующий блок, а не конкретный сосед элемента. Внутреннего порядка в блоке нет; добавление после разных его элементов не создаёт новых разбиений.
Можно ли допускать пустые блоки?
Тогда это другая модель. В определении S(n,k) все k блоков непусты; иначе число блоков и множитель k! требуют нового учёта.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как включения и исключения считают распределения без пустых ящиков
Посчитайте размещения различимых объектов по подписанным ящикам без пустых: включения и исключения исправят многократное вычитание.
Открыть темуПочему разбиения числа отличаются от упорядоченных сумм
Как считать разбиения числа на положительные слагаемые без порядка, отличать их от композиций и не делить автоматически число упорядоченных сумм на факториал.
Открыть темуПочему соседние числа треугольника Паскаля складываются
Доказываем правило сложения соседних чисел через разбиение выборок на две непересекающиеся группы и проверяем нумерацию строк треугольника.
Открыть тему