Двенадцатеричный путь

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

ОбзорПравить

Пусть $N$$N$  и $X$$X$  будут конечными множествами. Обозначим через $n=|N|$$n=|N|$  и $x=|X|$$x=|X|$  мощность этих множеств (число элементов). Будем говорить, что $N$$N$  является $n$$n$ -множеством, а $X$$X$  является $x$$x$ -множеством.

Основная задача, которую будем рассматривать, заключается в подсчёте классов эквивалентности функций $f:N\to <!--\; \to \; -->X$$f:N\to X$ .

Функции попадают под одно из трёх следующих ограничений:

1. Нет ограничений: любой элемент $a$$a$  из $N$$N$  может быть отображён функцией $f$$f$  в любой элемент $b$$b$  из $X$$X$ , и каждый элемент $b$$b$  может встретиться несколько раз.
2. $f$$f$  является инъекцией: каждое значение $f(a)$$f(a)$  для $a$$a$  из $N$$N$  должно отличаться от всех остальных, так что каждый элемент $b$$b$  из $X$$X$  может встретиться максимум один раз в образе функции $f$$f$ .
3. $f$$f$  является сюръекцией: для любого элемента $b$$b$  из $X$$X$  должен быть по меньшей мере один элемент $a$$a$  из $N$$N$ , такой, что $f(a)=b$$f(a)=b$ , то есть каждый элемент $b$$b$  будет встречаться в образе функции $f$$f$  по меньшей мере один раз.

(Условие «$f$$f$  является биекцией» возможно только в случае, когда $n=x$$n=x$ , но тогда оно эквивалентно как «$f$$f$  является инъекцией», так и «$f$$f$  является сюръекцией».)

Существует четыре различных отношения эквивалентности, которые могут быть определены на множестве функций $f$$f$  из $N$$N$  в $X$$X$ :

1. равенство;
2. равенство с точностью до перестановки элементов $N$$N$ ;
3. равенство с точностью до перестановки множества $X$$X$ ;
4. равенство с точностью до перестановки множеств $N$$N$  и $X$$X$ .

Любое из этих отношений эквивалентности даёт разбиение множества функций на классы эквивалентности.

(Класс эквивалентности — это орбита функции $f$$f$  под действием рассматриваемой группы: f, или $f\circ <!--\; \circ \; -->S_n$$f\circ S_{n}$ , или $S_x\circ <!--\; \circ \; -->f$$S_{x}\circ f$ , или $S_x\circ <!--\; \circ \; -->f\circ <!--\; \circ \; -->S_n$$S_{x}\circ f\circ S_{n}$ , где $S_n$$S_{n}$  — симметрическая группа на N, а $S_x$$S_{x}$  — симметрическая группа на X.)

Три условия на функции и четыре отношения эквивалентности могут быть скомбинированы в $3\times <!--\; \times \; -->4=12$$3\times 4=12$  сценариев.

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

Классические задачи подсчёта согласуются с этими установками следующим образом.

• Подсчёт n-перестановок (то есть частичных перестановок^[en] или последовательностей без повторений) множества X эквивалентен подсчёту инъективных функций $N\to <!--\; \to \; -->X$$N\to X$ .
• Подсчёт n-сочетаний множества X эквивалентен подсчёту инъективных функций $N\to <!--\; \to \; -->X$$N\to X$  с точностью до перестановки множества N.
• Подсчёт перестановок множества X эквивалентен подсчёту инъективных функций $N\to <!--\; \to \; -->X$$N\to X$ , где $n=x$$n=x$ , а также подсчёту сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$ , где $n=x$$n=x$ .
• Подсчёт мультимножеств размера n (известных также как n-сочетания с повторениями) элементов из X эквивалентен подсчёту всех функций $N\to <!--\; \to \; -->X$$N\to X$  с точностью до перестановок множества N.
• Подсчёт разбиений множества N на x подмножеств эквивалентен подсчёту всех сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$  с точностью до перестановок множества X.
• Подсчёт разложений числа n на x частей эквивалентен подсчёту всех сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$  с точностью до перестановок множества N.

Точки зренияПравить

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

Шары и ящикиПравить

Традиционно многие из задач в двенадцати сценариях формулируются в терминах размещения шаров по ящикам (или другие похожие визуализации) вместо определения функций. Множество N можно отождествить с шарами, а множество X — с ящиками. Функция $f:N\to <!--\; \to \; -->X$$f:N\to X$  тогда описывает способ распределения шаров по ящикам, а именно, шар a размещается в ящик $f^{\prime }(a)$$f'(a)$ . Тогда свойство, что функция приписывает единственный образ каждому значению из области определения, отражается свойством, что любой шар может попасть только в один ящик (вместе с требованием, что никаких шаров не должно остаться вне ящиков), где любой ящик может принять (в принципе) произвольное число шаров. Требование от ƒ быть инъективной означает запрещение укладывания более одного шара в любой ящик, в то время как требование от ƒ быть сюръективной означает, что каждый ящик должен содержать по меньшей мере один шар.

Подсчёт отношений эквивалентности перестановок множества N и/или множества X отражается в признании шаров и ящиков «неразличимыми». Это признание не является точной формулировкой (на практике индивидуальные шары и ящики могут быть различены по их положению и можно разместить различные шары по различным ящикам), но указывает, что различные конфигурации не считаются отдельными, если одна из них может быть преобразована в другую путём обмена шаров или ящиков. Это как раз то, что формализуется перестановками множеств N и/или X. Неразличимые ящики труднее представить, чем неразличимые шары, поскольку конфигурация неминуемо предполагает некоторое упорядочение ящиков. Перестановка ящиков будет проявляться как обмен их содержимого.

ВыборкиПравить

Другой подход к рассмотрению тех же случаев — в терминах выборок в статистике. Представим себе популяцию X объектов (или людей), из которой мы выбираем N. Обычно рассматриваются две схемы, известные как «выборка с возвращением» и «выборка без возвращения»^[en]. В первом случае (выборка с возвращением) после выборки объекта мы возвращаем его в популяцию, так что он может нам попасть снова. Результат каждой такой выборки независим от всех других выборок и множество выборок технически считается независимыми одинаково распределёнными случайными величинами. Во втором случае, однако, после выборки объекта мы откладываем его в сторону и объект второй раз появиться не может. Это означает, что факт выборки одного объекта имеет эффект на все последующие выборки (конкретный объект не может попасть во второй раз), так что наши выборки оказываются зависимыми одна от другой.

В случае выборки с возвратом мы ниже будем говорить «Любая f' », в то время как при выборке без возврата будем говорить «Инъективная f' ». Каждый ящик означает, сколько различных выборок наборов было сделано в конкретной схеме. Строка со словом «Различные» означает, что порядок учитывается. Например, если мы имеем объекты, из которых мы выбираем два, то выборка (4,7) отличается от (7,4). С другой стороны, строка, помеченная «S_n порядок», означает, что порядок значения не имеет; в этом случае выборки (4,7) и (7,4) эквивалентны. В терминах распределения вероятностей, выборки с возвращением, где упорядочение учитывается, сравнимы с описанием совместного распределения N отдельных случайных величин, каждое с X-кратным категорийным распределением^[en]. Случай, где порядок не учитывается, сравним с описанием отдельного мультиномиального распределения N выборок из X-кратной категории, где лишь число каждой категории имеет значение. Случай, в котором порядок не учитывается и выборки осуществляются без возвращения, сравним с отдельным мультивариантным гипергеометрическим распределением, а сравнение четвёртой возможности с чем-то не проглядывается. Заметим, что во всех «инъективных» случаях (то есть при выборках без возвращения), число наборов выборок равно нулю, если не выполняется $N⩽<!--\; ⩽\; -->X$$N\leqslant X$ . (Слово «сравнимый» в вышеприведённых случаях означает, что каждый элемент пространства элементарных событий соответствующего распределения соответствует отдельному множеству выборок, а потому число в ячейке показывает размер пространства событий для данного распределения.)

С этой точки зрения случай с пометкой «Сюръективная f' » выглядит странным. По существу, мы продолжаем выбирать с возвращением, пока не выберем каждый элемент по меньшей мере один раз. Теперь мы подсчитываем, сколько раз мы вытаскивали шары, и, если это число не равно N, отбрасываем всю выборку и повторяем. Это смутно напоминает задачу о собирании купонов^[en], где процесс вовлекает «собирание» (выборка с возвращением) множества X купонов, пока не наберём набор, в который каждый купон входит по меньшей мере один раз. Заметим, что во всех «сюръективных случаях» число множеств выборок равно нулю, если не $N⩾<!--\; ⩾\; -->X$$N\geqslant X$ .

Выборка, разметка, группировкаПравить

Функцию $f:N\to <!--\; \to \; -->X$$f:N\to 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 (для произвольной ƒ) частей.

ФормулыПравить

Формулы для различных случаев двенадцати сценариев сведены в таблицу, каждый элемент таблицы связан с разделом ниже, объясняющим формулу.

Двенадцать комбинаторных объектов и их формулы.

f-класс	Любая f	Инъективная f	Сюръективная f
f	n-последовательность в X $x^n$$x^n$	n-перестановка множества X $x^{\underset{\_<!--\; \_\; -->}{n}}$$x^{\underline {n}}$	композиция N с x подмножествами $x!\{\genfrac{}{}{0ex}{}{n}{x}\}$$\textstyle x!\{{n \atop x}\}$
$f^{\prime }\circ <!--\; \circ \; -->S_n$$f'\circ S_{n}$	n-мультиподмножество of X $(\genfrac{}{}{0ex}{}{x+n-<!--\; -\; -->1}{n})$${\binom {x+n-1}{n}}$	n-подмножество множества X $(\genfrac{}{}{0ex}{}{x}{n})$${\binom {x}{n}}$	композиция n с x членами $(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n-<!--\; -\; -->x})$${\binom {n-1}{n-x}}$
$S_x\circ <!--\; \circ \; -->f$$S_{x}\circ f$	разбиение N на $⩽<!--\; ⩽\; -->x$$\leqslant x$  подмножеств $\underset{k=0}{\overset{x}{\sum <!--\; \sum \; -->}}\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$$\sum _{k=0}^{x}\left\{{n \atop k}\right\}$	разбиение N на $⩽<!--\; ⩽\; -->x$$\leqslant x$  элементов $[n⩽<!--\; ⩽\; -->x]$$[n\leqslant x]$	разбиение N на $⩽<!--\; ⩽\; -->x$$\leqslant x$  подмножеств $\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$$\left\{{n \atop x}\right\}$
$S_x\circ <!--\; \circ \; -->f\circ <!--\; \circ \; -->S_n$$S_{x}\circ f\circ S_{n}$	разбиение n на $⩽<!--\; ⩽\; -->x$$\leqslant x$  частей $p_x(n+x)$$p_{x}(n+x)$	разбиение n на $⩽<!--\; ⩽\; -->x$$\leqslant x$  частей 1 $[n⩽<!--\; ⩽\; -->x]$$[n\leqslant x]$	разбиение n на x частей $p_x(n)$$p_{x}(n)$

Используемые обозначения:

• Убывающий факториал $x^{\underset{\_<!--\; \_\; -->}{n}}=\frac{x!}{(x-<!--\; -\; -->n)!}=x(x-<!--\; -\; -->1)(x-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->n+1)$$x^{\underline {n}}={\frac {x!}{(x-n)!}}=x(x-1)(x-2)\cdots (x-n+1)$ ,
• Возрастающий факториал $x^{\stackrel{¯<!--\; ¯\; -->}{n}}=\frac{(x+n-<!--\; -\; -->1)!}{(x-<!--\; -\; -->1)!}=x(x+1)(x+2)\cdots <!--\; \cdots \; -->(x+n-<!--\; -\; -->1)$$x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots (x+n-1)$ ,
• Факториал $n!=n^{\underset{\_<!--\; \_\; -->}{n}}=n(n-<!--\; -\; -->1)(n-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->1$$n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1$ 
• Числа Стирлинга второго рода $\{\genfrac{}{}{0ex}{}{n}{k}\}$$\textstyle \{{n \atop k}\}$  выражают число способов разбиения множества из n элементов на k подмножеств
• Биномиальный коэффициент $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_<!--\; \_\; -->}{k}}}{k!}$$\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}$ 
• Скобка Айверсона кодируют истинность или ложность утверждения (как 1 или 0)
• число $p_k(n)$$p_{k}(n)$  разбиений числа n на k частей

Интуитивное значение строк и столбцовПравить

Здесь подведён краткий итог, что каждый класс означает. Классы описаны в деталях ниже.

Рассмотрим набор X пронумерованных элементов (числа от 1 до x), из которых мы выбираем n, что даёт упорядоченный список элементов. Например, если имеется $x=10$$x=10$  элементов, из которых мы выбираем $n=3$$n=3$ , результатом может быть список (5,2,10). Мы теперь подсчитываем, как много таких различных списков существует, иногда сначала преобразуя списки так, чтобы сократить число различных возможностей.

Тогда столбцы означают:

• Любая f: После того, как мы выбрали элемент, мы укладываем его обратно, так что мы его можем выбрать снова.
• Инъективная f: После того, как мы выбрали элемент, мы его откладываем в сторону, так что мы не можем выбрать его снова. Следовательно, мы заканчиваем выборку, имея n различных элементов. Безусловно, в этом случае, если не выполняется $n⩽<!--\; ⩽\; -->x$$n\leqslant x$ , никакого списка мы не получим.
• Сюръективная f: После того, как мы выбрали элемент, мы возвращаем его обратно, так что мы можем вытащить его снова, но в конце концов, мы должны выбрать каждый элемент по меньшей один раз. Безусловно, в этом случае, если не выполняется $n⩾<!--\; ⩾\; -->x$$n\geqslant x$ , никакого списка мы не получим.

Строки означают:

• Различные: Оставляем списки как есть, подсчитываем их прямо.
• S_n орбиты: Перед подсчётом сортируем списки по номерам выбранных элементов, так что порядок не имеет значение, e.g. (5,2,10), (10,2,5), (2,10,5) и т. д. все → (2,5,10).
• S_x орбиты: Перед подсчётом перенумеруем элементы так, что первый элемент в списке получает номер 1, второй (если не равен) получает номер 2, и т. д.. Числа могут повторяться, если элемент встречается в списке более одного раза, например, (3,5,3), (5,2,5), (4,9,4) и т. д. → (1,2,1), в то время как (3,3,5), (5,5,3), (2,2,9) и т. д. → (1,1,2).

• ${\mathbf{S}}_n\times <!--\; \times \; -->{\mathbf{S}}_x$$\mathbf {S} _{n}\times \mathbf {S} _{x}$  орбиты: Перед подсчётом список сортируется и перенумеровывается, как описывается выше. (Заметим: Перенумерация с последующей сортировкой может дать другие списки в некоторых случаях, однако число возможных списков не изменится.)

Детали различных случаевПравить

Случаи ниже упорядочены так, как они подсчитываются, что не совпадает с упорядочением в таблице.

Функции из N в XПравить

Этот случай эквивалентен подсчёту последовательностей n элементов множества X без ограничений: функция $f:N\to <!--\; \to \; -->X$$f:N\to X$  определяется n образами элементов из N, которые могут быт независимо выбраны следи элементов x. Это даёт в общей сложности xⁿ возможностей.

Пример:

$X=\{a,b,c\},N=\{p,q\}$$X=\{a,b,c\},N=\{p,q\}$ , тогда

$\left|\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}\right|=3^2=9$$\left\vert \{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}\right\vert =3^{2}=9$ 

Инъективные функции из N в XПравить

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

$x^{\underset{\_<!--\; \_\; -->}{n}}=x(x-<!--\; -\; -->1)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->n+1).$$x^{\underline {n}}=x(x-1)\cdots (x-n+1).$ 

Заметим, что в случае, когда $n>x$$n>x$ , один из множителей будет равен нулю, так что в этом случае нет инъективных функций $N\to <!--\; \to \; -->X$$N\to X$ . Это просто переформулировка принципа Дирихле.

Пример:

$X=\{a,b,c,d\},N=\{1,2\}$$X=\{a,b,c,d\},N=\{1,2\}$ , тогда

$\left|\{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right|=4^{\underset{\_<!--\; \_\; -->}{2}}=4\times <!--\; \times \; -->3=12$$\left\vert \{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert =4^{\underline {2}}=4\times 3=12$ 

Инъективные функции из N в X, с точностью до перестановки множества NПравить

Этот случай эквивалентен подсчёту подмножеств с n элементами из X, называемых также n-сочетаниями X — среди последовательностей из n различных элементов множества X, те, которые отличаются лишь порядком элементов, отождествляются с перестановками множества N. Поскольку во всех случаях все эти группы имеют ровно n! различных последовательностей, мы можем разделить число таких последовательностей на n!, чтобы получить число n-сочетаний набора X. Это число известно как биномиальный коэффициент $(\genfrac{}{}{0ex}{}{x}{n})$${\tbinom {x}{n}}$  и он задаётся формулой

$(\genfrac{}{}{0ex}{}{x}{n})=\frac{x^{\underset{\_<!--\; \_\; -->}{n}}}{n!}=\frac{x(x-<!--\; -\; -->1)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->n+2)(x-<!--\; -\; -->n+1)}{n(n-<!--\; -\; -->1)\cdots <!--\; \cdots \; -->2\cdot <!--\; \cdot \; -->1}.$${\binom {x}{n}}={\frac {x^{\underline {n}}}{n!}}={\frac {x(x-1)\cdots (x-n+2)(x-n+1)}{n(n-1)\cdots 2\cdot 1}}.$ 

Пример:

$X=\{a,b,c,d\},N=\{1,2\}$$X=\{a,b,c,d\},N=\{1,2\}$ , тогда

$\left|\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\right|=\frac{4^{\underset{\_<!--\; \_\; -->}{2}}}{2!}=\frac{4\times <!--\; \times \; -->3}{2}=6$$\left\vert \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\right\vert ={\frac {4^{\underline {2}}}{2!}}={\frac {4\times 3}{2}}=6$ 

Функции из N в X с точностью до перестановки NПравить

Этот случай эквивалентен подсчёту мультимножеств с n элементами из X (которые называются n-мультикомбинациями). Причина в том, что для каждого элемента из множества X сочетание определяется тем, как много элементов множества N отображаются в этот элемент функцией f, в то время как две функции, которые дают то же число «кратностей» для каждого элемента множества X, могут всегда быть преобразованы из одной в другую путём перестановки элементов множества N. Формула, подсчитывающая все функции $N\to <!--\; \to \; -->X$$N\to X$ , здесь бесполезна, поскольку число сгруппированных элементов перестановками of N меняется от функции к функции. Скорее, как объяснено в разделе «Сочетания с повторениями», число n-мультикомбинаций из множества с x элементами можно рассматривать как число n-сочетаний из множества с x + n − 1 элементами. Это сводит задачу к другому случаю в «двенадцатеричном пути», и даёт результат

$(\genfrac{}{}{0ex}{}{x+n-<!--\; -\; -->1}{n})=\frac{(x+n-<!--\; -\; -->1)(x+n-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->(x+1)x}{n(n-<!--\; -\; -->1)\cdots <!--\; \cdots \; -->2\cdot <!--\; \cdot \; -->1}=\frac{x^{\stackrel{¯<!--\; ¯\; -->}{n}}}{n!}.$${\binom {x+n-1}{n}}={\frac {(x+n-1)(x+n-2)\cdots (x+1)x}{n(n-1)\cdots 2\cdot 1}}={\frac {x^{\overline {n}}}{n!}}.$ 

Пример:

$X=\{a,b,c\},N=\{p,q\}$$X=\{a,b,c\},N=\{p,q\}$ , тогда

$\left|\{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}\right|=\frac{3^{\stackrel{¯<!--\; ¯\; -->}{2}}}{2!}=\frac{4\times <!--\; \times \; -->3}{2}=6$$\left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 3}{2}}=6$ 

Сюръективные функции из N в X с точностью до перестановки NПравить

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

$(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n-<!--\; -\; -->x}).$${\binom {n-1}{n-x}}.$ 

Заметим, что в случае $n<x$  нет вообще сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$ . Это принимается во внимание в формуле, если считается, что биномиальные коэффициенты всегда равны 0, если нижний индекс отрицателен. То же значение также задаётся выражением

$(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{x-<!--\; -\; -->1}),$${\binom {n-1}{x-1}},$ 

За исключением крайнего случая $n=x=0$$n=x=0$ , в котором предыдущая формула даёт верное значение $(\genfrac{}{}{0ex}{}{-<!--\; -\; -->1}{0})=1$${\tbinom {-1}{0}}=1$ , а последняя формула даёт $(\genfrac{}{}{0ex}{}{-<!--\; -\; -->1}{-<!--\; -\; -->1})=0$${\tbinom {-1}{-1}}=0$ .

Эта формула результата подсказывает искать ассоциацию сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$  непосредственно с подмножеством из n − x элементов, выбранных из n − 1 элементов, что можно сделать следующим образом. Сначала выберем полное упорядочение множеств N и X и заметим, что при применении подходящей перестановки множества N, любая сюръективная функция $N\to <!--\; \to \; -->X$$N\to X$  может быть преобразована в единственную медленно растущую (и, конечно, всё ещё сюръективную) функцию. Если соединить элементы множества N (согласно порядку) n − 1 дугами в линейный граф, то выбор любого подмножества n − x дуг и удаления остальных даст граф с x связными компонентами, а отображение их в последовательные элементы множества X даст медленно растущую сюръективную функцию $N\to <!--\; \to \; -->X$$N\to X$ . Также размеры связных компонент дают композицию n в x частейs. Этот довод, по сути, то же, что и в звёздочках и чёрточках, за исключением того, что делается выбор x − 1 «разделителей»

Пример:

$X=\{a,b\},N=\{p,q,r\}$$X=\{a,b\},N=\{p,q,r\}$ , тогда

$\left|\{\{a,a,b\},\{a,b,b\}\}\right|=(\genfrac{}{}{0ex}{}{3-<!--\; -\; -->1}{3-<!--\; -\; -->2})=(\genfrac{}{}{0ex}{}{2}{1})=\frac{2!}{1!\times <!--\; \times \; -->(2-<!--\; -\; -->1)!}=2$$\left\vert \{\{a,a,b\},\{a,b,b\}\}\right\vert ={\binom {3-1}{3-2}}={\binom {2}{1}}={\frac {2!}{1!\times (2-1)!}}=2$ 

Инъективные функции из N в X с точностью до перестановок XПравить

В этом случае мы рассматриваем последовательности n различных элементов из X, но отождествляем функции, полученные одна из другой путём перестановки элементов множества X. Легко видеть, что две различные такие последовательности могут всегда быть отождествлены — перестановка должна отобразить член i первой последовательности в член i второй последовательности, а поскольку значение встречается дважды в обоих последовательностях, это требования не противоречат друг другу. Отображение остаётся переводящим элемент, не встречающийся в первой последовательности в элемент, не встречающийся во второй последовательности. Единственная вещь, которая делает результат зависящим от n и x, это существование таких последовательностей, что выражается в требовании $n⩽<!--\; ⩽\; -->x$$n\leqslant x$  согласно принципу Дирихле. Число перестановок поэтому выражается как $[n⩽<!--\; ⩽\; -->x]$$[n\leqslant x]$  при использовании скобки Айверсона.

Инъективные функции из N в X с точностью до перестановок множеств N и XПравить

Этот случай сводится к предыдущему — поскольку все последовательности n различных элементов из X могут быть преобразованы друг в друга с помощью перестановок множества X, что позволяет переупорядочивать элементы без образования новых сущностей, число остаётся $[n⩽<!--\; ⩽\; -->x]$$[n\leqslant x]$ .

Сюръективные функции из N в X с точностью до перестановки множества XПравить

Этот случай эквивалентен подсчёту разбиений N на x (непустых) подмножеств или подсчёту отношений эквивалентности на N с ровно x классами. Более того, для любой сюръективной функции $N\to <!--\; \to \; -->X$$N\to X$  отношение иметь тот же образ при отображении функцией f является таким отношением эквивалентности и это отношение не меняется при последовательном применении перестановок множества X. В другую сторону, можно превратить такое отношение эквивалентности в сюръективную функцию путём назначения элементам x множества X некоторых классов эквивалентности. Число таких разбиений или отношений эквивалентности равно по определению числу Стирлинга второго рода S(n,x), которое записывается также в виде $\{\genfrac{}{}{0ex}{}{n}{x}\}$$\textstyle \{{n \atop x}\}$ . Значения можно описать с помощью рекуррентного отношения или с помощью произвводящих функций, но, в отличие от биномиальных коэффициентов, не существует выражения в замкнутой форме^[en] для этих чисел, не использующее суммирование.

Сюръективные функции из N в XПравить

Для каждой сюръективной функции $N\to <!--\; \to \; -->X$$N\to X$ , её орбита по перестановкам множества X имеет x! элементов, поскольку композиция (слева) с двумя различными перестановки множества X никогда не дают ту же функцию на N (перестановки должны отличаться на некотором элементе множества X, который всегда может быть записан в виде f(i) для некоторого $i\in <!--\; \in \; -->N$$i\in N$ , и композиции будут тогда отличаться на элементе i). Отсюда следует, что число для этого случая в x! раз больше числа в предыдущем случае, то есть $x!\{\genfrac{}{}{0ex}{}{n}{x}\}.$$\textstyle x!\{{n \atop x}\}.$ 

Пример:

$X=\{a,b\},N=\{p,q,r\}$$X=\{a,b\},N=\{p,q,r\}$ , тогда

$\left|\{(a,a,b),(a,b,a),(a,b,b),(b,b,a),(b,a,b),(b,a,a)\}\right|=2!\{\genfrac{}{}{0ex}{}{3}{2}\}=2\times <!--\; \times \; -->3=6$$\left\vert \{(a,a,b),(a,b,a),(a,b,b),\ (b,b,a),(b,a,b),(b,a,a)\}\right\vert =\textstyle 2!\{{3 \atop 2}\}=2\times 3=6$ 

Функции из N в X с точностью перестановки множества XПравить

Этот случай подобен соответствующему случаю для сюръективных функций, но некоторые элементы x могут не соответствовать любому классу эквивалентности совсем (поскольку рассматриваются функции с точностью до перестановки множества X, не имеет значения, какие элементы рассматриваются, имеет значение лишь сколько). Как следствие, подсчитываются отношения эквивалентности на N с максимум x классами и результат получается из упомянутого случая суммированием по значениям x, что даёт $\underset{k=0}{\overset{x}{\sum <!--\; \sum \; -->}}\{\genfrac{}{}{0ex}{}{n}{k}\}$$\textstyle \sum _{k=0}^{x}\{{n \atop k}\}$ . В случае $x⩾<!--\; ⩾\; -->n$$x\geqslant n$ , размер x не накладывает вообще никаких ограничений и подсчитываются все отношения эквивалентности на множестве из n элементов (эквивалентно, все разбиения такого множества). Поэтому $\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\{\genfrac{}{}{0ex}{}{n}{k}\}$$\textstyle \sum _{k=0}^{n}\{{n \atop k}\}$  даёт выражение для числа Белла B_n.

Сюръективные функции из N в X с точностью до перестановок Nи XПравить

Этот случай эквивалентен подсчёту разбиений числа n на x ненулевых частей. Случай сравним со случаем подсчёта сюръективные функции с точностью до перестановок множества X (только по X, $\{\genfrac{}{}{0ex}{}{n}{x}\}$$\textstyle \{{n \atop x}\}$ ), лишь следует учитывать размеры классов эквивалентности, на которые функция разбивает множество N (включая кратность каждого размера), поскольку два отношения эквивалентности могут быть преобразованы одно в другое перестановкой множества N тогда и только тогда, когда размеры из классов совпадают. Это именно то, что отличает понятие разбиения n от понятия разбиения N, так что результат получаем путём определения числа p_x(n) разбиений n на x ненулевых частей.

Функции из N в X с точностью до перестановки множеств N и XПравить

Этот случай эквивалентен подсчёту разбиений числаn на не более чем x частей. Ассоциация та же, что и в предыдущем случае, включая разбиение части 0 для каждого элемента X, не попавшего в образ функции. Каждое разбиение числа n на максимум x ненулевых частей может быть расширено до такого разбиения путём добавления необходимого числа нулей и это подсчитывается для всех возможностей ровно раз, так что результат задаётся формулой $\underset{k=0}{\overset{x}{\sum <!--\; \sum \; -->}}{p}_k(n)$$\textstyle \sum _{k=0}^{x}p_{k}(n)$ . При добавлении единицы к каждой из x частей получаем разбиение n + x на x ненулевых частей и это соответствие биективно. Следовательно, выражение может быть упрощено до записи $p_x(n+x)$$p_{x}(n+x)$  (правда, это изменение не делают вычисления проще).

Экстремальные случаиПравить

Вышеприведённые формулы дают соответствующие значения для всех конечных множеств N и X. В некоторых случаях имеются альтернативные формулы, которые почти эквивалентны, но которые не дают правильный результат в некоторых экстремальных случаях, например, при пустом N или X. Следует учитывать в этих случаях следующее.

• Для любого множества X существует ровно одна функция из пустого множества в X (не существует значений у этой функции), которая всегда инъективна, но никогда не сюръективна, за исключением случая, когда и X (также) пусто.
• Для любого непустого множества N не существует функции из N в пустое множество (нужно, чтобы имелось хотя бы одно значение функции, а его нет).
• Когда $n>x$$n>x$ , нет инъективной функции $N\to <!--\; \to \; -->X$$N\to X$ , а если $n<x$ , нет сюръективных функций $N\to <!--\; \to \; -->X$$N\to X$ .
• Выражения, используемые в формулах, имеют конкретные величины

$0^0=0^{\underset{\_<!--\; \_\; -->}{0}}=0!=(\genfrac{}{}{0ex}{}{0}{0})=(\genfrac{}{}{0ex}{}{-<!--\; -\; -->1}{0})=\left\{\genfrac{}{}{0ex}{}{0}{0}\right\}=p_0(0)=1$$0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1$ 

(первые три являются представителями пустого произведения^[en], а значение $(\genfrac{}{}{0ex}{}{-<!--\; -\; -->1}{0})=\frac{(-<!--\; -\; -->1{)}^{\underset{\_<!--\; \_\; -->}{0}}}{0!}=1$$\scriptstyle {\tbinom {-1}{0}}={\frac {(-1)^{\underline {0}}}{0!}}=1$  определяется повсеместно принятым расширением биномиальных коэффициентов на произвольные значения верхнего индекса), в то время как

$\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}=p_x(n)=0$$\left\{{n \atop x}\right\}=p_{x}(n)=0$  когда либо $n>0=x$$n>0=x$ , либо $0\leqslant n<x.$ 

В частности, для случая подсчёта мультимножеств с n элементами, выбранными из X, приведённое выражение $(\genfrac{}{}{0ex}{}{n+x-<!--\; -\; -->1}{n})$${\tbinom {n+x-1}{n}}$  эквивалентно в большинстве случаев $(\genfrac{}{}{0ex}{}{n+x-<!--\; -\; -->1}{x-<!--\; -\; -->1})$${\tbinom {n+x-1}{x-1}}$ , но последнее выражение даёт 0 в случае $n=x=0$$n=x=0$  (при обычном соглашении, что биномиальные коэффициенты с отрицательным нижним индексом всегда равны 0). Аналогично, для случая подсчёта композиций числа n с x ненулевыми частями, приведённое выражение $(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{n-<!--\; -\; -->x})$${\tbinom {n-1}{n-x}}$  почти эквивалентно выражению $(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{x-<!--\; -\; -->1})$${\tbinom {n-1}{x-1}}$ , которое даёт подход звёздочки и чёрточки argument, но в последнем случае получаем неверный результат для $n=0$$n=0$  и всех значениях x. Для случаев, где результат вовлекает суммирование, а именно, при подсчёте разбиений N на максимум x непустых подмножеств или разбиений n на максимум x ненулевых частей, индекс суммирования начинается с 0, хотя соответствующий член равен нулю для всех $n>0$$n>0$  и он становится ненулевым, когда $n=0$$n=0$ . В случае $n=0$$n=0$  результат станет неверным, если начинать суммирование с 1.

ОбобщенияПравить

Мы можем обобщить далее, позволив другим группам перестановок действовать на N и X. Если G является группой перестановок множества N, а H — группой перестановок множества X, то мы подсчитываем классы эквивалентности функций $f:<!--\; :\; -->N\to <!--\; \to \; -->X$$f\colon N\to X$ . Две функции $f$$f$  и $F$$F$  считаются эквивалентными тогда и только тогда, когда существуют $g\in <!--\; \in \; -->G,h\in <!--\; \in \; -->H$$g\in G,h\in H$ , такие, что $F=h\circ <!--\; \circ \; -->f\circ <!--\; \circ \; -->g$$F=h\circ f\circ g$ . Это расширение ведёт к понятиям, таким как циклическая и диэдральная перестановки, а также к циклическим и диэдральным разбиениям чисел и множеств.

Двадцатиричный путьПравить

Другое обобщение, названное двадцатиричный путь, разработал Кеннет П. Богарт в своей книге «Combinatorics Through Guided Discovery» (Комбинаторика путём направляемых открытий). В задаче распределения объектов по ящикам объекты и ящики могут считаться неразличимыми или различными. Богарт различал 20 случаев.

Двадцатиричный путь

n объектов и условия, как они получаются	x получателей и математическая модель распределения
Различные	Одинаковые
1. Различные Нет условий	n-последовательности в X $x^n$$x^n$	разбиение N на $⩽<!--\; ⩽\; -->x$$\leqslant x$  подмножеств $\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}\left\{\genfrac{}{}{0ex}{}{x}{i}\right\}$$\sum _{i=0}^{n}\left\{{x \atop i}\right\}$
2. Различные Каждый выбирается не более раза	n-перестановки множества X $x^{\underset{\_<!--\; \_\; -->}{n}}$$x^{\underline {n}}$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases}}$
3. Различные Каждый выбирается не менее раза	композиции N с x подмножествами $x!\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$$x!\left\{{n \atop x}\right\}$	разбиение N на x подмножеств $\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$$\left\{{n \atop x}\right\}$
4. Различные Каждый выбирается ровно раз	$n!=x!$$n!=x!$  перестановок	$1{\begin{cases}1&n=x\\0&n\neq x\end{cases}}$
5. Различные, порядок учитывается	$(n+x-<!--\; -\; -->1{)}^{\underset{\_<!--\; \_\; -->}{n}}$$(n+x-1)^{\underline {n}}$  упорядоченных функций	$\underset{i=1}{\overset{x}{\sum <!--\; \sum \; -->}}L(n,i)$$\sum _{i=1}^{x}L(n,i)$  разорванных перестановок (на $⩽<!--\; ⩽\; -->x$$\leqslant x$  частей) Где $L(n,i)$$L(n,i)$  является числом Лаха
6. Различные, порядок учитывается Каждый выбирается не менее раза	$(n{)}^{\underset{\_<!--\; \_\; -->}{x}}(n-<!--\; -\; -->1{)}^{\underset{\_<!--\; \_\; -->}{n-<!--\; -\; -->x}}$$(n)^{\underline {x}}(n-1)^{\underline {n-x}}$  упорядоченных в функциях	$L(n,x)=\left(\genfrac{}{}{0ex}{}{n}{x}\right)(n-<!--\; -\; -->1{)}^{\underset{\_<!--\; \_\; -->}{n-<!--\; -\; -->x}}$$L(n,x)=\left({n \atop x}\right)(n-1)^{\underline {n-x}}$  разорванных перестановок (на x частей) где $L(n,x)$$L(n,x)$  является числом Лаха
7. Одинаковые Нет условий	n-мультимножеств множества X $\left(\genfrac{}{}{0ex}{}{x+n-<!--\; -\; -->1}{n}\right)$$\left({x+n-1 \atop n}\right)$	$\underset{i=1}{\overset{x}{\sum <!--\; \sum \; -->}}{p}_i(n)$$\sum _{i=1}^{x}p_{i}(n)$  число разбиений (на $⩽<!--\; ⩽\; -->x$$\leqslant x$  частей)
8. Одинаковые Каждый выбирается не более раза	n-подмножеств множества X $\left(\genfrac{}{}{0ex}{}{x}{n}\right)$$\left({x \atop n}\right)$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases}}$
9. Одинаковые Каждый выбирается не менее раза	$\left(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{x-<!--\; -\; -->1}\right)$$\left({n-1 \atop x-1}\right)$  композиций (x частей)	разбиение n на x частей $p_x(n)$$p_{x}(n)$
10. Одинаковые Каждый выбирается ровно раз	${\begin{cases}1&n=x\\0&n\neq x\end{cases}}$	${\begin{cases}1&n=x;\\0&n\neq x\end{cases}}$