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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Обзор [ править ]

Пусть $N$ и $X$ - конечные множества . Позвольте и быть мощностью множеств. Таким образом, $N$ - это $n$ -множество, а $X$ - это $x$ -множество. ${\ Displaystyle п = | N |}$ ${\ displaystyle x = | X |}$

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

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

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

(Условие « $е$ является взаимно однозначным » только вариант , когда , но тогда это эквивалентно как « $е$ инъективна» и « $е$ сюръективна».) ${\ Displaystyle п = х}$

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

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

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

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

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

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

Точки обзора [ править ]

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

Шары и коробки [ править ]

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

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

Выборка [ править ]

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

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

Первые две строки и столбцы нижеприведенной таблицы соответствуют выборке с заменой и без нее, с учетом и без учета порядка. Случаи выборки с заменой указаны в столбце «Любое f », а случаи выборки без замены - в столбце «Injective f ». Случаи, когда порядок имеет значение, находятся в строке с меткой «Отдельно», а случаи, когда порядок не имеет значения, находятся в строке с меткой «S _n орбит». Каждая запись в таблице указывает, сколько существует различных наборов вариантов в конкретной схеме выборки. Три из этих записей таблицы также соответствуют распределениям вероятностей. Отбор проб с заменой , где заказе вопросы сопоставимо с описывающим совместным распределением из N разделения случайных величин , каждая из которых имеет X - кратный категориальное распределение . Отбор проб с заменой , где порядок не имеет значения, однако, сравнимо с описания одного полиномиальное распределение из N черпает из X категории кратном, где только число видели в каждой категории вопросов. Выборка без замены, где порядок не имеет значения, сравним с одним многомерным гипергеометрическим распределением.. Выборка без замены, когда порядок имеет значение, не соответствует распределению вероятностей. ^[2] Обратите внимание, что во всех «инъективных» случаях (т.е. выборка без замены) количество наборов вариантов равно нулю, если только $N \leq X$ . («Сопоставимый» в приведенных выше случаях означает, что каждый элемент пространства выборки соответствующего распределения соответствует отдельному набору вариантов, и, следовательно, число в соответствующем поле указывает размер пространства выборки для данного распределения.)

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

Маркировка, выбор, группировка [ править ]

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

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

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

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

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

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

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

Разделы наборов и чисел [ править ]

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

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

Формулы [ править ]

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

Двенадцать комбинаторных объектов и формулы их перечисления.
f -класс	Любой f	Инъективная f	Сюръективный f
Отличный $f$	n -последовательность в X Икс п {\ Displaystyle х ^ {п}}	n -перестановка X Икс п _ {\ Displaystyle х ^ {\ подчеркивание {п}}}	композиция N с x подмножествами Икс ! { п Икс } {\ Displaystyle \ textstyle х! \ {{п \ на вершине х} \}}
S _n орбиты $f \circ S n$	n -многоподмножество X ( Икс + п - 1 п ) {\ Displaystyle {\ binom {х + п-1} {п}}}	n -подмножество X ( Икс п ) {\ displaystyle {\ binom {x} {n}}}	композиция n с x членами ( п - 1 п - Икс ) {\ displaystyle {\ binom {n-1} {nx}}}
S _x орбиты $S x \circ f$	разбиение N на ≤ x подмножеств ∑ k знак равно 0 Икс { п k } {\ Displaystyle \ сумма _ {к = 0} ^ {х} \ влево \ {{п \ на вершине к} \ вправо \}}	разбиение N на ≤ x элементов [ п ≤ Икс ] {\ Displaystyle [п \ Leq х]}	разбиение N на x подмножеств { п Икс } {\ Displaystyle \ влево \ {{п \ на вершине х} \ вправо \}}
S _n × S _x орбиты $S x \circ f \circ S n$	разбиение n на ≤ x частей п Икс ( п + Икс ) {\displaystyle p_{x}(n+x)}	разбиение n на ≤ x частей 1 [ n ≤ x ] {\displaystyle [n\leq x]}	разделение n на x частей p x ( n ) {\displaystyle p_{x}(n)}

В частности, используются следующие обозначения:

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

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

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

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

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

Любой f : после того, как мы выбрали элемент, мы возвращаем его, чтобы мы могли выбрать его снова.
Injective f : после того, как мы выбрали элемент, мы откладываем его в сторону, поэтому мы не можем выбрать его снова; следовательно, мы получим 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 орбиты: перед подсчетом отсортируйте списки и затем измените их нумерацию, как описано выше. (Примечание: при изменении нумерации и затем сортировке в некоторых случаях создаются разные списки, но количество возможных списков не меняется.)

Подробная информация о различных случаях [ править ]

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

Функции от N до X [ править ]

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

Пример:
$X=\{a,b,c\},N=\{p,q\}{\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 [ править ]

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

x^{\underline {n}}=x(x-1)\cdots (x-n+1).

Заметим, что если $n > x,$ то получается нулевой множитель, так что в этом случае инъективных функций $N \to 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 [ править ]

Этот случай эквивалентен счетных подмножеств с п элементов из X , называемый также п -combinations из X : среди последовательностей п различных элементов X , те , которые отличаются только в порядке их точки идентифицируются перестановок N . Поскольку во всех случаях эти группы вместе составляют ровно n ! различных последовательностей, мы можем разделить количество таких последовательностей на n ! чтобы получить число п -combinations из 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 . Формула подсчета всех функций $N \to 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=\{p,q\}{\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 встречается хотя бы один раз. Это также эквивалентно подсчет композиций по п с й (ненулевым) выражением , путем перечисления кратности элементов х в порядке. Соответствие между функциями и мультимножествами такое же, как и в предыдущем случае, а требование сюръективности означает, что все кратности равны по крайней мере единице. Уменьшая все кратности на 1, это сводится к предыдущему случаю; так как изменение уменьшает значение n на x , результат

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

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

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

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

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

Пример:
$X=\{a,b\},N=\{p,q,r\}{\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 [ править ]

В этом случае мы рассмотрим последовательность п различных элементы из X , но определить, полученные от друга друга, применяя к каждому элементу перестановки X . Легко видеть, что всегда можно идентифицировать две разные такие последовательности: перестановка должна отображать член i первой последовательности в член i второй последовательности, и, поскольку ни одно значение не встречается дважды в любой последовательности, эти требования не противоречат друг другу; остается сопоставить элементы, не встречающиеся в первой последовательности, биективно с элементами, не встречающимися во второй последовательности, произвольным образом. Единственный факт, который заставляет результат зависеть от n и xвообще то, что для существования любых таких последовательностей с самого начала требуется $n \leq x$ , по принципу «голубятни». Таким образом, число выражается как , используя скобку Айверсона . $[n\leq x]$

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

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

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

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

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

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

Пример:
$X=\{a,b\},N=\{p,q,r\}{\text{, then }}$
$\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 , давая . В случае, если x ≥ n , размер x не накладывает никаких ограничений, и учитываются все $\textstyle \sum _{k=0}^{x}\{{n \atop k}\}$ отношения эквивалентности на множестве из n элементов (что эквивалентно всем разбиениям такого множества); поэтому дает выражение для числа Белла B _n . $\textstyle \sum _{k=0}^{n}\{{n \atop k}\}$

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

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

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

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

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

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

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

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

Обобщения [ править ]

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

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

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

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

Ссылки [ править ]

^ Ричард П. Стэнли (1997). Перечислительная комбинаторика, Том I . Издательство Кембриджского университета. ISBN 0-521-66351-2 . стр.41
^ Роберт В. Хогг и Эллиот А. Танис (2001). Вероятность и статистический вывод . ISBN Prentice-Hall, Inc. 0-13-027294-9 . стр.81
^ Кеннет П. Богарт (2004). Комбинаторика через управляемое открытие , стр.57

[1] Ричард П. Стэнли (1997). Перечислительная комбинаторика, Том I . Издательство Кембриджского университета. ISBN 0-521-66351-2 . стр.41

[2] Роберт В. Хогг и Эллиот А. Танис (2001). Вероятность и статистический вывод . ISBN Prentice-Hall, Inc. 0-13-027294-9 . стр.81

[3] Кеннет П. Богарт (2004). Комбинаторика через управляемое открытие , стр.57

[1]