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

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

Обзор

Пусть N и X — конечные множества . Позволять $n=|N|$ и $x=|X|$ — мощности множеств. Таким образом, N — это набор из n элементов, а X — набор из x элементов.

— это перечисление классов эквивалентности функций Общая задача, которую мы рассматриваем , $f:N\to X$.

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

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

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

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

• равенство;
• равенство до перестановки точностью N ; с
• равенство с точностью до перестановки X ;
• равенство с точностью до перестановок N и X .

Три условия на функции и четыре отношения эквивалентности можно соединить 3 × 4 = 12 способами.

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

Включение классических задач перечисления в эту постановку заключается в следующем.

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

Точки зрения

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

Мячи и коробки

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

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

Выборка

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

Второе различие между схемами выборки заключается в том, имеет ли значение порядок выборки. Например, если у нас есть десять предметов, из которых мы выбираем два, то выбор (4, 7) отличается от (7, 4), если порядок имеет значение; с другой стороны, если порядок не имеет значения, то варианты (4, 7) и (7, 4) эквивалентны.

Первые две строки и столбцы таблицы ниже соответствуют выборке с заменой и без нее, с учетом порядка и без него. Случаи отбора проб с заменой указаны в графе «Любые». $f$", а случаи отбора проб без замещения - в графе "Инъекционная". $f$". Случаи, когда порядок имеет значение, находятся в строке с надписью "Различные", а случаи, когда порядок не имеет значения, находятся в строке с надписью " S _n орбиты". Каждая запись таблицы указывает, сколько существует различных наборов вариантов, в конкретной схеме выборки три из этих записей таблицы также соответствуют распределениям вероятностей . Выборка с заменой, где порядок имеет значение, сравнима с описанием совместного распределения N отдельных случайных величин , каждая из которых имеет X -кратное категориальное распределение . не имеет значения, однако сравнимо с описанием одного полиномиального распределения N , взятого из X -кратной категории, где имеет значение только количество наблюдаемых каждой категории. Выборка без замены, где порядок не имеет значения, сравнима с одним многомерным гипергеометрическим распределением. Выборка без замены, где порядок имеет значение, похоже, не соответствует распределению вероятностей. Во всех инъективных случаях (выборка без замены) количество наборов вариантов выбора равно нулю, если только N ≤ X . («Сравнимость» в приведенных выше случаях означает, что каждый элемент выборочного пространства соответствующего распределения соответствует отдельному набору вариантов выбора, и, следовательно, число в соответствующем поле указывает размер выборочного пространства для данного распределения.)

С точки зрения выборки столбец с надписью «Сюръективный $f$" несколько странно: по сути, мы продолжаем выборку с заменой до тех пор, пока не выберем каждый элемент хотя бы один раз. Затем мы подсчитываем, сколько вариантов мы сделали, и если оно не равно N , выбрасываем весь набор и повторяем. Это можно отчасти сравнить с проблемой коллекционера купонов , где процесс включает в себя «сбор» (путем выборки с заменой) набора из X купонов до тех пор, пока каждый купон не будет увиден хотя бы один раз. Во всех сюръективных случаях количество наборов вариантов выбора равно. ноль, если N ≥ X. только

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

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

• функция $f$ помечает каждый элемент N элементом X .
• функция $f$ выбирает (выбирает) элемент множества X для каждого элемента N , всего n вариантов.
• функция $f$ группирует элементы N вместе, которые отображаются на один и тот же элемент X .

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

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

При просмотре $f$ В качестве маркировки элементов N последние можно рассматривать как расположенные в последовательности, а метки из X - как последовательно присвоенные им. Требование, чтобы $f$ быть инъективным означает, что ни один ярлык не может быть использован второй раз; результатом является последовательность меток без повторений . При отсутствии такого требования используется терминология «последовательности с повторением», означающая, что метки могут использоваться более одного раза (хотя допускаются и последовательности, оказавшиеся без повторения).

При просмотре $f$ к неупорядоченному выбору элементов X применимо такое же различие. Если $f$ должно быть инъективным, тогда выборка должна включать n различных элементов X , поэтому это подмножество X размера n , также называемое n - комбинацией . Без требования один и тот же элемент X может встречаться в выборке несколько раз, и в результате получается мультимножество размера n элементов из X , называемое также n - мультикомбинацией или n -комбинацией с повторением.

Требование, чтобы $f$ быть сюръективным с точки зрения маркировки элементов N означает, что каждая метка должна использоваться хотя бы один раз; с точки зрения выбора из X это означает, что каждый элемент X должен быть включен в выборку хотя бы один раз. Маркировка сюръекцией эквивалентна группировке элементов N с последующей маркировкой каждой группы элементом X и, соответственно, ее несколько сложнее описать математически.

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

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

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

Формулы

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

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

$f$-сорт	Любой $f$	инъективный $f$	Сюръективный $f$
Отчетливый ж	n -последовательность в X $x^{n}$	n -перестановка X $x^{\underline {n}}$	композиция N с X подмножествами $x!\left\{{n \atop x}\right\}$
S n орбиты е ∘ С н	n -мультисубмножество X ${\binom {x+n-1}{n}}$	n -подмножество X ${\binom {x}{n}}$	композиция n с x членами ${\binom {n-1}{n-x}}$
S x орбиты С х ∘ ж	разделение N ≤ x на подмножества $\sum _{k=0}^{x}\left\{{n \atop k}\right\}$	разбиение N на ≤ x элементы $[n\leq x]$	разделение N на x подмножеств $\left\{{n \atop x}\right\}$
S n × S x орбиты S Икс ∘ ж ∘ S п	разбиение n на ≤ x частей $p_{x}(n+x)$	разбиение n на ≤ x частей 1 $[n\leq x]$	разбить n на x частей $p_{x}(n)$

Конкретные используемые обозначения:

• падающая факторная мощность ${\textstyle x^{\underline {n}}={\frac {x!}{(x-n)!}}=x(x-1)(x-2)\cdots (x-n+1)}$,
• растущая факторная власть ${\textstyle x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$,
• факториал ​ ${\textstyle n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1}$
• число Стирлинга второго рода ${\textstyle \left\{{n \atop k}\right\}}$, обозначающий количество способов разбить набор из n элементов на k непустые подмножества
• биномиальный коэффициент ${\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$
• скобка Айверсона [] кодирует значение истинности как 0 или 1
• число ${\textstyle p_{k}(n)}$ разбиений ​ n ​ на k частей

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

Это краткое изложение того, что означают различные случаи. Подробно случаи описаны ниже.

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

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

Любая ж

После того, как мы выбрали предмет, мы кладем его обратно, чтобы иметь возможность выбрать его снова.

Инъективное ф

Выбрав предмет, мы откладываем его в сторону и не можем выбрать его снова; следовательно, мы получим n различных элементов. Тогда обязательно, если только $n\leq x$, никакие списки вообще не могут быть выбраны.

Сюръективное f

После того, как мы выбрали предмет, мы кладем его обратно, чтобы мы могли выбрать его снова, но в конце концов мы должны выбрать каждый предмет хотя бы один раз. Тогда обязательно, если только $n\geq x$, никакие списки вообще не могут быть выбраны.

И строки означают:

Отчетливый

Оставьте списки в покое; посчитайте их напрямую.

S _n орбиты

Перед подсчетом отсортируйте списки по номеру выбранных элементов, чтобы порядок не имел значения, например, (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) .

S _n × S _x орбиты

Два списка считаются одинаковыми, если их можно переупорядочить и пометить, как указано выше, и получить один и тот же результат. Например, (3, 5, 3) и (2, 9, 9) считаются одинаковыми, поскольку их можно переупорядочить как (3, 3, 5) и (9, 9, 2), а затем перемаркировка обоих приведет к одинаковому результату. список (1, 1, 2).

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

Таблица ниже аналогична таблице выше, но вместо показа формул она дает интуитивное понимание их значения на знакомом примере с шариками и коробками. Ряды обозначают различимость шаров и коробок. В столбцах указано, разрешены ли мультиупаковки (более одного мяча в одной коробке) или пустые коробки. Ячейки диаграммы показывают вопрос, на который можно ответить путем решения формулы, приведенной в таблице формул выше.

Таблица из 12 комбинаторных объектов – интуитивная диаграмма с использованием шариков и коробочек

	Любая ж (нет правил по размещению)	Инъективное ф (комплексная упаковка не допускается)	Сюръективное f (пустые коробки запрещены)
ж (Шарики и коробки отмечены)	n -последовательность в X Сколькими способами вы можете разместить n отмеченных шаров в x отмеченных ящиков, без каких-либо других правил по размещению?	n -перестановка в X Сколькими способами вы можете разместить n отмеченных шаров в x отмеченных ящиков, без каких-либо мультипаков?	композиция N с x подмножествами Сколькими способами вы можете разместить n отмеченных шаров в x отмеченных ящиков, без пустых коробок?
е ∘ С н (Шарики простые, коробки отмечены)	n -мультисубмножество X Сколькими способами вы можете разместить n простых шаров в x отмеченных коробок, без каких-либо других правил по размещению?	n -подмножество X Сколькими способами вы можете разместить n простых шаров в x отмеченных коробок, без каких-либо мультипаков?	композиция n с x членами Сколькими способами вы можете разместить n простых шаров в x отмеченных коробок, без пустых коробок?
С х ∘ ж (Шарики отмечены, коробки простые)	разделение N ≤ x на подмножества Сколькими способами вы можете разместить n размеченных шаров в x простых коробок, без каких-либо других правил по размещению?	разбиение N на ≤ x элементы Сколькими способами вы можете разместить n размеченных шаров в x простых коробок, без каких-либо мультипаков?	разделение N на x подмножеств Сколькими способами вы можете разместить n размеченных шаров в x простых коробок, без пустых коробок?
С Икс ∘ Икс ∘ С п (Шарики и коробки простые)	разбиение n на ≤ x частей Сколькими способами вы можете разместить n простых шариков в x простых коробок, без каких-либо других правил по размещению?	разбиение n на ≤ x частей 1 Сколькими способами вы можете разместить n простых шариков в x простых коробок, без каких-либо мультипаков?	разбить n на x частей Сколькими способами вы можете разместить n простых шариков в x простых коробок, без пустых коробок?

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

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

Функции от N до X

Этот случай эквивалентен подсчету последовательностей из n элементов X , каждый из которых может без ограничений: функция f : N → X определяется n образами элементов N быть независимо выбран среди элементов x . Это дает в общей сложности х ^н возможности.

Пример:

$X=\{a,b,c\},N=\{1,2\}{\text{, then }}$

$\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^{\underline {n}}=x(x-1)\cdots (x-n+1).$

Обратите внимание, что если n > x нет , то получается нулевой фактор, поэтому в этом случае инъективных функций N → X вообще ; это всего лишь повторение принципа «ячейки» .

Пример:

$X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}$

$\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 . Это число известно как биномиальный коэффициент ${\tbinom {x}{n}}$, что, следовательно, определяется выражением

${\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\}{\text{, then }}$

$\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 → X, здесь бесполезна, поскольку число их, сгруппированных перестановками N, варьируется от одной функции к другой. Скорее, как поясняется в разделе «Комбинации» , количество n -мультикомбинаций из набора с элементами x можно считать таким же, как количество n -комбинаций из набора с элементами x + n - 1 . Это сводит проблему к другой двенадцатикратным образом и дает в результате

${\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=\{1,2\}{\text{, then }}$

$\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 , результат будет

${\binom {n-1}{n-x}}.$

Обратите внимание, что когда n < x, вообще нет сюръективных функций N → X (своего рода принцип «пустой ячейки»); это учитывается в формуле по соглашению, согласно которому биномиальные коэффициенты всегда равны 0, если нижний индекс отрицательный. То же значение дает и выражение

${\binom {n-1}{x-1}},$

за исключением крайнего случая n = x = 0 , где первое выражение правильно дает ${\tbinom {-1}{0}}=1$, а последний неверно дает ${\tbinom {-1}{-1}}=0$.

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

Пример:

$X=\{a,b\},N=\{1,2,3\}{\text{, then }}$

$\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\leq x]$, используя скобку Айверсона .

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

Этот случай сводится к предыдущему: поскольку все последовательности из n различных элементов из X уже могут быть преобразованы друг в друга путем применения перестановки X к каждому из их термов, разрешение переупорядочения термов не дает никаких новых идентификаций; номер остается $[n\leq x]$.

функции от N до X до X

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

Сюръективные функции от N до X

Для каждой сюръективной функции f : N → X ее орбита при перестановках X имеет x ! элементов, поскольку композиция (слева) с двумя различными перестановками X никогда не дает одну и ту же функцию на N (перестановки должны различаться в каком-то элементе X , что всегда можно записать как $f(i)$ для некоторого i ∈ N , и тогда композиции будут различаться в точках i ). Отсюда следует, что число для этого случая равно x ! раз больше числа для предыдущего случая, то есть $\textstyle x!\{{n \atop x}\}.$

Пример:

$X=\{a,b\},N=\{1,2,3\}{\text{, then }}$

$\left\vert \{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \atop 2}\right\}=2\times 3=6$

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

Этот случай аналогичен соответствующему случаю для сюръективных функций, но некоторые элементы x могут вообще не соответствовать какому-либо классу эквивалентности (поскольку рассматриваются функции с точностью до перестановки X , не имеет значения, какие элементы задействованы, а сколько) . Как следствие, подсчитываются отношения эквивалентности на N с не более чем x классами, а результат в указанном случае получается суммированием по значениям до x , что дает $\textstyle \sum _{k=0}^{x}\{{n \atop k}\}$. В случае x ≥ n размер x вообще не накладывает ограничений, и учитываются все отношения эквивалентности на наборе из n элементов (эквивалентно всем разделам такого набора); поэтому $\textstyle \sum _{k=0}^{n}\{{n \atop k}\}$ дает выражение для числа Белла B _n .

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

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

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

Этот случай эквивалентен подсчету разбиений числа n на ≤ x частей . Связь такая же, как и в предыдущем случае, за исключением того, что теперь некоторые части разбиения могут быть равны 0. (В частности, они соответствуют элементам X, не входящим в образ функции.) Каждое разбиение n не более чем на x можно расширить до такого раздела, добавив необходимое количество нулей, и это учитывает все возможности ровно один раз, поэтому результат определяется выражением ненулевые части $\textstyle \sum _{k=0}^{x}p_{k}(n)$. Добавляя 1 к каждой из частей x , можно получить разбиение n + x на x ненулевых частей, и это соответствие является биективным; следовательно, данное выражение можно упростить, записав его как $p_{x}(n+x)$.

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

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

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

$0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1$

(первые три — это экземпляры пустого товара , а значение ${\tbinom {-1}{0}}={\tfrac {(-1)^{\underline {0}}}{0!}}=1$ задается обычным расширением биномиальных коэффициентов до произвольных значений верхнего индекса), а

$\left\{{n \atop x}\right\}=p_{x}(n)=0\quad {\hbox{whenever either }}n>0=x{\hbox{ or }}0\leq n<x.$

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

Обобщения

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

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

Другое обобщение, названное двадцатикратным путем, было развито Кеннетом П. Богартом в его книге «Комбинаторика через управляемое открытие». В задаче о распределении объектов по ящикам как объекты, так и ящики могут быть одинаковыми или разными. Богарт идентифицирует 20 случаев. Роберт А. Проктор сконструировал тридцатикратный путь.

Двадцатикратный путь; модели распределения n объектов среди x получателей

№	Объекты	Состояние распределения	Получатели
			Отчетливый	Идентичный
1	Отчетливый	Нет ограничений	n -последовательность в X $x^{n}$	разделение N ≤ x на подмножества $\sum _{i=0}^{x}\left\{{n \atop i}\right\}$
2		Максимум по одному	n -перестановка X $x^{\underline {n}}$	${\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}$
3		Хотя бы по одному каждому	композиция N с x подмножествами $x!\left\{{n \atop x}\right\}$	разделение N на x подмножеств $\left\{{n \atop x}\right\}$
4		Ровно по одному	$n!=x!$ перестановки	${\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}$
5	Отчетливый, заказал	Нет ограничений	$x^{\overline {n}}$ упорядоченные функции	$\sum _{i=1}^{x}L(n,i)$ сломанные перестановки ( $\leq x$ части) Где $L(n,i)$ это число Лаха
6		Хотя бы по одному каждому	$(n)^{\underline {x}}(n-1)^{\underline {n-x}}$ упорядочен по функциям	$L(n,x)=\left({n \atop x}\right)(n-1)^{\underline {n-x}}$ сломанные перестановки ( x частей) Где $L(n,x)$ это число Лаха
7	Идентичный	Нет ограничений	n -мультисубмножество X $\left({x+n-1 \atop n}\right)$	$\sum _{i=1}^{x}p_{i}(n)$ числовые разделы ( $\leq x$ части)
8		Максимум по одному	n -подмножество X $\left({x \atop n}\right)$	${\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}$
9		Хотя бы по одному каждому	$\left({n-1 \atop x-1}\right)$ композиции ( х частей)	разбить n на x частей $p_{x}(n)$
10		Ровно по одному	${\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}$	${\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}$

См. также

• Звезды и полосы (комбинаторика)