Введение в прикладную комбинаторику, Кофман А. (984071), страница 21
Текст из файла (страница 21)
Обобщенная задача о супружеских парах. Рассмотрим задачу пересчета перестановок, противоречащих двум заданным, одна из которых тождественна, а другая произвольная. Эта задача изучалась Т уш а ром ') и Р и орда но м (Зб]. На рнс. б4 представлен пример при и = 7, где две перестановки задаются нижними строками в 1234567 1234567 (1 2 3 4 5 6 7) и (3 4 ! 7 г 6 2).
(22.22) Рис. б4 показывает, что множества запретных ячеек, соответ. ствующих (1 2 3 4 5 6 7) (3 4 1 7 5 6 2)' пересекаются. Напротив, если вторая подстановка является циклом (как на рис, бб), то приходим к задаче о супружеских парах. !) Т о п с Ь а г 6, Реппп1апопз 6)зсогбап! вг)!)! 1чго и!уеп реппп1зпопз, Зспр1а гпа1)гоп!в!!се 19 11953), 108 — 119. 149 и=) о=2 п=З п=4 в=5 о=6 и =-7 и=8 0 0 1 3 16 96 675 б 413 8 35 211 1 459 !1 584 1 3 6 38 213 1 479 11692 1 6 20 134 915 7 324 1 10 50 385 3 !30 Предположим, что подстановка, соответствующая второй перестановке, принадлежит классу (/г) = (77о йс,..., /г„).
(22. 23) Заметим тогда, что соты разлагаются на непересекающиеся подсоты, соответствующие каждому циклу. Обозначим через 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Рис. 64. Рис. 65. р' (г) производящую функцию для подсот, образованных с по! мощью цикла длины 3и; тогда рс(~)=(1 +г) ' [р~ (г)! ' ~рх (г)7( ", (22.24) где р' (г), 1=2,3,..., и, функции р*(г) соответственно для сот порядка 2, 3, ..., и в задачах о супружеских парах.
П р и м е р (рис. 64). Пусть задана подстановка 13417562)' Выписываем ее циклы: (5), (6), (13), (247), (22. 25) т. е (Й) = (2, 1, 1, О, О, О, О). В силу (22.9) с и= 2 и и= 3 п= 2: р*(г) = 1+ 4г+ 2г'-, и = 3: р*(г) = 1 + бг + 9ги+ 2г' (22.26) (22.27) (22.28) Итак, р,'„(г) = (1+ г)'(1 + 4г + 2г ) (1+ бг + 9ги+ 2г ) = =! .+ 12г.+ 5622.+ 130гз ! 161г4 ! 106г1+ 34ги+ 437 (22 29) Ро = 1 р! = 12 рс = 56 р. = 130 р4 = 161 рс = 106 рс = 3 1, рт = 4.
(22.30) По формулам (21.3) и (21.8) вычисляем п7(т) и Ф'(г). 150 УПРАЖНЕНИЯ 22А, Пересчитать перестановки, противоречащие перестановкам, обозна пенным на сотах ! 2 3 4 5 ! 2 3 4 5 ! 2 3 4 5 г) 2 3 4 5 8 7 8 ! 2 3 4 5 0 7 8 5) а) соты 7) н 2), б) соты 7) н 3), в) соты Л), 2) и 3), г) соты 4) и 5), 225. То же, что и в упражнении 22А, но использовать формулу (224). $23. Латинские прямоугольники Рассмотрим множество объектов, элементы которого обозначены через 1, 2, ..., и.
Латинским прямоугольником называется прямоугольная таблица с г строками и 3 столбцами, где каждая строка и каждый столбец — размещения без повторений соответственно из л объектов по г и из и объектов по 8(г ( и, 8 ( а). На рис. 66 приведен латинский прямоугольник размера 4 Х6 на множестве из восьми объектов. Пусть 3 = п. Тогда строки латинского прямоугольника — перестановки л объектов. Такой латинский прямоугольник называется нормализованным, если элементы его первой строки записаны в естественном порядке (см., например, рис. 67).
Каждый латинский прямоугольник можно нормализовать, перес ! ав чя и его ст олбцы. 151 0 (г, и) = и!К (г, и). К(2, и) = 0„, (23.1) Очевидно, что (23,2) где 0„ — число беспорядков (см. (14.11)). ! 2 3 4 3 6 Ряс. 66. Рис 67. Легко видеть, что число латинских прямоугольников размера 3 зс', и с двумя первыми строками ! 23...и и! 2...и — ! (23. 3) равно числу (/„в задаче о супружеских парах.
Число всех латинских прямоугольников размера 3)с' ,и дает формула Риордапа (см. [36]): Л3 К(3, и) = — ~ С„Ос 404(уи 2 3 4 з=з где гп — наибольшее целое число, меньшее и/2, и 4 ! 2 3 (7 з 4 ! 2 Пример. Вычислим К(3,5): К (3, 5) = Сз0404Уз + Сз 040~ У~ + С30з0 Уь Рис. 63. (23.5) (23.4) По формулам (14.11), (20.8) и из таблиц 14.1 и 22.1 К(3,5)=1 44 1.13+5 9 О 1+10 2 1 1=592. (23.6) Число латинских прямоугольников прн г ) 3 неизвестно Можно доказать (см. [35) и [36)), что г сз ззз 0(г, п) .(и!) е ', если г((!пп) (23.7) Латинский квадрат. При г=з=п говорят о латинском квадрате.
Примером латинского квадрата служит таблица умножения конечной группы. На рис. 68 изображен латинский квадрат размера 4 Х 4. Если ! — число латинских квадратов, в которых !62 Если через 0(г, п) обозначить число латинских прямоугольников размера гни, а через К(г,п) число нормализованных, то элементы первой строки и первого столбца записаны в естественном порядке, то Л (и, и) = и! (и — 1)11а, (23.8) а если в естественном порядке записаны только элементы первой строки, то К(п, и) = (и — 1)! 1„.
(23.9) Известные значения („ приведены в таблице 23.1 (из (36)). Т а б л и ц а 23.1 1 ! 4 16 942 080 66 9 408 На рис. 69 перечислены латинские квадраты размера 4 рг', 4. а) б) в) Рис. 69. Заметим, что квадраты б) и в) — таблицы умножений двух возможных групп порядка 4. УПРАЖНЕНИЯ 23А. Каково число нормализованных латинских прямоугольников размеров: а) 3 Х 6, б) 3 Х 7, в) 3 Х 8. Сравнить с числами, получающимися по формуле (23.7). 23Б. Указать число латинскнх квадратов порядка 5, в которых злементы первой строки и первого столбца идут в естественном порядке. Тот же вопрос при условии, что второй столбец имеет вид 2, 3, 4, 5, 1.
Выписать все решения, ГЛАВА П1 СВОИСТВА ГРАФОВ 2 24. Введение В конце предыдущего параграфа с помощью понятия сот изучались комбинаторные задачи о размещениях по ячейкам, причем в часть из них помещать элементы было запрещено. Тем самым ячейки сот разбивались на два подмножества: ячейки, обладающие некоторым свойством У, и ячейки, не обладающие им (т. е. обладающие свойством У). Всякий раз, когда это имеет место, говопят, что множество реализует граф. На рис. 70 приведен прн- 2 мер графа.
Этот термин 3 10 Рис. 7!. Рис. 70. широко обсуждался, и некоторые считают, что этимологически предпочтительнее заменить его термином «грамма» (используя аналогию: телеграф — инструмент, а телеграмма — сообщение, передаваемое этим инструментом), но мы будем придерживаться обычной терминологии.
Под графом, следуя Кен игу [21) и Ве ржу [8), мы будем понимать разбиение теоретико-множественного произведения некоторого счетного множества на себя на две части. Графы рассматриваются во многих областях математики, и мы посвящаем им значительную часть книги. 154 Рассмотрим рис. 70, изображающий граф. На нем можно разглядеть пуделя, но рассмотрения такого рода нас не интересуют (в противоположность комбинаторной топологии).
Этого пуделя можно представить подмножеством пар С = ((3, 3), (4, 2), (4, 3) (4, 9), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 4), (5, 5), (5, 5), (5, 7), (5, 8), (7, 4), (7, 8), (8, 4), (8, 8)) (24 1) или так, как это сделано на рнс. 71, где пара изображена стрелкой. Все эти способы изображения графа эквивалентны *), и в 1 2 3 4 б б 7 8 Рнс. 73. Рнс 72. каждом конкретном случае мы будем пользоваться тем из них, который более удобен.
Например, на рнс. 72 при некотором воображении можно представить себе перекресток двух улиц с односторонним движением, чего нельзя сказать о том же графе, изображенном на рис. 73; только математику легко усмотреть их изоморфизм. На языке графов можно сформулировать многие комбинаторные задачи, а также многие задачи из физики, химии, социологии, исследования операций.
2 25. Граф. Определение Рассмотрим теоретико-множественное произведение множеств Еп', Е'"', ..., Ени Р=Ен'ХЕ"'Х ... Х Ем (25.1) и его разбиение на две части Ос:Р (25.2) и ОсР, (25.3) *) См. сноску на стр. Пб, (Прим. перев.) причем (25.4) (25.5) Тогда б (а также н б) называют графом, определенным в Р. Граф б называют дополнением к б. В этой главе будем рассматривать частный вид графа ') (25.6) б~Р=ЕХЕ, где Š— конечное множество. Графы трактуются здесь, как у Кепи га [21] н Б ер ж а [8).
А В С В и Р А В С Р Е р Предетавлеиив в вида булевой матрицы Предетавлеиив в виде оат Рис. 74. Рис. 75. ГА = [А, В, Е, Е), ГС = ) А, 0'„ГЕ = (А, В, В), ГВ= (А, С), ГВ= [С, В), ГЕ=)Е). (25.7) В связи с этим граф') можно рассматривать как пару 6 =-(Е, Г), (25.8) ') Разумеется, определение графа должно включать множество Е, кото. рое порождает Р. ') Мы уже отмечали, что определение графа должно включать множество Е, которое порождает Е Х Е. Иначе исключаются изолированные вершины (не принадлежащие никакой паре).
По Бурбаки граф определяется фор. мулой (25.6); описание Бержа устраняет возможное недоразумение. 156 На рис. 74 — 78 приведены различные представления одного и того же графа; на рис. 74 — в виде сот, на рис. 75 в виде булевой матрицы, на рис. 76 — с помощью латинской матрицы, на рис. 77 — соответствием, на рис. 78 — с помощью стрелок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
