Введение в прикладную комбинаторику, Кофман А. (984071), страница 13
Текст из файла (страница 13)
(15.42) Обозначим через Ц„К Ц матрицу 1, 1=1, „К!1= 1, /=1, „А!1 — „541, Например, для и = 4 1 с элементами (15.43) 1, !'=2,3,..., п, 1 1 1 о о о (15. 44) Ц4К П (15.48) если заметить, что рег Ц зВ Ц = 1. Пример. Пусть и=5. о 1 1 1 1 о о о о о !О!! !!О! !!!О о о + 4 рег о (15.50) =0 рег рег В силу (15.11) последний член справа в (15.50) запишется так: 1 1 1 1 о 1 1 1 о о =рег 1 О 1+Зрег1 0 1 . (15,51) 1110, о рег Подставляя (15.51) в (15.50), получаем формулу, совпадающую при и= 5 с (15.47): регЦ,ВЦ=4регПзВЦ+12рег!!4КЦ, (15.52) По (15.11), учитывая инвариантность перманента при перестановках строк и столбцов, имеем регЦ „В Ц= (и — 1) регЦ „,К Ц, (15.45) регП „,К П = рег!! „,В Ц+ (и — 2) рег П „,К 1!.
(! 5.46) Подставим (15.46) в (15.45): рег Ц „В Ц = (и — 1) (рег !! и аВ 1! + (и — 2) рег Ц е аК Ц ). (! 5. 47) Заменим в (15,45) и на и — 1: регЦ„,В Ц=(и — 2) регЦ„КЦ. Тогда (15.47) запишется так: рег~!„ВЦ=(и — 1)(регЦ„,ВЦ+рег!!„,ВЦ), (15.49) В силу (15.49) 1О 1 1 1 о 1 О о 1О рег~ 1 О ! +рег 1 1 0 (15.53) рег 1(,В~!= 4 что опять приводит к (15.47) для п=б: реги,В !1= 4 рег!! зВ !1+ 12 рег11,К 1~, (15.54) если заметить, что 0 1 1 1 0 1 1 1 1 1/ рег 1 0 1 ! =Орег 1 О 1 +Зрег 1 0 ! . (15.55) 1 1 0 1 1 1 0 1 1 О Перепишем (14.25): Оп — — п0„, +( — 1)", и=1, 2, 3, ..., (15.56) и заменим п на гг — 1: 0„, =(и — 1) 0„+ ( — 1)" 0п-1 (и 1) ~и-2+ ( 1) (15.57) (15.58) Отсюда ( — 1)"=0„— п0„,= — 0„, +(и — 1) 0„э 0„= (и — 1) (О„! + 0„4, (15.59) (! 5.60) Г=О получаем новую формулу для числа беспорядков: л 1 0„= ~ ( — 1)'С„'(и — г)'(и — г — 1)" '.
(15.62) Применение перманентов булевых матриц. Формулы (15.35) и (15.42) можно получить непосредственно следующим образом. Подсчитаем число перестановок из п элементов, в которых не допускаются некоторые расположения элементов. Построим прямоугольную булеву матрицу, в которой на запрещенных местах стоят нули (на рис. 11 эти клетки заштрихованы), а на остальных местах — единицы. если заметить, что 0з = 1. Сравнивая (15.49) и (15.60), видим, что последовательности О, н рег !1„В~~ совпадают. Тем самым (15.42) доказано. Разлагая рег ~~ „В ~~ согласно (15.28): и ! рег!1„В!1= 2~ ( — 1)'С„'(и — г)'(и — г — 1)" ", (15.61) Тогда при указанных ограничениях перманент этой матрицы совпадает, по определению, с числом перестановок.
Вообще перманент булевой матрицы размера т Х ц совпадает с числом размещений, удовлетворяющих соот. з 4 5 О 7 ветствующим ограничениям. 1 1 1 ! 1 ! 1 С помощью таких рассмотрений можно непосредственно доказать 2 ' ' ' ' ' (15.38) и (15.42). В случае (15.38) з ! ! ! ! 1 ! ограничений нет и мы получаем все и! перестановок. Если все ограничения сводятся к наличию нулей на главной 5 ! ! ! ! ! ! диагонали, то получаем (18.42), так как любой беспорядок есть перестановка, в которой запрещенные позиции 7 ! ! ! 1 1 1 изображаются нулями на главной диа- гонали в соответствующей булевой маРис.
11. трице. Отметим, что перманент можно рассматривать как энумератор, хотя этот способ неудобен, когда число строк или столбцов в матрице велико. Более эффективный способ излагается в Ц 42 — 45 главы 1тг. Мы вновь вернемся к перманенту в 3 20. УПРАЖНЕНИЯ 15А. Вычислить по формуле (!5,1) перманенты матр иц 16В. Вычислить перманенты матриц из упражнения ! 5А по формуле (1513). 15В.
Вычислить по формуле (15.28) перманент матрицы 3 5 О 8 — 1 2 — 3 О 4 ! 3 7 2 — 1 О 8 16Г. Подсчитать число подстановок с ограничениями на расположение элементов, заданными матрицами: А В С Р Е А В С Р Е А В С Р В 7 А В С Р и тг А А А В С Р и г $16. Группы подстановок. Перестановки. Транспозиции Эти понятия играют важную роль в комбинаторике и мы напомним их. Подстановкой называется биекция ') конечного множества Е на себя (рис. 12).
Подстановку часто изображают в виде соответствия между двумя строками: =(; .'; .":) (16.1) ') Биекция — взаимно однозначное соответствие. ') с!а этом основании можно иногда не различать слова «перестановка» В «подстановка». первую строку называют «операндом», вторую — «результатом>. Порядок, в которо- записывается операнд, вооб- а гце говоря, несуществен: ), (16. 2) Подстановку можно представить, выписывая в строку и элементов Е и подписывая под ка- в У ждым из них его образ при бнекции.
Перестановкой множества Е называется впол- Рнс. !2. не упорядоченное множество, состоящее нз всех элементов Е. Если Е состоит из а элементов, то имеется а) таких множеств, Таким образом, подстановку можно охарактеризовать перестановкой, задаваемой нижней строкой'). Произведение двух подстановок. Структура группы. Пусть у=г(х), х, у г:— Е, у — образ элемента х при подстановке г, в=з(у), у, хан Е, г — образ элемента у прн подстановке з. Определим подстановку г = з [г (х) [ = зг (х), (16.3) с с с е е е в Р ° 1З.
Рис.!5. Рис. 14. 3 Я 4 и б 7 е и е в б 7 бе а) Рис. 1б. Например, если то ( ь и ) ( ь и ) ( и ь ) ' (16'5) На рис. 13 изображено это произведение. За единичную подстановку примем (а Ь с а е) Для каждой подстановки существуют симметричная ей слева и симметричная ей справа, совпадающие между собой (как на рис. 14). Легко проверить свойство ассоциативности: (з!з2) зг з1 (зззс) (16.7) Таким образом, выполняются все групповые аксиомы. Множество и! подстановок и элементов образует группу, называе. мую симметрической группой 5„, Группа Я„не коммутативна, так как для некоторых элементов (16.8) з!за Ф згз! Прежде чем ввести понятие цикла, укажем еще одно изображение подстановки, пример которого приведен на рис. 15.
С другой стороны, подстановку можно записать с помощью перестановки, если первые строки всех подстановок взять одинаковыми. Например, !а Ь с а е! (е й с Ь и) представляет (е и с Ь а! Цикл. Пусть задана биекция подмножества Еь ~ Е на себя. Если мы проходим, следуя ей, все элементы Ем начиная с некоторого а! ~ Еь и возвращаясь в него, то получаемую подстановку назовем циклом. Например, на рис. 16 представлен цикл, (1652734), на рис. 17 представлены циклы (1427) и (365), на рис.
18 — циклы (17), (2), (3), (456). Запишем эти подстановки с помощью циклов: (1652734) (рис. 16), (1427) (365) (рис. 17), (17) (2) (3) (456) (рис. 18). Обычно цикл записывают, начиная с наименьшего элемента (или с элемента с наименьшим индексом). Например, (365) — (653) (536). Часто удобно заменить символы в подстановке 89 на целые числа (или на элементы с целочисленными индексами). Цикл, состоящий из й элементов, называют й-циклом.
Например, (1652734) на рис. 16 есть 7-пикл; (1427) на рис. 17 есть 4-цикл; (2), (17), (456) на рис. 18 являются соответственно 1-циклом, 2-циклом, З-циклом. а" 4 а а т 8 4 4 г б 7 а) б) Рис 17. 2 г" г' 4 а Е 7 Рис. 18. Классы подстановок. Пусть Р— множество всех и! подстановок и элементов. Разобьем это множество на классы эквивалентности согласно цикловой структуре. Подмножество из Р образует класс (й) = (Аь йм ..., Й„), если для каждой подстановки из этого подмножества число 1-циклов равно йь число 2-циклов равно йм ..., число и-циклов равно А„. Пример.
На рис. 16 (й)=(0,0,0,0,0,0,1), на рис. 17 (й) = (О, О, 1, 1, О, О, 0), на рис. !8 (й) = (2, 1, 1, О, О, О, 0), Будем иногда писать (О, О, 1, 1) вместо (О, О, 1, 1, О, О, 0), если это не приводит к недоразумению. Т е о р е м а 1. Для любого класса (йь й,, ..., й ) иодстановок и элементов (!6.9) 90 2~ тй„= и.
к=! Это очевидно, ибо т-цикл содержит г элементов, а всего элементов в подстановке и, Те о р ем а П. Обозначим через Рйь Ам ..., й„) число подсгановок класса (йь !гм ..., Й„). Тогда ('"и 2 ' ' 'В ~р) П ''а! (16.10) где ~ М, = и. г=! Рассмотрим й„ г-циклов в подстановке из заданного класса. Так как безразлично, какой элемент брать в качестве начального в каждом из этих циклов, то эту подстановку можно запи- А сать г р различными способами. Учитывал, что циклы можно (16.11) дл'ггг! йнгМ йжМг! РйгЛгг г г С) дгггйг дгдй) два й) йггл® Рнс !9.
Эти подстановки представлены на рис. 19. Степени подстановки. Определим последовательно зз згз зр зр-1з (16.13) Очевидно, что все эти подстановки коммутативны: зрзч зчзр Например, если (16.14) переставлять между собой, получаем г~М,! различных способов записи. Следовательно, л1обу~о подстановку из класса (йь /гм ..., й„) можно записать (1~'й,!)(2~рйг!) ... (п~ й„!) способами.
Так как всего имеется и! возможных записей подстановок из этого класса, то получаем (16.10). Пример. Рассмотрим класс (1,О, 1, О) при п = 4. Тогда 4! 4 ° 3 ° 2 з~ = з = 6 (16.12) то ( а ь)(а ь ) ( и ь )' Все степени некоторой подстановки можно изобразить в виде схемы, как это показано на рис. 20. Однако если подстановка обладает несколькими циклами, такая схема громоздка. а е- а с = с — с Рис. 20. Аналогично вводятся отрицательные степени: в и=в 'в-', в и=з ив ', ..., в-и =в-и+'з-', (16,16) Рв и — з сз и (16. 17) Порядок подстановки. Порядок подстановки есть наименьшее целое положительное число р такое, что за= 1. (16,18) Например, как это видно из рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
