В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 2
Текст из файла (страница 2)
Помимо аксиом 1, 2, 3 и 4 может оказаться также, чтоxρ y & xρ z ⇒ y = x. Если рассматривать бинарное отношение как функцию f , ставящую в соответствие множеству Xнекоторое другое множество D f , то в этом случае она будет инъективной. Область определения f : X → Y совпадает сX, область значений в то же время не обязательно совпадает с Y . В случае X = Y и D f = X при конечных множествах fвзаимно однозначна. На функции распространяются определенные на бинарных отношениях композиции и обратныеэлементы. Таким образом, появляется связь комбинаторных чисел с функциями.Часто бывает удобным исследовать не саму комбинаторную конфигурацию, а в некотором роде изоморфную ей. Стем, чтобы сделать это рассмотрение корректным, сформулируем принцип взаимно однозначного соответствия.Если одному множеству комбинаторных конфигураций с определенными свойствами изоморфно относительно этихсвойств ставится в соответствие другое множество комбинаторных конфигураций, то число комбинаций, обладающихопределенными свойствами в обоих множествах одно и то же.1.1Простейшие комбинаторные числаПусть X = {1, 2, .
. . , n} ,Y = {y1 , . . . , ym }. Множество всех отображений множества X во множество Y обозначается Y X .Оно имеет мощность mn . Это множество изоморфно множеству раскладок n шаров, помеченных числами 1, . . . , n по mящикам, помеченным элементами y1 , . . . , ym , также оно изоморфно множеству слов yi1 yi2 . . . yin длины n в алфавите Y .Отображение f называется инъективным, если i 6= j & i → ys , j → y` ⇒ ys 6= y` .
Для того, чтобы отображение былоинъективно, очевидно, необходимо, чтобы |X| 6 |Y |, то есть n 6 m. Число инъективных отображений равно убывающему факториалу [m]n = m (m − 1) (m − 2) · · · (m − n + 1). В терминах шаров и ящиков этому множеству соответствуетмножество раскладок n различимых шаров по m различимым ящикам так, чтобы в каждом ящике было бы не болееодного шара. В терминах слов в алфавите Y этому множеству соответствует множество слов длины n в алфавите Y ,все буквы в котором различны. Отображение f называется сюръективным, если R f = Y , то есть каждый элементиз Y имеет хотя бы один прообраз. Для того, чтобы отображение было сюръективным, очевидно, необходимо, чтобы|X| > |Y |.
По принципу взаимно однозначного соответствия этой комбинаторной конфигурации соответствует множество раскладок n различимых шаров по m различимым ящикам так, чтобы в каждом ящике оказалось хотя бы по одномушару или множество слов длины n в алфавите из m букв таких, что каждая буква алфавита присутствует в слове хотябы один раз. Число сюръективных отображений X в Y равно mn · m! · mn−m . Отображение, являющееся одновременно сюръективным и инъективным, называется биективным (взаимно однозначным, биекцией). Для того, чтобыотображение было биективным, очевидно, необходимо, чтобы |X| = |Y |.
В случае конечных множеств следующие триутверждения эквивалентны:1. f биективно;2. f сюръективно и |X| = |Y |;3. f инъективно и |X| = |Y |.51.1. ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛАОпределение 1.1.1. Биективные отображения конечных множеств в себя называются перестановками.Введем бинарное отношение на множестве инъективных отображений: fρ g ⇔ R f = Rg .XA B B A B B AU BN BN R f = nYОчевидно, это будет являться отношением эквивалентности.
Оно разбивает все множество инъективных отображенийна n! классов эквивалентности. В силу свойств фактормножества, его мощность будет равна биномиальному коэф[m]m!= Cmn = mn . По принципу взаимно однозначного соответствия вышеописанное фактормножефициенту n!n = n!(m−n)!ство эквивалентно множеству n-элементных подмножеств m-элементного множества или множеству наборов из нулейи единиц длины m ровно с n единицами.Этот результат можно обобщить, если допустить вхождение элементов в подмножество с кратностью.
Мультимножеством называется множество, у каждого элемента которого есть кратность — натуральное число, символизирующее количество вхождений данного элемента в мультимножество. Мощностью мультимножества называетсясумма кратностей всех его элементов. Иными словами необходимо найти число мультиподмножеств мощности n множества Y, |Y | = m. Используя принцип взаимно однозначного соответствия, подсчет можно перенести на наборы целыхнеотрицательных чисел:α1 + α2 + · · · + αm = n,(1.1)αi > 0, αi ∈ Z, i = 1, m.Число различных решений этой системы и будет равно числу мультиподмножеств мощности n множества мощностиm.
Число решений в данном случае будет также являться биномиальным коэффициентом. Действительно, применяяпринцип взаимно однозначного соответствия, можнокаждому решению (α1 , . . . , αm ) взаимно однозначно поставить всоответствие набор длины n+m−1 из нулей и единиц 1| .{z. . 1} 0 1| .{z. . 1} 0 . . . 0 1| .{z. . 1}. Таким образом, число решений равноα1α2αmчислу наборов указанной длины с m − 1 нулем, то есть биномиальному коэффициенту n+m−1= n+m−1. Это число наm−1nзывается числом сочетаний с повторениями. Ему можно придать несколько другой содержательный смысл: числоразличных последовательностей шаров, извлекаемых из урны с возвращением.Число мультиподмножеств, содержащих каждый элемент исходного множества по крайней мере один раз, совпадает с числом решений системыα1 + α2 + · · · + αm = n,αi ∈ N, i = 1, m,которое по принципу взаимно однозначного соответствия совпадает с числом решений системы 0α1 + α20 + · · · + αm0 = n − m,αi0 > 0, αi ∈ Z, i = 1, m,n−1 то есть равно n−m.
Используя полученные результаты можно, например, найти число целочисленных точек в тетраэдре x, y, z > 0, x + y + z 6 k.zk6\ \\ k 0 ykx (k+1)(k+1)Их число равно k+2=.k2Введем еще одно комбинаторное число: [m]n = m (m + 1) · · · (m + n − 1) = [m + n − 1]n — возрастающий факториал. Это число имеет следующий содержательный смысл: имеется m-ярусный стеллаж, на который надо расставитьn книг, причем порядок книг на полке имеет значение.
Действительно, для первой книги имеется ровно m различныхвозможностей поставить ее на одну из полок. Для второй книги возможностей уже на одну больше, так как на одной изполок есть уже две неравнозначные позиции. И так далее. В результате получится возрастающий факториал.Перестановки. Рассмотрим теперь подробней взаимно однозначные отображения множестваX = {1, 2, .
. . , n}6ГЛАВА 1. КОМБИНАТОРИКАна себя, то есть перестановки. Всего их n!. Множество перестановок n-элементного множества называется симметрической группой степени n и обозначается Sn . Чтобы мотивировать такое определение, введем произведение (композицию) двух перестановок π1 , π2 ∈ Sn ⇒ π1 · π2 = π по следующему правилу: π1 · π2 (x) = π2 (π1 (x)).π1xπ2??Иногда в литературе композицию определяют наоборот: π1 · π2 (x) = π1 (π2 (x)), однако, мы будем придерживаться введенных выше обозначений. Таким образом, Sn — группа с введенным выше внутреннимзаконом композиn . Для каждой перестановкиции. Единичным элементом в этой группе служит единичная перестановка e = 11 22 ...... n... n−1 = a1 a2 ...
an ∈ S , при это подразумевается, что столбцыπ = a11 a22 ...nan ∈ Sn существует обратная перестановка π1 2 ... nпоследней переупорядочены так, что элементы первой строчки расположены по возрастанию. Действительно, в этомслучае π · π −1 = π −1 · π = e. Можно показать, что операция композиции ассоциативна, но некоммутативна. Также справедливо утверждение о том, что любая конечная группа изоморфна симметрической группе подходящего порядка n.Перестановками можно описывать всевозможные повороты и симметрии. Так, например, группа симметрий графа(группа перестановок вершин, приводящих к графу, изоморфному исходному)2``4#c## c #`c#`1 #c#c#6 ccc#c``35содержит всего четыре элемента: e, π1 = 11 23 32 44 55 66 , π2 = 11 22 33 45 54 66 , π3 = 11 23 32 45 54 66 .Граф, задающий перестановку имеет достаточно простой вид. Поясним это на примере: пусть дана перестановка1 2 3 4 5 6 7 8 9 10.4 9 2 6 10 7 1 8 3 5Тогда ей можно поставить в соответствие набор непересекающихся контуров1`6`72`-9`AKA A`?`36-4`5`8̀n`10В этом случае говорят, что перестановка распадается на соответствующие циклы.
В общем случае, начиная последовательно применять перестановку к элементу i, затем к π (i), и так далее, в силу конечности исходного множестварано или поздно наступит повтор, а в силу взаимной однозначности перестановки этот повтор наступит тогда, когдазначение перестановки станет равным i. Таким образом, для любой перестановки допустимо представление в виде произведения своих простых циклов.
Перестановка из примера представляется в виде произведения следующим образом:[1, 4, 6, 7] [2, 9, 3] [5, 10] [8]. При этом порядок элементов внутри цикла важен, а порядок циклов в произведении не играетникакой роли. По договоренности в дальнейшем будем писать циклы в порядке возрастания их наименьших элементов.Также часто не будем выделять циклы единичной длины, то есть неподвижные элементы. Тогда, если π1 = [C1 ], где C1 —упорядоченный набор элементов, образующих цикл, а π2 = [C2 ], при условии C1 ∩C2 = ∅ ⇒ π = π1 ·π2 = π2 ·π1 = [C1 ] [C2 ].Заметим, что в данном случае перестановки, представляющие простые циклы, коммутируют в силу того, что на любойэлемент в таком произведении будет действовать только одна перестановка.Определение 1.1.2. Типом перестановки π множества X = {1, 2, .
. . , n} называется вектор длины n с целыми неотрицательными компонентами λ (π) = (λ1 , λ2 , . . . , λn ), где λ1 — число петель (неподвижных элементов), λi для i = 2, n —число циклов длины i.Тип рассмотренной в примере перестановки будет (1, 1, 1, 1, 0, 0, 0, 0, 0, 0).Компоненты вектора типа перестановки удовлетворяют простому соотношению:n∑ iλi = n.i=1Зададимся вопросом, сколько перестановок из Sn имеют заданный тип. Ответом на него служит следующее число:n!.λ1λnλ1 !···λn !1 ···n[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
