Введение в прикладную комбинаторику, Кофман А. (984071), страница 20
Текст из файла (страница 20)
') Полсоты минимальные, если онн не могут быть разложены на непере- секающиеся полсоты, До к аз а тельство. В самом деле, пусть р,— число г-выборок, соответствующих всевозможным г непротиворечивым свойствам, Имеем р,=,р, +,р,, зр, +,р, з ° р,+ ... +,р, °,р, 1+ор„, (21.24) где 1р!(зр!), 1=1, 2, ..., г, равно числу 1-выборок с непроти- 1 й 3 4 б б 7 8 9 (3 5) ! 1 9 81!4) 18 7)12) ! ) (41 1б! (2' Рис. 49.
Рис. 48. воречивыми свойствами из С, (и! С,), или и Рс= ~4 !Р -! 'зр! зро=зро=1 ° ! з (21,25) Учитывая (7.19), имеем 1Э (2) = Р, (2) Р,(2). П р и м е р (рис. 50). Запретные клетки обозначены 1=1,2,...,8. Легко получаем !Ро=! !р! =3, !Рз=2, !Рз=О; зро = 1~ зр! = 5, ор, = 8, ,р„ = 4, зрз = О> р,'(2) = 1 + Зг + 22', (21.26) через 944, (21.27) (21.28) (21.29) (21.30) !38 р*(г) = 1 + 52 + 82' + 4г'. р* (г) = (1 + Зг + 229) (1 + 52+ 8г" + 42з) = 1+ 8г+ 252'.+ 3828+ 28г4+ 8гб (21 31) а также ро = 1, р, = 8, рз = 25, р! = 38, р, = 28, р, = 8, Ро = О, р! —— О. Отсюда 447 (0) = 5040, 73 (1) = 5760, н7 (2) = 3000, ы (3) = 912, зе(4)=168, за(5)=16, н7(б)=0, 4е(7)=0, (21,33) н7*(г) =5040+ 57о03+ 309037+ 912гз+ 1683'+ 16г', (21.34) (17 (0) = ш (0) — н7 (! ) + ы (2) — пз (3) + и (4) — ы (5) + зе (6)— — ш (7) =- 5040 — 5760 + 3000 — 912 + 168 — ! 6 =! 520, К (1) = ы (1) — С.7е (2) -+ Сзнз (3) — С4ш (4) + Сзй (5) — С;7я (6) + + Сзы (7) = 5760 — 6003 + 2735 — 672 + 80 = 1904, (4 2 3) (4 6 6 7 14 ) 3 '2' )3 ! 1 1 6 1 36 1 ! 7,! Рис 00.
(р'(2) = ш (2) — Сзю (3) + С4ш (4) — Сзш (5) + Сзэ (6) — Стш (7) = = 3000 — 2736 + 1008 — 160 = ! 112, 1(7 (3) = н7 (3) — Сзнз (4) + Сзш (5) — Сзы (6) + Сзи (7) = = 912 — 672 + 160 = 400, ()7 (4) = ш (4) — Сзш (5) + Сзш (6) — Сзш (?) = 168 — 80 = 88, 97(5) = в(5) — Сзш(б) + Сты (7) =!6, ((7(6)=0, К(7)=0; (21.35) (Р" (г) = 1520 -1- 1904г +! 112г'+ 400гз + 88г4+ !бгз. (2! 36) Замечание. Легко убедиться, что соотношение р*(г)= =-р",(г) р,"(г) не влечет подобного соотношения для н7'(г), н7',(г), в.,"(г), а также и для 07*(г), Я7",(г), Ж';(г).
Формула (21,23) 4зэ случай д минимальных непересекающихся обобщается на подсот: Р*(г) =Р',(г) Р.,"(г) ... Р,(г). Частичные соты для заданных сот. Если в заданных сотах аннулировать запреты на некоторые ячейки, то полученные соты называются частичными. На рис. 52 изображены частичные соты для сот на рис. 51. Понятие частичных сот вводится с целью получить представление функции р*(г) через более простые функции. (2!.37) ! 2 3 4 б б 7 1 2 3 4 б 6 7 Рис.
62. Рис. 61. Теорем а. Пусть заданы соты К. Через К1 обозначим частичные сотби для К, которые получаются снятием запрета с ячейки (1, !), а через Кз — частичные сотьц которые получаются из К снятием запрета со всех ячеек в 1-й строке и 1-м столбце. Тогда Р =1Р +зр -1 г=! 2 и (2! .38) где р„, 1рп зр„— ладейньсе многочлены соответственно для К, К! и Кз. Доказательств о. Обозначим через й!1 свойство, соответствующее ячейке (1, !), а через А1 — подмножество перестановок с этим свойством. Любым г множествам с непустым пересечением, не содержащим А1, однозначно соответствуют г множеств из К1, а любым г множествам с непустым пересечением, содержащим А1, однозначно соответствуют г — ! множеств из Кз и наоборот.
Теорема доказана. Проиллюстрируем эту теорему на примере. Через С, К1 и Кз обозначены соты на рис. 53, 54 и 55, где У!1 — ячейка (2, 2). Выпишем непустые пересечения для С при г=3: (А1П Аз П А4) (А1 П А4 П Аз), (Аз П Аз П А4), (Аз П Аз П Аб), (Аз П А4 П Аз), (Аз П А4 П Аб), (Аз П А4 П Аб).
(21.39) Таким образом, р,=7. !40 Аналогично непустые пересечения для К, при с=3: (Агй Азй Аг), (Азй Азй АО), (Азй Агй Аз), (Аз й А4 й Ао), (Аз й А4 й Ао) т. е.,рз=5, а непустые пересечения для К, при с=2: (Аз й Аг) (А4 й Аз) (21. 41) 1 З З з з иг Рис. 55. Рис. 54.
Рис. 53. Легко выписать теперь соотношение для производящих функций: Р'(а) =,Р'(и) + а гр" (а), (21.42) где Р'(а) =- Х Р,е", (21. 43) г=О Р'(и) = Х ,Р, ', г=о (21.44) ,Р" (а) = ~ зр,е . =о (21. 45) В самом деле, 24," — Х ' Рг~ ~ грг~ + ~г грг-г~ из ~рг~ + ~ ~ зрг-гз г=1 г=-1 г.=1 г=1 г=! = Х ,р,а' + а Х зрга'. (2!.46) г=г г=о Так как Ро —— ! и гро=!, то имеем Х Р,а' = Х Р, ' + Х гр,а'.
.=О г=о =о (21.47) 14! т. е.,рз= 2. Отсгода видим, что пересечения из (2!.39) и (2!.41) дают все пересечения из (21,39), 3 а м е ч а н и е. Функция р*(г) определяется только лищь взаимным расположением запретных ячеек, а размеры сот несущественны. Так функция р" (г) = 1+Зг+ 2га одна и та же для всех сот на рис. 56. функционально эквивалентные соты.
Двое сот с одной и той же функцией р" (г) называются функционально эквивалентными. ! 2 3 4 з ! 2 3 4 Рис. 56. 'Я4 ~! Рз Ра Рнс. ЗУ. Это отношение является отношением эквивалентности (поскольку оно рефлексивно, симметрично и транзитивно). Пример двух функционально эквивалентных сот с р" (г) = ! + 4г + 2г' (21.49) приведен на рис. 57 (изображены лишь запретные ячейки). Следовательно, двое функционально эквивалентных сот имеют совпадающие функции как тв'(г), так и мт'(г). В (36] приведены таблицы различных функций р" (г). Разложение сот на более простые частные соты.
Как мы видели раньше (см. (21.42)), Р (г) = !Р (г) + гтр (г) (21.50) Введем соответствующую (2!.50) операцию над сотами: К=К! З Ка. (2! .51) Аналогично можно поступать с К! и Ка. К=К ЗК4 (21.52) К2 КаЗ Ка (2! .53) Тогда (21.54) К=(Ка З К4) З (Кв З Ка) Поступаем так столько раз, сколько нужно '). ') Заметим, что ата оверавия некоммутатввна, нерефлексивна и неассоциатввна. УПРАЖНЕНИЯ 21А Вычислить функции р„м(г), ва(л), Ю(г), 1Г'(г) и Аа(г) или соа 1 2 3 4 1 2 3 4 1 2 3 4 1 а) а) 1 2 3 4 5 2 3 4 5 1 2 3 4 5 е) 1 2 .1 4 5 6 7 3 4 5 5 еа) в) 144 Приведем пример (рис. 58).
Символом К с нечетными индексами обозначаются частичные соты, где запрет снят с одной ячейки, а символом К с четпымн индексами обозначаются соты, где запрет снят с ячеек в одной строке и одном столбце. Разумеется, описанное разложение не единственно, и пересчет таких разложений является трудной задачей. Дополнение сот. Дополнением сот С являются соты С, где запретны все ячейки, которые не были запретными в С и наоборот.
Соответствующий пример приведен на рис. 59. Не существует простой формулы, позволяющей выразить р*(г) через р*(г) (об этом см. [36)). 2!Б. Подсчитать число подстапозок с ограпичекппчи, указапиьпги стрел- каин, иа каждой из диаграчи 21В. Дать разложение иа иииимальиые иепересекамгииесп подсоты указаииых ниже сот и найти длп казкдой из иих р" (з) и 74" (г). 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 6 9 2 !и а) ф 22. Противоречивые перестановки Перестановки из некоторого множества называготся противоречащими заданной перестановке л, если они удовлетворяют ограничениям, которые вытекают из рассмотрения сот с запретными ячейками, соответствующими подстановке 1 1, где р = = (1 2 ...
и). Например, подстановке (и) (3 4 1 6 2 5) (22.1) соответствуют соты на рис. бО. 1 2 3 4 5 б ! 2 3 4 ... ю Рис. 61. Ряс. 60. Рассмотрим теперь несколько задач о противоречивых перестановках. Задача о встречах. Эта задача уже рассматривалась в $ 14. Если через Ун обозначить свойство: элемент ! занимает место 1, то из рассмотрения сот на рис. 61 легко получается (М.2) р, = С'„, г = О, 1, 2... и. Отсюда р (3) — 4.4 С~а — (1 + 3) Имеем (см.!4.7)) (22.3) ге (г) = С„' (и — г)! = †" , г = О, 1, 2, ..., и, (22.4) г1 ' а Чг' (~) = ~~ — „г' = и1 (1+ г+ — „+ + — „, ) (22 б) Из (22,5) легко получить числа Р, определяемые формулой (14.11).
Н6 Можно рассматривать перестановки, противоречащие нескольким заданным перестановкам. Эти перестановки удовлетво. ряют ограничениям, вытекающим из рассмотрения сот, получаю. шихся наложением сот, соответствующих каждой из заданных перестановок. Задача пересчета перестановок, противоречащих одной заданной перестановке, немедленно сводится (если переставить строки и столбцы в сотах) к задаче о встречах. Если задаются две перестановки, то одну из них можно считать тождественной, Можно изучать также множества перестановок и объектов, противоречащих одной (или нескольким) перестановкам т из этих объектов (и ( и).
С другой стороны, л У„(г) = ) С,',(и — г)! (г — «'= ~ —,(г — «'= =о =и!(1+( — «+ (, ) + ... + ! (22.6) Задача о супружеских парах. Задачу о супружеских парах из $ 20 можно рассматривать как задачу об отыскании перестановок, противоречащих следующим двум: (1, 2, ..., и — 1, и) и (2, 3, ..., и, 1). Соответствующие соты указаны на рис. 62. ! 2 3 ... л! л 2 ! ! ! ! ! П !' лл! Рис. 62.
Рис. 63. По второй лемме Капланского имеем 2и С ! с 2л — г ол-г' (22.8) л Р*(г) = ~~ 2„, С': — г с=о ы (г) — Со„, (и — г)!, (22.9) (22.10) по'(г) = чь С'л, (и — г)! г". и'О 2л — г (22.1 « =о Если обозначить через ~/„'(г) производящие функции и=2, 3, ...: л У„(г) = У С',„, ( — )! ( — «', М*(г) для (22.12) с-о !42 Это — другое выражение для денумератора о!;, (г) ио (14,32), си;.- волически !о! (г)=Э+ г) с! — 'Й„, и=1, 2, ..., 1 — 'Во, (22,7) поло!нить (22.13) то получим числа (У(п, й), которые для п от 2 до 8 приведены в таблице 22.1. Т а б л и ц а 22. ! Числа 77(и, 7с) а задаче о супружескпх парах 01'и, а! а=о о=о с=с 2 35 280 10 800 ! ! 672 Видоизмененная задача о супружеских парах.
Рассмотрим соты на рис. 63. Они соответствуют расположению супругов в задаче о супружеских парах, если эти пары рассаживаются вдоль одной из сторон прямоугольного стола, т.е. данные соты отличаются от сот на рис. 62 только ячейкой (и, 1). По первой лемме Капланского г=О, 1, 2, ..., ~ (22.14) Оие~!П! !о (г) .:~ С„„, !г (22,16) =-о сп (г) = С'„, с ! (и — !.)!; (22.16) и и.!. ! но ! ю" (г) = гл С,", се~(и — г)! г'. (22.
17) Если для этого случая обозначить через 1'„'(г) производящую функцию й7" (г), а через )7(п, г) — ее коэффициенты, то Ии<-!!р! (7",(г) = ~! С'„,е! (а — г)! (г — 1)', (22. 18) .=о КиЕОГЛ )7и(г) = ~ )7 (и, г) г'. с=о (22.19) В таблице 22.2 числа 17(п, й) приведены для п от 1 до 8. 148 и=2 и=-3 и=4 и=5 и=б и=7 и=8 0 1 2 13 80 579 4 738 0 8 39 192 ! 344 2 3 4 40 2!О ! 477 2 8 20 !52 994 7 888 2 !5 69 469 3 660 2 24 !40 1 232 Тзблопа 22.2 Числа к'(а, а) в вндонзмененной задаче о супружеских парах 2=8 Г!в,е) 1 15 1 105 21 952 196 1 28 Если индекс М! относится к задаче о супружеских парах, а индекс М,— к видоизмененной задаче о супружеских парах, то в силу (21.38) и (21.42) имеем (22.20) л!р,= —,нр,+и'р, ! ! 2 р, (г) =- яр,' (г) + а р*,, (г), ! ! (22. 21) где М', относится к задаче, функционально эквивалентной видоизмененной задаче о и — 1 супружеских парах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
