Введение в прикладную комбинаторику, Кофман А. (984071), страница 14
Текст из файла (страница 14)
20, /а Ь с а ет порядок подстановки з = ( (,а'аЬес( ) равен б, (16.19) а из рис. 21 заключаем, что /аЬса'е~ порядок подстановки в = ( (,Ь а е а с/ ) равен 6. (16.20) Количество элементов в цикле называют порядком цикла, Например, й-цикл имеет порядок й.
Теорема Н!. Порядок подстановки равен наименьшему общему кратному порядков циклов, определяющих класс эквивалентности, которому она принадлежит. Пусть подстановка з принадлежит классу (йь йм ..., я„), Ее всегда можно представить в виде произведения и подстановок гь вм ..., з (перестановочных между собой), первая из которых содержит и 1-циклов, вторая содержит и — 2йи 1-циклов и яе 2-циклов... и-я содержит и — пн„1-циклов и я„п-циклов. На рис.
22 дан пример такого разложения. 92 Таким образом, (16.21) з!зс зи В силу коммутативности зсз/ зт 12'''и' Для того чтобы з" была единичной подстановкой, достаточно, чтобы (16.22) необходимо и (16.23) это свойство зс зс Но наименьшее целое число т, для которого Рис. 2!.
выполняется, есть наименьшее общее кратное тех чисел 2, 3, ..., и, для которых й! > О, 1 = 1, 2, ..., п. е' !'465 !'здб Рис. 22. Рис. 23. Транспозиция. Транспозиция есть подстановка из класса (и — 2, 1, О, ..., О). (16.24) Она переставляет между собой два элемента, не меняя располо. жения остальных. Пример транспозиции (рис. 23) (а Ь е с! с)' (16.25) Теорема 1Ч. Всякая подстановка разлагается в произведение транспозиций. Способ доказательства теоремы пронллюстрируем на примере, яа аи- Ь е-~ -и с Ж %:. Пусть (16.26) и заданы транспозиции =(".:.":) (Н Ь с а е)' (16.27) Тогда как видно из рнс. 24.
(16.28) э = сАЬ;14~ Гт са се се Рис. 24. Произведение различных транспозиций не коммутативно. Например, (а Ь с а' е)(а Ь с и' е) (а Ь с а е)(а Ь с а' е) (а Ь с а е) (16.29) но (а Ь с а' е)(а Ь с а е) (а Ь с а' е) (а с Ь И е)(Ь а с и е) (Ь с а и е) (16.30) Четкость перестановки. Рассмотрим перестановку л на мно. жестве Е из и элементов. С этим множеством свяжем неупорядоченное множество Т„, образованное '/а(л — 1)и парами различных элементов Е, причем элементы в каждой паре записываются в том же порядке, что и в л. Например, с перестановкой л =(Ь е с( а с), (16.31) получающейся из подстановки на рис.
26, связываем неупорядоченное множество Т„= ((Ье), (Ь4, (Ьа), (Ьс), (ест, (еа), (ес), (с(а), (с(с), (ас)). (16.32) Рис. 26 показывает, как можно легко получить Т„без пропусков и повторений. 04 Четности п! и п~! либо все одинаковы, либо все противоположны (! = 1, 2, ...). Действительно, определим подстановку Е Рассматривая и'! и пв как нижние строки соответствующих под- становок, имеем гп! =п2 ). (16.
39) Отсюда следует, что число инверсий при переходе от и! к пв совпадает с числом инверсий при переходе от и! к пт. Таким образом, подстановки также распадаются на два класса (подстановка ( '1 принадлежит четному классу). Имеется п(/2 четных !к! ! подстановок и столько же нечетных. Группы и подгруппы подстановок. Рассмотрим все подстановки множества Е из и элементов. Как было показано, они образуют группу, элементы которой можно разбить на два класса: четных и нечетных подстановок. Четные подстановки образуют подгруппу: 1) единичная подстановка четна по определению; 2) обратная к четной подстановке также четная; 3) произведение четных подстановок четно.
Сформулируем еще несколько теорем. Теорема Ч. Всякая транспозиция есть нечетная подстановка. Теорема очевидна в силу определения транспозиции. Так как произведение 2п транспозиций дает четную подстановку, а произведение 2п + 1 транспозиций — нечетную, то справедливо следующее утверждение: Теорема И. Если подстановка з разложена в произведение транспозиций, то число их четно или нечетно в зависимости от того, чегна или нечетна з. Верно и обратное утверждение, Теорема тГП. Если число четных циклов четно, то подстановка четна; если это число нечетно, то подстановка нечетна. Приведем несколько примеров. Подстановки класса (1, 2, О, 1, О, О, О, О, 0) нечетны, так как содержат 2+ 1 = 3 четных циклов. Подстановки класса (О, 1, 1, 1, О, О, О, О, 0) четны, так как содержат 1+ 1 = 2 четных циклов.
Подстановки класса (3,0,1,0,0,0) четны, так как не содержат четных циклов. Т е о р е м а тгП1 (теорема Кали). Всякая конечная группа (Е, ») изоморфна некоторой группе подстаноэок ее элементов. Доказательство предоставим читателю в виде упражнения, '1 Соответствующая формула оригинала не верна, (Г1рлл!. лерга.) 96 УПРАЖНЕНИЯ 16А. Пусть заданы подстановки /ВАСРОВЕ) /САРВВОЕ) 'тСАОРЕВ0/ 10ЕАРВОС/ (АВРЕО 0 С( (САОРЕ0 В/ Найти: а) з!зззз, б) зззтз1, в) з!, г) (з!зззз) . 16Б.
Представить в цикловой записк подстановки з„ з,, зм а также а), б), в), г) из упражнения !6А. 16В. Перечислить классы подстановок а элементов, л = 1, 2, ..., 7. 16Г. Пусть а = б. Пересчитать подстановки следуюи!их классов: (б, О, О, О, 0), (1, 2, О, О, 0), (2, О, 1, О, 0), (О, 1, 1, О, 0), ((, О, О, 1, 0), (О, О, О, О, 1). 16Д. Для подстановок зо з„з, из упражнения !6А найти: а) з! ', б) (з!зз) , в) з!ззз! ', г) (з!зззз) (з! зз зз ). 16Е. Указать порядки подстановок зн з„з„а также а), б), в), г) из упражнения !6А.
16)К. Пусть Ь = (Ьь Ь„ ..., Ь„) — класс подстановки з. Описать класс й' подстановки з' = зз. 163. Разложить в произведение транспоэиций подстановки з1 и зз нз упражнения !6А. 16И. Определить четность следующих перестановок; (0АВСЕ), (ВСВАРЕ), (САОРЕВ0), (СОАРЕВ0). 16К. Найти группы подстановок, изоморфиые группам (Е, *), заданным нижеследующими таблицами (з — единица группы): с 2) Ь 1) а в а с а Ь с с а Ь 5) с с а Ь с а с а Ь с и с а Ь с 2 17.
Денумераторы цикловых классов В этом параграфе рассматриваются различные способы пересчета подстановок (или, что то же самое, перестановок), обладающих некоторыми свойствами. Процесс перечисления будет рассмотрен позже (гл. 1'тг, 2 41), 97 Напомним формулу (16.10) предыдущего параграфа: 1 (43! (зм ° ° ° йа) = !.а,!83з.а,! „~з,г ! ' где (!7.1) й! + 273! + ... + и 'г„= п. (17.2) Производящая функция, представляющая денумератор по- следовательности чисел Р(24, 4зг,..., !3 ), должна быть функцией п переменных.
Сопоставим г! 1-циклам, гг 2-циклам, ..., г„ и-циклам. Таким образом, Р'(го г„..., г )=лл Р(!г!, !зг, ° ° °, lг )г,'гг'... г„", (!7.3) где суммирование производится по всем и-выборкам (йь й,, ... ..., 43„), удовлетворяющим (17.2). Подставляя (17.!) в (!7.3), имеем )ю(г!' 23' ''' 2~)=4~~> 3 !3 !" 3 !!! !') ~ф) ' '' ( ~") (17''1) й, + 2/гз+ ... + и'я„=л, (17. 5) При суммировании по этой формуле удобно пользоваться неко- торыми свойствами экспоненциального г-преобразования. Приведем пример прямого использования (17.4).
Пусть и = 3: Рз(2! амгз)= 5аа!Е'!4! ( !') (4')'(8)*, (17.6) Выборки (/зьйг,йз), для которых Уг!+2(зг+Зйз=З,— это (3, О, 0), (1, 1, 0), (О, 0,1). Таким образом, РЗ( !' г' 3) Отсюда следует, что имеется одна подстановка класса (3, О, 0), три подстановки класса (1, 1, 0) и две — класса (О, О, 1), Действуя аналогично, можно получить Р! (2!) = г„ Рг (2!, 23) = 2! + гм Рз(2! 23 гз) г! + 32423+ 22з Р (г, гм гз, г ) = г44+ 6гг4гг+ Згг+ 8г!гз+ 6г4' Р;(г„г„г,, г,, г,) =гз+ 10гзгг+ 152,гг+ 202',г,+ (17,8) + 20гггз + ЗОг,г4 + 24гм Рз(2„2,, 23 г„гз, г,) = гз+ 152',г, + 45г',г, '+ 40г',гз + + 15ггз+ 120г4гггз+ 902гг4+ 4023+ 90г г4+ + 1442423+ 120гз. 88 Решение уравнения ~ гй„=п.
Можно решать это уравне»=» ние непосредственно последовательным лексикографическим перечислением. Напомним понятие лексикографического порядка. Лексикогра фи ческий порядок — это порядок, принятый в словарях. г-выборка (А>, В!, С>, ..., Я>) предшествует г-выборке (А,, Вм См ..., )7»), если й первых элементов (считая слева направо или справа налево, по соглашению) этих г-выборок равны, а (й+!)-й элемент первой предшествует (й+1)-му элементу второй.
Например, (3, 5, 7, 2, 5, 8) предшествует (3, 5, 7, 4, 1, 3), -> (В, С, Т) предшествует (В, В, А), (О, О, 1, 73) предшествует (О, О, 2, 18), (3, 8, 2, О, 0) предшествует (7, 1, 3, 0,0) (направление отсчета указано стрелкой). Разумеется, отношение порядка может быть произвольным: «предшествует», «больше чем», «меньше чем», «содержит» и т.д. Решим лексикографически уравнение в ~~ гй, =8. (!7.9) г=! Образуем восемь колонок й„йь ..., й!.
В строку (1) поме>цаем наибольшее возможное число, т. е. (1,0,0,0,0, О, 0 0), в строку (2) — следующее за ним по величине и удовлетворяющее (17.9), т.е, (О, 1, 0,0,0, 0,0, 1), и т. д. Таким образом, всего существуют 22 решения, приведенные в указанной таблице, которая читается справа налево. Там же приводятся решения при и = 3, 4, 5, 6. Рассмотрим некоторые интересные соотношения.
Имеем ~~~>Р(й„й„..., й„) =и!, (17.10) так как каждая подстановка входит в точности в один класс, а также Р*,(1, 1, ..., 1) =и! (17.11) Из (17.4) вытекает тогда Р„*(1, 1, ..., 1) =и! ~(» ° „... — ). (17.12) '> ! 'Ф>! 2 '«>! и "«»! Сравнивая (17.11) в (17.12), получаем т ! '»>! 2 ~а»! и "е»! l где суммирование производится по всем и-выборкам » (йь йм ..., Й„), для которых ~ гй, =и. Тождество (17.13) ча »=! сто называют тождеством Коши. Напомним формулу (10.53) из з 10: аы~ (игп ип1 и~а.
а) 3~2>'''\ — — — (!7.14) где й1 + йз+... + я„= и, й~ ) О, и суммирование производится л %1 по всем п-выборкам, для которых,д~ гй, =и. т=! Очевидно, что от формулы (17.14) можно перейти к (174) и обратно с помощью следующего соответствия: и"~~-~(г — 1)! г, анп(ин~, и"~, . и'"' 1) ~ — тР'(г г г ) (17.15) Заметим, что при выводе формулы Бруно (см. (10.46) и (10.51)) можно считать и',~ независимыми переменными гю так как там речь идет о символических биномиальных разложениях.
Следовательно, Ри('н 'р" ~ 'п)=~Р(йн йм ".~ йл)'!","" 'л"= Х а ~ а ь ! ( ! ) ( э. ) ... ( и ), (17.16) егп ы+~лз+мз+...~ Р.. Р. 1 2 8 . Р.о (17.17) Соотношениям (17.16) и (17.17) отвечает аналог (10.46): Р'"~'=ш(Р" +ш)", Р" — 'Р'„Р' — '1, в' — 'в„г=1, 2, ..., (17. 18) где положено и, =(г — 1)! а,. (17.19) Разложим (17.18) по формуле бинома: Рва+1 Ъ1 г н~ ° -. \1 и! г+~ а-г г=О г=з Р"' — ' Р*„Р'~ — ' 1, и' — ' в„ (17,20) г=1,2,...,п, где суммирование производится по всем и-выборкам (йн й„..., й„), л для которых ~гй,=п, й~)0. Используя экспоненциальное г ! разложение, подобное (10.51), заменяя а на Р', а на 1, и', на (г — 1)! з„можно получить о о (2) (2) (1) (21 (з) (з) о о 2 О (4) о о 1 2 (4) (5) (6) (5) о о (2) з г (8) (9) (10) (2) (12) (з) (!3) (4) (14) (5) (15) (16) (6) (17) (!8) (!9) (го) 4 З 2 йв (21) (Ы) зв ! 4в ) 6 о о о о о о о о о о о о 4 3 2 1 о о о о о о 3 з о 2 2 1 4 О 6 или л ° '~и и! Р*О! = ~~ ! )с, псгОср.-' =О (17.
21) Заменим пс, на г, по формуле (!7.19): л! Р'„.с.с = т,, ', г,, ср'„„ .Л( [п — г)! г! (17. 22) г О или Рл» вЂ”,гс Алгггср — ° г О (! 7.23) с' д Огг д гсС+гг — +" +г — е = — е =л дг, дг гс+г с + Отсюда получаем г д е — — с'е *; Р' — 'Рс, Р' — '1, 1=1, 2, 3, ... (17,25) где слева стоит де! дс.„р г — е =г — (1+Р'(+Р' — + ... ! Ргл ! ) дгг ! 2 ''' л! (! — Р!+ — Р— +...+ — Р— + Р Р д ° д «и Сг д л дг дг 2! ''' дг л! (17.26) а справа !"е''=!'(1+Р!+Р' —,с+ +Ргл '(„,), + )= Отождествляя коэффициенты при 1, получаем (17.28) или д ° г ° г д Р.=А Р: —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
