Введение

Систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств. В комбинаторике «двенадцатикратный путь» — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, включающая классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений множества или числа. Идея классификации принадлежит Джан Карло Роте, а название предложено Джоэлем Спенсером.

Мнения

Различные задачи в двенадцатикратном способе могут рассматриваться с различных точек зрения.

Шары и коробки

Традиционно многие задачи в двенадцатикратном способе формулировались в терминах размещения шаров в ящики (или аналогичной визуализации) вместо определения функций. Множество N можно отождествить с множеством шаров, а X – с множеством ящиков; тогда функция описывает способ распределения шаров по ящикам, а именно, помещая каждый шар в ящик. Функция сопоставляет каждому значению из своей области определения уникальный образ; это свойство отражается в том, что каждый шар может попасть только в один ящик (вместе с требованием, чтобы ни один шар не оставался вне ящиков), в то время как каждый ящик может вместить произвольное количество шаров. Требование инъективности дополнительно означает запрет на помещение более одного шара в любой ящик, а требование сюръективности – требование, чтобы каждый ящик содержал хотя бы один шар. Учет с точностью до перестановок N или X отражается в том, что шары или ящики, соответственно, называют "неразличимыми". Это не совсем точная формулировка, призванная указать, что различные конфигурации не следует считать отдельно, если одну можно преобразовать в другую перестановкой шаров или ящиков. Эта возможность преобразования формализуется действием перестановок.

Отбор проб

Другой способ рассмотреть некоторые из этих случаев — это выборка в статистике. Представьте себе совокупность из X элементов (или людей), из которой мы выбираем N. Обычно описываются две различные схемы, известные как «выборка с возвращением» и «выборка без возвращения». В первом случае (выборка с возвращением), как только мы выбрали элемент, мы возвращаем его в совокупность, так что можем выбрать его снова. В результате каждый выбор независим от всех остальных выборов, и набор образцов технически называется независимым и одинаково распределенным. Однако во втором случае, когда мы выбрали элемент, мы откладываем его в сторону, чтобы не выбрать его снова. Это означает, что выбор элемента влияет на все последующие выборы (конкретный элемент больше не может быть выбран), поэтому наши выборы зависимы друг от друга. Второе различие между схемами выборки заключается в том, имеет ли значение порядок. Например, если у нас есть десять элементов, из которых мы выбираем два, то выбор (4, 7) отличается от (7, 4), если порядок имеет значение; с другой стороны, если порядок не имеет значения, то выборы (4, 7) и (7, 4) эквивалентны. Первые два ряда и столбца таблицы ниже соответствуют выборке с возвращением и без возвращения, с учетом и без учета порядка. Случаи выборки с возвращением находятся в столбце, обозначенном как «Любые», а случаи выборки без возвращения — в столбце, обозначенном как «Инъективные». Случаи, когда порядок имеет значение, находятся в строке, обозначенной как «Различные», а случаи, когда порядок не имеет значения, — в строке, обозначенной как «Орбиты Sn». Каждая ячейка таблицы указывает, сколько различных наборов выборов существует в конкретной схеме выборки. Три из этих ячеек таблицы также соответствуют распределениям вероятностей. Выборка с возвращением, когда порядок имеет значение, сопоставима с описанием совместного распределения N отдельных случайных величин, каждая из которых имеет X-мерное категориальное распределение. Однако выборка с возвращением, когда порядок не имеет значения, сопоставима с описанием одного полиномиального распределения N извлечений из X-мерной категории, где имеет значение только количество каждого элемента категории. Выборка без возвращения, когда порядок не имеет значения, сопоставима с одним многомерным гипергеометрическим распределением. Выборка без возвращения, где порядок имеет значение, не соответствует распределению вероятностей. Во всех инъективных случаях (выборка без возвращения) количество наборов выборов равно нулю, если N ≤ X. («Сопоставимый» в вышеуказанных случаях означает, что каждый элемент пространства выборки соответствующего распределения соответствует отдельному набору выборов, и, следовательно, число в соответствующей ячейке указывает размер пространства выборки для данного распределения.) С точки зрения выборки, столбец, обозначенный как «Сюръективный», несколько странен: по сути, мы продолжаем выборку с возвращением, пока не выберем каждый элемент хотя бы один раз. Затем мы подсчитываем, сколько выборов мы сделали, и если это не равно N, отбрасываем весь набор и повторяем. Это отдаленно сопоставимо с задачей о собирателе купонов, где процесс включает в себя «собирание» (по выборке с возвращением) набора X купонов, пока каждый купон не будет замечен хотя бы один раз. Во всех сюръективных случаях количество наборов выборов равно нулю, если N ≥ X.

Маркировка, отбор, группировка

Функция может рассматриваться с точки зрения X или N. Это приводит к различным подходам:

Функция присваивает каждому элементу N элемент из X.
Функция выбирает элемент множества X для каждого элемента N, в общей сложности n выборов.
Функция объединяет элементы N, которые отображаются в один и тот же элемент X.
Эти подходы не одинаково подходят для всех случаев. Подходы, основанные на присвоении и выборе, плохо согласуются с перестановкой элементов X, поскольку это меняет присвоенные значения или выбор. С другой стороны, подход, основанный на объединении, не предоставляет полной информации о конфигурации, если элементы X не могут быть свободно переставлены. Подходы, основанные на присвоении и выборе, более или менее эквивалентны, когда N не переставляется, но когда N переставляется, подход, основанный на выборе, более уместен. Выбор можно рассматривать как неупорядоченный выбор: делается единый выбор (мульти)множества из n элементов из X.

Маркировка и отбор с повторением или без него

При рассмотрении как простановки меток элементам N, последние можно представить как расположенными в последовательности, а метки из X последовательно присваиваются им. Требование, чтобы была инъективной, означает, что ни одна метка не может быть использована повторно; в результате получается последовательность меток без повторений. При отсутствии такого требования используется терминология "последовательности с повторениями", что означает, что метки могут использоваться более одного раза (хотя допускаются и последовательности, которые случайно не содержат повторений). При рассмотрении как неупорядоченного выбора элементов из X применяется аналогичное различие. Если требуется, чтобы функция была инъективной, то выбор должен включать n различных элементов из X, то есть это подмножество X размера n, также называемое сочетанием из n элементов. Без этого требования один и тот же элемент из X может встречаться в выборе несколько раз, и результатом является мультимножество размера n, состоящее из элементов X, также называемое мультисочетанием из n элементов или сочетанием из n элементов с повторениями. Требование, чтобы функция была сюръективной, с точки зрения простановки меток элементам N, означает, что каждая метка должна быть использована хотя бы один раз; с точки зрения выбора из X – что каждый элемент X должен быть включен в выбор хотя бы один раз. Простановка меток с сюръекцией эквивалентна группировке элементов N с последующей простановкой метки каждому элементу группы из X и, следовательно, несколько сложнее для математического описания.

Разделения множеств и чисел

При рассмотрении как группировки элементов N (что подразумевает отождествление элементов при перестановках X), требование сюръективности означает, что число групп должно быть ровно x. Без этого требования число групп может быть не более x. Требование инъективности означает, что каждый элемент N должен составлять группу сам по себе, что оставляет максимум одну допустимую группировку и, следовательно, приводит к довольно тривиальной задаче подсчета. Если дополнительно отождествлять элементы при перестановках N, это равносильно забыванию самих групп, сохраняя лишь их размеры. Эти размеры при этом не имеют определенного порядка, и один и тот же размер может встречаться несколько раз; можно упорядочить их в неубывающий список чисел, сумма которых равна n. Это дает комбинаторное понятие разбиения числа n на ровно x (для сюръективных отображений) или не более x (для произвольных отображений) частей.

Подробности различных дел

Приведенные ниже примеры расположены в порядке, группирующем те, в которых аргументы, используемые при подсчете, имеют отношение друг к другу. Этот порядок отличается от порядка, представленного в таблице.

Инъективные функции от до , до перестановки

В этом случае мы рассматриваем последовательности из n различных элементов множества X, но отождествляем те, которые получаются друг из друга применением к каждому элементу перестановки X. Легко видеть, что любые две различные такие последовательности можно отождествить: перестановка должна сопоставлять i-й элемент первой последовательности i-му элементу второй последовательности, и поскольку ни одно значение не встречается дважды ни в одной из последовательностей, эти требования не противоречат друг другу; остаётся сопоставить элементы, отсутствующие в первой последовательности, биективно элементам, отсутствующим во второй последовательности, произвольным образом. Единственный фактор, от которого результат зависит от n и x, заключается в том, что само существование таких последовательностей требует n ≤ x, согласно принципу Дирихле. Следовательно, число выражается как , используя скобку Иверсона.

Инъективные функции от до , до перестановок и

Этот случай сводится к предыдущему: поскольку все последовательности из n различных элементов множества X уже могут быть преобразованы друг в друга применением перестановки к каждому из их элементов, то и допущение перестановки элементов не приводит к новым отождествлениям; число остаётся прежним.

Суръективные функции от до , до перестановки

Этот случай эквивалентен подсчету разбиений числа N на x (непустых) подмножеств или подсчету отношений эквивалентности на множестве N с ровно x классами эквивалентности. Действительно, для любой сюръективной функции f : N → X, отношение эквивалентности, определяемое совпадением образов элементов под действием f, является таким отношением эквивалентности, и оно не изменяется при применении перестановки к множеству X; обратно, любое такое отношение эквивалентности можно преобразовать в сюръективную функцию, произвольным образом сопоставив элементы множества X классам эквивалентности. Число таких разбиений или отношений эквивалентности по определению является числом Стерлинга второго рода S(n, x), также обозначаемым как S<sup>(2)</sup>(n, x). Его значение можно описать с помощью рекуррентного соотношения или с помощью производящих функций, но, в отличие от биномиальных коэффициентов, для этих чисел не существует замкнутой формулы, не содержащей суммирования.

Функции от до , до перестановки

Этот случай аналогичен соответствующему случаю для сюръективных функций, но некоторые элементы из x могут вообще не соответствовать ни одному классу эквивалентности (поскольку функции рассматриваются с точностью до перестановки X, неважно, какие именно элементы задействованы, а только их количество). Как следствие, мы подсчитываем отношения эквивалентности на N с не более чем x классами, и результат получается из рассмотренного случая суммированием по значениям до x, что дает. Если x ≥ n, размер x не накладывает никаких ограничений, и мы подсчитываем все отношения эквивалентности на множестве из n элементов (что эквивалентно всем разбиениям такого множества); следовательно, это дает выражение для числа Белла Bn.

Суръективные функции от до , до перестановок и

Этот случай эквивалентен подсчету разбиений числа n на x ненулевых частей. По сравнению со случаем подсчета сюръективных функций с учетом перестановок множества X, здесь сохраняются только размеры классов эквивалентности, на которые функция разбивает множество N (включая кратность каждого размера), поскольку два отношения эквивалентности могут быть преобразованы друг в друга перестановкой множества N тогда и только тогда, когда размеры их классов совпадают. Именно это отличает понятие разбиения числа n от понятия разбиения множества N, поэтому в результате получается, по определению, число px(n) разбиений числа n на x ненулевых частей.

Функции от до , до перестановок и

Этот случай эквивалентен подсчету разбиений числа n на не более x частей. Соответствие такое же, как и в предыдущем случае, за исключением того, что теперь некоторые части разбиения могут быть равны 0. (В частности, они соответствуют элементам множества X, не входящим в образ функции.) Каждое разбиение n на максимум x ненулевых частей можно расширить до такого разбиения, добавив необходимое количество нулей, и это учитывает все возможности ровно один раз, поэтому результат дается выражением. Добавляя 1 к каждой из x частей, получаем разбиение n + x на x ненулевых частей, и это соответствие биективно; следовательно, данное выражение можно упростить, записав его как .

Обобщения

Мы можем обобщить дальше, позволяя другим группам перестановок действовать на N и X. Если G — группа перестановок N, а H — группа перестановок X, то мы подсчитываем классы эквивалентности функций. Две функции f и F считаются эквивалентными тогда и только тогда, когда существует такое , что . Это расширение приводит к понятиям, как циклические и диэдрические перестановки, а также циклические и диэдрические разбиения чисел и множеств.