В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 3
Текст из файла (страница 3)
. .] [. . .] [. . .] [. . .] . . . [. . .] [. . .]| {z } | {z } | {z }λnλn−1λ171.1. ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛАРасставляем все n элементов по местам (n! способов). Затем отождествляем порядок циклов внутри группы цикловодной длины, то есть делим на λ1 ! · · · λn !. Также отождествляем порядки элементов внутри цикла, если они определяютодин и тот же цикл: для конкретного цикла длины k число различных способов его определить в одной группе равно k(k циклических сдвигов), то есть делим на 1λ1 · · · nλn . Получаемутверждаемоечисло.i ...
j ...образуютинверсию, если i < j & ai > a j . ЧислоБудем говорить, что элементы ai и a j в перестановке ...... ai ... a j ... n(n−1)... nинверсий перестановки π будем обозначать через I (π). Так, например, I (e) = 0, I n1 ...= 2 = n2 . Для пере1становки определяется знак:(1,если перестановка четная,I(π)sgn (π) = (−1)=−1, если перестановка нечетная.Для знака перестановки выполняется очевидное свойство sgn (π1 · π2 ) = sgn (π1 ) · sgn (π2 ). Транспозиция двух элементов i и j обозначается просто [i, j], частным случаем транспозиции выступает транспозиция двух соседних элементов[i, i + 1]. Справедливо утверждение, что любую перестановку можно представить в виде произведения транспозицийдвух соседних элементов, число которых равно числу инверсий перестановки.
Действительно,... i i+1 ... [i, i + 1] = ... i i+1 ...... a b ...... b a ...i ...Берем произвольную перестановку и смотрим, что переводится ею в единицу: π = ...... 1 ... . Тогда π · [i − 1, i] ·[i − 2, i − 1] · · · [1, 2] = π1 единицу переводит в единицу, причем в силу того, что единица образовывала транспозициисо всеми элементами левее, число транспозиций уменьшилось ровно на i − 1. Поступаем также со всеми остальнымиэлементами и получаем, что π · t1 · t2 · · ·tI(π) = e. Далее, так как обратным элементом к транспозиции двух элементовявляется она сама, π = tI(π) · · ·t2 · t1 .
Умножение на каждую транспозицию изменяет знак, следовательно, для любых0двух перестановок π1 = tI(π1 ) · · ·t1 и π2 = tI(π· · ·t10 верно, что sgn (π1 · π2 ) = sgn (π1 ) (−1)I(π2 ) = sgn (π1 ) sgn (π2 ).2)Все четные перестановки образуют подгруппу симметрической группы. Знак любой транспозиции вида... i ... j ......
j ... i ...|{z}kравен (−1)2k+1 = −1. Определим знак произвольного простого цикла как произведение знаков простых транспозиций,композицией которых является данный цикл:[a1 a2 . . . ak ] = [a1 a2 ] [a2 a3 ] · · · [ak−1 ak ] ⇒ sgn ([a1 . . . ak ]) = (−1)k−1 .Таким образом, чтобы определить знак перестановки, нужно знать число циклов четной длины:b 2n c∑ λ2iλ (π) = (λ1 , λ2 , . .
. , λn ) ⇒ sgn (π) = (−1) i=1.Принцип включения и исключения. Из теории множеств известны простейшие мощностные равенства: |A ∪ B| =|A|+|B|−|A ∩ B| , |A ∪ B ∪C| = |A|+|B|+|C|−|A ∩ B|−|B ∩C|−|C ∩ A|+|A ∩ B ∩C| и так далее. Следующее предложениедокажем по индукции. Пусть есть исходное множество N , |N | = N и набор свойств P1 , . . . , Pn , кодируемые набором{1, 2, . . .
, n} = [n]. Для каждого элемента формулируем n высказываний относительно обладания им каждого из этихсвойств. Пусть I = {i1 , i2 , . . . , is } ⊆ [n] — подмножество кодов свойств. ОбозначимN [I] = ] {a ∈ N | a обладает в точности свойствами Pi1 , . . . , Pis и больше не обладает никакими}Так, например, N [∅] равно числу элементов N , не обладающих ни одним из указанных свойств. Далее, обозначимN (I) =∑N [J]I⊆J⊆[n]— число элементов, обладающих заданными свойствами Pi1 , .
. . , Pis с кодами из I и, быть может, еще какими-то. Втерминах n-мерного булева куба, все вершины которого помечены неотрицательными целыми числами, показывающими сколько элементов из N обладают соответствующими свойствами, эти числа имеют следующий содержательныйсмысл: N [I] — это число, приписанное вершине, у которой все разряды с номерами из I равны единице, а оставшиесяравны нулю; N (I) — это сумма чисел, приписанных всем вершинам грани между вершиной N [I] и единичной. ПустьтеперьN[r] = ∑ N [J]J⊆[n]|J|=r8ГЛАВА 1. КОМБИНАТОРИКА— число элементов, обладающих ровно r (неважно какими) свойствами. В n-мерном булевом кубе это сумма чисел,приписанных вершинам r-го слоя;N(r) = ∑ N (J)J⊆(n)|J|=r— число элементов, обладающих не менее r (неважно какими) свойствами. В n-мерном булевом кубе это сумма чисел,приписанных вершинам всех слоев, начиная с r-го.Теперь можно сформулировать принцип включения и исключения:Теорема 1.1 (Принцип включения и исключения).N[0] = N(0) − N(1) + · · · + (−1)i N(i) + · · · + (−1)n N(n) , mm+1i m+in−m nN[m] =N −N(m+1) + · · · + (−1)N(m+i) + · · · + (−1)N .m (m)mmm (n)(1.2)(1.3) Док-во.
При n = 1 N[0] = N(0) −N(1) = N −N(1) и формула (1.2), очевидно, справедлива. Пусть формула справедливадля n − 1 свойств. ИмеемN[0] = N(0) − N(1) + N(2) − N(3) + · · · + (−1)n−1 N(n−1) .(1.4)Эта формула справедлива и для совокупности объектов, обладающих свойством n:nnN [n] = N(n) − N(1)+ · · · + (−1)n−1 N(n−1),(1.5)где N(nj) — число объектов, обладающих свойством n и еще какими-то другими свойствами, число которых не меньшеj. Вычитая формулу (1.5) из (1.4), получаем формулу (1.2).Докажем теперь формулу (1.3). Перепишем ее следующим образом: nn−mm+kN[m] = ∑ (−1)k∑ N[i] .mk=0i=m+kДокажем, что каждый предмет, обладающий в точности m свойствами, будет учтен в ней ровно один раз.
В самомделе, элементы, обладающие s < m свойствами, не учитываются очевиднымобразом. Элемент, обладающий заданнымиm+t s = m + t свойствами, будет учитываться во внутренней сумме m+kраз. Ноn−m∑ (−1)k=0km+kk (1 при t = 0,m+tm+t tk t=∑ (−1) k = 0 при t > 0.m+kmk=0Таким образом, в (1.3) ровно по одному разу учитываются элементы, обладающие в точности m свойствами, а остальныене учитываются.Принцип включения и исключения имеет весовой аналог. Пусть задана некоторая весовая функция ω : N → K,где K — кольцо, ставящая каждому элементу a ∈ N в соответствие его вес ω (a). Тогда если во всех обозначенияхпоменять N на значение веса W , то суммарный вес элементов, обладающих ровно m свойствами будет равенТеорема 1.2 (Весовой вариант принципа включения и исключения). mm+1i m+in−m nW[m] =W −W(m+1) + · · · + (−1)W(m+i) + · · · + (−1)W .m (m)mmm (n)(1.6) Док-во.
Доказательство формулы (1.6) полностью аналогично доказательству формул (1.2) и (1.3) с тем лишь различием, что считать необходимо не число элементов, а их суммарный вес.Перестановки с ограничениями. Будем рассматривать взаимно однозначные отображения множества X ={1, 2, . . . , n} в себя с ограничениями, то есть для каждого элемента будем запрещать его отображение в какие-то другие. В нижеприведенной таблице под чертой указаны запреты для каждого элемента.1a11a12...a1i1Некоторые запреты вполне могут быть пустыми.2a21a22...a2i2... j.
. . a1j. . . a2j........ . . aijj...............nan1an2...anin91.1. ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛАПримером задачи на перестановки с ограничениями может служить задача о беспорядках. В ней требуется найтичисло перестановок со следующими ограничениями:1 2 ... n1 2 ... nТакие перестановки называются беспорядками. Число беспорядков n-элементного множества обозначим Dn .Задачи на перестановки с ограничениями часто сводятся к подсчету перманента 0, 1-матрицы.
Вспомним, чтоопределителем квадратной матрицы An размера n × n называется следующее число:det (An ) =∑sgn (π) · a1,π(1) · a2,π(2) · · · an,π(n) .π∈SnОбобщениями определителя служат числа, получаемые заменой в правой части знака перестановки sgn (π) некоторойдругой функцией перестановки f (π), называемой в этом случае функцией Шура. Из всех таких функций рассмотримодну: f (π) ≡ 1. Выражениеper (An ) = ∑ a1,π(1) · a2,π(2) · · · an,π(n) ,π∈Snполучаемое в этом случае, называется перманентом матрицы.
Он обладает некоторыми свойствами, схожими сосвойствами определителя. Так, например, если матрицу транспонировать, то ее перманент не изменится. Также, привычислении перманента можно использовать разложение по строке или столбцу. Но есть и различия: если переставитьдве строки (два столбца), перманент не изменится в отличии от определителя, который поменяет знак. Также, добавление к одной из строк (одному из столбцов) линейной комбинации других строк (столбцов), вообще говоря, меняет перманент. Определение перманента можно обобщить на случай прямоугольной матрицы: если, например, число столбовm больше числа строк n, то перманент будет равен сумме всевозможных различных произведений элементов, взятыхиз разных строк и разных столбцов.
В добавление к вышесказанному заметим, что вычисление перманента являетсяNP-полной задачей (в настоящий момент известны только экспоненциальные алгоритмы вычисления перманента), вто время как задача вычисления определителя полиномиальна (известный метод Гаусса требует O n2 умножений).Для таблицы запретов строим 0 − 1-матрицу размера n × n, в которой столбцам припишем элементы исходного множества, а строкам — запреты на отображения.
Единицу в позиции (i, j) ставим тогда и только тогда, когда элемент iможет отображаться перестановкой в элемент j, в противном случае (если отображение i в j запрещено), ставим нуль.Между перестановками и слагаемыми в перманенте устанавливается взаимно однозначное соответствие. Если перестановка нарушает хотя бы один запрет, то соответствующее ей слагаемое будет равно нулю, в противном случае онобудет равно единице. Таким образом, число перестановок с запретами будет просто равно перманенту соответствующейматрицы.Для задачи о беспорядках перманент выглядит следующим образом:0 1 1 ... 11 0 1 .
. . 11 1 0 . . . 1. . . . . . . . . . 11per011...0При n = 21= 1;0При n = 30per 111 10 1 = 2.1 0Вызывает интерес поведение величины числа беспорядков n-элементного множества Dn при n → ∞. Возможны четыреварианта:Dn→ 0;n!Dn→ a,n!10<a< ;2Dn→ a,n!16 a < 1;2Dn→ 1.n!Воспользуемся принципом включения и исключения. Обозначим для i = 1, n свойством Pi перестановки тот факт, чтоi → i. Задача свелась к подсчету общего числа перестановок, не обладающих ни одним из этих свойств:N[0] = N(0) − N(1) + · · · + (−1)i N(i) + · · · + (−1)n−m N(n) = nnm nn nn! −(n − 1)! +(n − 2)! + · · · + (−1)(n − m)! + · · · + (−1)(n − n)! =12mnn! n!(−1)m n!(−1)n n!11(−1)m(−1)nn! − + + · · · ++···+= n! 1 − + + · · · ++···+.1! 2!m!n!1! 2!m!n!10ГЛАВА 1. КОМБИНАТОРИКАУстремляя n к бесконечности получаем асимптотику числа беспорядков:∞Dn11−−−→ S = ∑ (−1)m ·= e−1 = .n! n→∞m!em=0Таким образом, правильным оказался второй вариант.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
