Математика · объяснение и практика

Числа Стирлинга второго рода: разбиваем различимые элементы на группы

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Число 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. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться