Почему я узнал про эту статью только сейчас???
Одна из самых красивых таблиц в комбинаторике — это “двенадцатикратный путь” Ричарда Стэнли.
По сути, это большая карта задач про шарики и урны. Есть шарики, есть урны, и мы хотим понять, сколько бывает разных способов их разложить.
Но вся магия в том, что задачи меняются в зависимости от трех вопросов:
— различимы ли шарики;
— различимы ли урны;
— есть ли ограничения: можно ли класть сколько угодно, не больше одного или обязательно хотя бы по одному.
Из этого получается 12 базовых сюжетов. И почти вся начальная комбинаторика внезапно собирается в одну систему.
Итак, поехали:
1. Различимые шарики, различимые урны, без ограничений.
Самая прямая задача: каждый шарик можно положить в любую урну.
2. Различимые шарики, различимые урны, не больше одного шарика в урну.
Уже появляется запрет на повторное заполнение: как рассадить разные объекты по разным местам без совпадений.
3. Неразличимые шарики, различимые урны, без ограничений.
Теперь важны только количества шариков в каждой урне, а не то, какой именно шарик куда попал.
4. Неразличимые шарики, различимые урны, не больше одного в урну.
То же самое, но теперь урна либо занята, либо нет.
5. Неразличимые шарики, различимые урны, в каждой урне должен быть хотя бы один шарик.
Классическая задача на распределение одинаковых объектов по подписанным ячейкам без пустых мест.
6. Различимые шарики, неразличимые урны, в каждой урне хотя бы один шарик.
Здесь уже важны не сами урны, а разбиение множества шариков на группы. То есть мы не нумеруем урны, а просто делим объекты на несколько непустых кучек.
7. Различимые шарики, различимые урны, в каждой урне хотя бы один шарик.
Почти то же самое, что и в предыдущем пункте, но теперь группы еще и “подписаны”.
8. Различимые шарики, неразличимые урны, без ограничений.
Можно разбивать шарики на разное число групп, не обязательно использовать все урны.
9. Различимые шарики, неразличимые урны, не больше одного в урну.
Если урны одинаковые, то при таком ограничении задача резко упрощается: по сути, нас интересует только, хватает ли урн.
10. Неразличимые шарики, неразличимые урны, не больше одного в урну.
Совсем “схлопывающийся” случай: если и шарики, и урны одинаковые, различать почти нечего.
11. Неразличимые шарики, неразличимые урны, в каждой урне хотя бы один шарик.
Это уже задача не столько про урны, сколько про разбиение числа на части.
12. Неразличимые шарики, неразличимые урны, без ограничений.
Самый “числовой” вариант: одинаковые объекты раскладываются по одинаковым кучкам, и пустые кучки допускаются.
То есть перед нами не 12 случайных упражнений, а удобная карта, по которой можно ориентироваться почти во всей базовой комбинаторике.