Двенадцатеричный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатеричный путь предложил Джоэл Спенсер по аналогии с термином восьмеричный путь из физики, который в свою очередь произошел от понятия восьмеричный путь в буддизме. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем 12 разных результатов.
Обзор Пусть и будут конечными множествами. Обозначим через и мощность этих множеств (число элементов). Будем говорить, что является -множеством, а является -множеством.
Основная задача, которую будем рассматривать, заключается в подсчёте классов эквивалентности функций .
Функции попадают под одно из трёх следующих ограничений: Нет ограничений: любой элемент из может быть отображён функцией в любой элемент из , и каждый элемент может встретиться несколько раз. является инъекцией: каждое значение для из должно отличаться от всех остальных, так что каждый элемент из может встретиться максимум один раз в образе функции . является сюръекцией: для любого элемента из должен быть по меньшей мере один элемент из , такой, что , то есть каждый элемент будет встречаться в образе функции по меньшей мере один раз. (Условие « является биекцией» возможно только в случае, когда , но тогда оно эквивалентно как « является инъекцией», так и « является сюръекцией».)
Существует четыре различных отношения эквивалентности, которые могут быть определены на множестве функций из в : равенство; равенство с точностью до перестановки элементов ; равенство с точностью до перестановки множества ; равенство с точностью до перестановки множеств и . Любое из этих отношений эквивалентности даёт разбиение множества функций на классы эквивалентности.
(Класс эквивалентности — это орбита функции под действием рассматриваемой группы: , или , или , или , где — симметрическая группа на N, а — симметрическая группа на X.)
Три условия на функции и четыре отношения эквивалентности могут быть скомбинированы в сценариев.
Двенадцать задач подсчёта классов эквивалентности функций не эквивалентны по сложности, и нет единого систематического метода их решения. Две задачи тривиальны (число классов эквивалентности равно 0 или 1), пять задач имеет ответ в терминах мультипликативной формулы от n и x, а оставшиеся пять задач имеют ответ в терминах комбинаторных функций (числа Стирлинга второго рода и функции разбиения для заданного числа частей).
Классические задачи подсчёта согласуются с этими установками следующим образом. Подсчёт n-перестановок (то есть или последовательностей без повторений) множества X эквивалентен подсчёту инъективных функций . Подсчёт n-сочетаний множества X эквивалентен подсчёту инъективных функций с точностью до перестановки множества N. Подсчёт перестановок множества X эквивалентен подсчёту инъективных функций , где , а также подсчёту сюръективных функций , где . Подсчёт мультимножеств размера n (известных также как n-сочетания с повторениями) элементов из X эквивалентен подсчёту всех функций с точностью до перестановок множества N. Подсчёт разбиений множества N на x подмножеств эквивалентен подсчёту всех сюръективных функций с точностью до перестановок множества X. Подсчёт разложений числа n на x частей эквивалентен подсчёту всех сюръективных функций с точностью до перестановок множества N.
Точки зрения Различные задачи в двенадцати сценариях можно рассматривать с различных точек зрения.
Шары и ящики Традиционно многие из задач в двенадцати сценариях формулируются в терминах размещения шаров по ящикам (или другие похожие визуализации) вместо определения функций. Множество N можно отождествить с шарами, а множество X — с ящиками. Функция тогда описывает способ распределения шаров по ящикам, а именно, шар a размещается в ящик . Тогда свойство, что функция приписывает единственный образ каждому значению из области определения, отражается свойством, что любой шар может попасть только в один ящик (вместе с требованием, что никаких шаров не должно остаться вне ящиков), где любой ящик может принять (в принципе) произвольное число шаров. Требование от ƒ быть инъективной означает запрещение укладывания более одного шара в любой ящик, в то время как требование от ƒ быть сюръективной означает, что каждый ящик должен содержать по меньшей мере один шар.
Подсчёт отношений эквивалентности перестановок множества N и/или множества X отражается в признании шаров и ящиков «неразличимыми». Это признание не является точной формулировкой (на практике индивидуальные шары и ящики могут быть различены по их положению и можно разместить различные шары по различным ящикам), но указывает, что различные конфигурации не считаются отдельными, если одна из них может быть преобразована в другую путём обмена шаров или ящиков. Это как раз то, что формализуется перестановками множеств N и/или X. Неразличимые ящики труднее представить, чем неразличимые шары, поскольку конфигурация неминуемо предполагает некоторое упорядочение ящиков. Перестановка ящиков будет проявляться как обмен их содержимого.
Выборки Другой подход к рассмотрению тех же случаев — в терминах выборок в статистике. Представим себе популяцию X объектов (или людей), из которой мы выбираем N. Обычно рассматриваются две схемы, известные как «выборка с возвращением» и . В первом случае (выборка с возвращением) после выборки объекта мы возвращаем его в популяцию, так что он может нам попасть снова. Результат каждой такой выборки независим от всех других выборок и множество выборок технически считается независимыми одинаково распределёнными случайными величинами. Во втором случае, однако, после выборки объекта мы откладываем его в сторону и объект второй раз появиться не может. Это означает, что факт выборки одного объекта имеет эффект на все последующие выборки (конкретный объект не может попасть во второй раз), так что наши выборки оказываются зависимыми одна от другой.
В случае выборки с возвратом мы ниже будем говорить «Любая f' », в то время как при выборке без возврата будем говорить «Инъективная f' ». Каждый ящик означает, сколько различных выборок наборов было сделано в конкретной схеме. Строка со словом «Различные» означает, что порядок учитывается. Например, если мы имеем объекты, из которых мы выбираем два, то выборка (4,7) отличается от (7,4). С другой стороны, строка, помеченная «Sn порядок», означает, что порядок значения не имеет; в этом случае выборки (4,7) и (7,4) эквивалентны. В терминах распределения вероятностей, выборки с возвращением, где упорядочение учитывается, сравнимы с описанием совместного распределения N отдельных случайных величин, каждое с X-кратным . Случай, где порядок не учитывается, сравним с описанием отдельного мультиномиального распределения N выборок из X-кратной категории, где лишь число каждой категории имеет значение. Случай, в котором порядок не учитывается и выборки осуществляются без возвращения, сравним с отдельным мультивариантным гипергеометрическим распределением, а сравнение четвёртой возможности с чем-то не проглядывается. Заметим, что во всех «инъективных» случаях (то есть при выборках без возвращения), число наборов выборок равно нулю, если не выполняется . (Слово «сравнимый» в вышеприведённых случаях означает, что каждый элемент пространства элементарных событий соответствующего распределения соответствует отдельному множеству выборок, а потому число в ячейке показывает размер пространства событий для данного распределения.)
С этой точки зрения случай с пометкой «Сюръективная f' » выглядит странным. По существу, мы продолжаем выбирать с возвращением, пока не выберем каждый элемент по меньшей мере один раз. Теперь мы подсчитываем, сколько раз мы вытаскивали шары, и, если это число не равно N, отбрасываем всю выборку и повторяем. Это смутно напоминает , где процесс вовлекает «собирание» (выборка с возвращением) множества X купонов, пока не наберём набор, в который каждый купон входит по меньшей мере один раз. Заметим, что во всех «сюръективных случаях» число множеств выборок равно нулю, если не .
Выборка, разметка, группировка Функцию можно рассматривать с опорой на X или N. Это приводит к различным точкам зрения:
функция ƒ помечает каждый элемент множества N элементом из X. функция ƒ выбирает элемент множества X для каждого элемента множества N, всего получая n выборок. функция ƒ группирует элементы множества N вместе, если они отображаются в тот же элемент множества X.
Эти точки зрения не одинаково подходят ко всем случаям. Точки зрения «разметка» и «выборка» не вполне совместимы с перестановкой элементов множества X, поскольку они меняют метки и выборки. С другой стороны, точка зрения «группировка» не даёт полную информацию о конфигурации, если элементы множества X не могут быть переставлены. Точки зрения «разметка» и «выборка» более или менее эквивалентны, когда N не переставляются, но в этом случае точка зрения «выборки» подходит больше. Выборку тогда можно рассматривать как неупорядоченную выборку — выбирается (мульти-)множество из n элементов из множества X.
Разметка и выборка с повторениями или без повторений Если рассматривать ƒ как пометку элементов множества N, буквы могут рассматриваться как упорядоченные в последовательность, а метки как последовательно назначаемые элементам. Требование, что функция ƒ инъективна, означает, что никакая метка не может быть использована дважды. Результатом будет последовательность меток без повторений. При отсутствии этого требования используется терминология «последовательности с повторениями», что означает, что метки могут быть использованы более одного раза (хотя последовательности, в которых повторений нет, также допустимы).
Для неупорядоченной выборки применим тот же вид различения. Если ƒ должна быть инъективной, то выбор должен вовлекать n различных элементов множества X, так что это будет подмножеством множества X размера n, так называемым n-сочетанием. Без этого требования тот же самый элемент набора X может оказаться в выборке несколько раз, так что результатом будет мультимножество из n элементов множества X, которое называется также n-мультисочетанием или n-сочетанием с повторением.
В этих случаях требование сюръективности ƒ означает, что любая метка должна использоваться по меньшей мере один раз, или что любой элемент множества X должен быть включён в выборку по меньшей мере один раз. Такое требование менее естественно при математическом рассмотрении, и более того, предыдущий случай легче рассматривается как группировку элементов N с добавлением в качестве меток групп элементов множества X.
Разбиения множеств и чисел Если рассматривать ƒ как группировку элементов множества N (что предполагает отождествление по перестановкам множества X), требование, чтобы ƒ была сюръективной, означает, что число групп должно быть в точности равно x. Без этого требования число групп не может превосходить x. Требование инъективности ƒ означает, что каждый элемент N должен быть сам по себе группой group, что оставляет только одну допустимую группировку, а потому не является интересной задачей подсчёта.
Если, кроме того, производится отождествление по перестановкам множества N, это приводит к забыванию групп, остаются только их размеры. Эти размеры не идут в каком-то определённом порядке, а сами размеры могут встречаться более одного раза. Можно упорядочить размеры в слабоубывающий список чисел, сумма которых равна nСлабоубывающий список — это убывающий список с возможностью повторения.. Это даёт комбинаторное представление разбиения числа n на в точности x (для сюръективной ƒ) или не более чем на x (для произвольной ƒ) частей.
Формулы Формулы для различных случаев двенадцати сценариев сведены в таблицу, каждый элемент таблицы связан с разделом ниже, объясняющим формулу.