В.А. Носов - Комбинаторика и теория графов, страница 6

Пусть at+1 - первый повторившийся элемент, т.е. at+1 = ak , k ≤ t+1 Тогда выполнено at+1 = a1. Если, напротив, at+1 = ai для i ≥ 2, то тогда имеем P(ai-1) = ai , P(at) = ai и всилу биективности P получаем ai-1 = at, что противоречит тому, что at+1 - первое повторение. В последовательности a1, a2, … , at все элементы различны. Данная последовательность называется циклом длины t и обозначается (a1, … , at). Теперь любая подстановка P может быть записана в виде произведения независимых циклов с помощью следующей процедуры:- начинаем с любого элемента a1 ∈ Nn и выписываем цикл, содержащий a1. Еслиэтот цикл содержит все элементы Nn , то останавливаемся. Если нет, то удаляем из Nnэлементы построенного цикла и повторяем процедуру.33Полученное представление подстановки называется цикловой записью подстановки. Например, пусть дана подстановка 1 2 3 4 5 6 7 8 9 7 1 3 8 6 5 9 2 4P= Тогда ее цикловое разложение имеет вид(1 7 9 4 8 2) (3) (5 6 )Ясно, что цикловое представление однозначно определяет подстановку.

Подстановке соответствует цикловое представление с точностью до порядка следованияциклов.Если подстановка в цикловом представлении содержит один цикл, то она называется полноцикловой. Если подстановка степени n имеет в цикловом представлении kiциклов длины i, i ∈ 1, n , то система чисел (k1, k2, … , kn) называется цикловой структу-[]рой подстановки и обозначается 1k1 2 k2 K n k n . Ясно, что выполнено соотношение1k1 + 2k2 + … + nkn = nПокажем, что число полноцикловых подстановок степени n равно(n - 1)!♦ Действительно, любая полноцикловая подстановка степени имеет цикловуюзапись (1, i2, … , in), где i2, … , in - различные элементы множества{2, … , n}. Числонаборов i2, … , in равно (n - 1)!, и разные такие наборы опреде- ляют разные подстановки.

♦Можно доказать, что число подстановок степени n с цикловой структурой[1k1]2 k2 K n k n выражается формулой1k1⋅ k1 ! 2k2n!⋅ k 2 !L n k n ⋅ k n !Пусть подстановка P имеет цикловое представление:(a11 a12 … a1t1 ) (a21 a22 … a 2t2 ) … (as1 as2 … a sts )Тогда подстановка P-1 имеет цикловое представление:( a sts … as2 as1) … ( a 2t2 … a22 a21) ( a 1t1 … a12 a11)Данное утверждение проверяется непосредственным вычислением.3. Зафиксируем некоторую подстановку F и определим последовательность подстановокF, F2, F3, …oLoFздесь Fk = F123k раз34В силу конечности числа подстановок существуют натуральные k, l (k > l ), для которых выполненоFk = F lОтсюда следует F l−k = E, k - l > 0.Значит, для любой подстановки F существует натуральное числоp, такое, что Fp = E.Наименьшее из таких натуральных чисел называется порядком подстановки F.Теорема. Порядок подстановки равен наименьшему общему кратному длин еециклов.∨♦ Всякому циклу z соответствует подстановка z в которой элементы, не входящие в цикл, остаются на месте.Если z1, z2 - два цикла, не имеющие общих элементов, то справедливо∨∨∨∨z1 • z2 = z2 •z1Пусть для подстановки F имеем ее цикловое представление F = z1 z2 … zt , то выполнено∨k∨k ∨kF = z1 ⋅ z 2 ⋅ … z tk∨kКроме того ясно, что F = E ⇔ z i = E для всех i ∈1, t в силу независимости циклов.kПоскольку порядок цикла zi равен его длине, то порядок F равен наименьшему k , которое делится на длины всех циклов zi , i ∈1, t .

♦4. Пусть S (Nn) - симметрическая группа подстановок на элементахNn = {1, 2, … , n}. Будем говорить, что подстановки g1, … , gk порождают S (Nn) илиподстановки g1, … , gk являются системой образующих для S (Nn), если любая подстановка F представляется как произведение x1, … , xt, где xi ∈ { g1, … , gk, g 1−1 , L , g −k1 } .В этом случае пишут, S (Nn) = 〈 g1, … , gk 〉. Подстановка, имеющая цикловую структуруk1 = n - 2, k2 = 1, k3 = … = kn = 0 , называется транспозицией. Если единственный циклдлины 2 содержит элементы i, j, то транспозиция обозначается (i,j) (циклы длины 1опускаются в записи).Непосредственно проверяется, что справедливо равенство(a1, … , at) = (a1, at) … (a1, a3)(a1, a2)Поскольку каждая подстановка представляется в виде произведения циклов, акаждый цикл - в виде произведения транспозиций, то получаем35Теорема.

Множество транспозиций является системой образующих для симметрической группы.Укажем теперь другие системы образующиха) (1, 2), (2, 3), … , (n - 1, n)в) (1, 2), (1, 3), … , (1, n)с) (1, 2), (1, 2, … , n)Легко проверяются следующие равенства:(i, j) = (1, i)(1, j)(1, i)(i, j) = (i, 1) (1, 2) … (j - 1, j)(j - 1, j - 2) … (2, 1)(i, 1)(1, 2, … , n)j (1, 2)(1, 2)(1, 2, … , n)-j = (j + 1, j + 2)Из данных равенств следует, что множества а), в), с) являются образующимидля симметрической группы S(Nn) .5.

Рассмотрим две подстановки степени n, имеющие одинаковые цикловыеструктуры:A1 = (a11, … , a 1k1 ) (a21, … , a 2k2 ) … (at1, … , a tkt )A2 = (b11, … , b1k1 ) (b21, … , b 2k2 ) … (bt1, … , b tkt )Определим теперь подстановку F с помощью двустрочной записи: a11L a1k1 a 21L a 2 k2 L a t1L a tk t F=  b11L b1k1 b 21L b 2 k2 L b t1L b tk t Непосредственным вычислением можно проверить, что справедливо равенствоF-1A2F = A1(α)Подстановки A1, A2 , для которых существует подстановка F, удовлетворяющая соотношению (α), называются сопряженными.Легко проверить, что отношение сопряженности является отношением эквивалентности на множестве подстановок. Значит, все множество подстановок распадаетсяна классы сопряженных подстановок.Из предыдущего следует, что любые две подстановки, имеющие одинаковуюцикловую структуру, - сопряжены.Верно и обратное, если две подстановки сопряженны, то они имеют одинаковуюцикловую структуру.♦ Действительно, если z = (a11, … , a1p) - цикл длины p, то для любой подстановки F имеем F-1zF = (F-1(a11), … , F-1(a1p)) - цикл длины p.

Далее, еслиz1 … zt - произведение независимых циклов, то36F-1z1 … ztF = F-1z1F ⋅ F-1z2F … F-1ztF также произведение независимых циклов тех же длин. ♦Заметим, что сопряженные подстановки имеют одинаковый порядок.Уравнение (α), в котором заданы подстановки A1, A2 и неизвестна подстановкаF, называется уравнением Коши. Как следует из предыдущего, оно разрешимо тогда итолько тогда, когда подстановки A1, A2 имеют одинаковую цикловую структуру.Можно доказать, что если цикловая структура подстановок A1, A2 есть,[1k1][]2 k2 K n k n , то имеется точно 1k1 k1 ! 2 k2 k 2 ! K n k n k n ! решений уравнения Коши.Упражнения.1.

Найти число подстановок степени n, имеющих порядок 2.2. Решить уравнение Коши X-1AX = B,1 2 3 4 5где A = ,B= 3 4 1 2 51 2 3 4 5 4 2 5 1 33. Множество подстановок S(N3) разбить на классы сопряженных.37§ 6. Порождение сочетаний и перестановок.1. Рассмотрим теперь алгоритмические вопросы, связанные с порождением сочетаний и перестановок. Пусть дано множество А = {1, 2, … , n}.Порождение сочетаний. Приведем алгоритм, порождающий все сочетания (подмножества) множества А.Алгоритм “сочетания”.1.

Дано: множество А. Выход: последовательность подмножеств А.2. Начало: Пустое множество ∅.3. Пусть порождено множество S. Тогда следующее множество S ′ получаетсявключением в S наименьшего элемента, не принадлежащего S, и удалением изнего всех элементов, меньших включенного. Если таких элементов нет, стоп.♦ Справедливость алгоритма следует индукцией по n, если заметить, что алгоритм порождает сначала все подмножества множества A ′ = {1, 2, , n - 1}, затем повторяет эту последовательность, добавляя к каждому подмножеству n. Последним членом впоследовательности будет само множество А, и алгоритм автоматически остановится. ♦Укажем теперь алгоритм, который порождает все подмножества множества А,так, что каждое следующее отличается от предыдущего не более, чем на один элемент.Данный алгоритм определим индуктивно.Алгоритм “Сочетания добавлением/изъятием одного элемента”.Если n = 1, то выход алгоритма есть последовательность ∅, {1}.Пусть для n - 1 выходом алгоритма есть последовательность Ln-1 .

ОбозначимL n−1 - последовательность Ln-1, написанную в обратном порядке. Тогда для n выходомалгоритма будет последовательностьLn = Ln-1 , L n−1 ∨ {n},где L n−1 ∨ {n} означает, что к каждому члену последовательности L n−1 добавлен элемент n.Пример:L2 = ∅, {1}, {1, 2}, {2}L3 = ∅, {1}, {1, 2}, {2}, {2, 3}, {1, 2, 3}, {1, 3}, {3}.Справедливость алгоритма легко устанавливается индукцией по n, если заметить, чтоLn-1 заканчивается множеством {n - 1}. Первая половина последовательности Ln совпадает с Ln-1 и по индукции удовлетворяет нужным требованиям. Следующий элемент после Ln-1 есть {n - 1, n}, и затем проходится последовательность Ln-1 в обратном порядке с38добавлением элемента {n}, и нужные требования снова выполняются.

Поскольку первыйэлемент в Ln-1 есть ∅, то последний элемент в Ln есть {n}. Если длина Ln-1 есть 2n-1 , тодлина Ln есть2⋅2n-1 = 2n . ♦Представим теперь алгоритм, который порождает все r-сочетания n-множестваА = {1, 2, … , n} в лексикографическом порядке. Каждое r-сочетание представляетсячислами a1 < a2 < … < ar.Начало алгоритма: a1 = 1, a2 = 2, … , ar = r.Пусть порождено r-сочетание a1, a2, … , ar . Тогда определяется наибольшее ai, такое, чтоai + 1 не входит в данное сочетание.

Если таких ai нет (это происходит только в случаеa1 = n - r + 1, … , ar = n ), то стоп.Если такое ai есть, то образуем новое сочетание a1′ ,K , a r ′ , полагаяa1′ = a1 ,K , a i −1′ = a i −1,a r ′ = a i + 1, a i +1′ = a i + 2,K , a r ′ = a i + r − i .Проиллюстрируем алгоритм для n = 4, r = 2ШагиСочетанияai11,2221,3331,4142,3352,4263,4стопПредоставляется доказать в качестве упражнения индукцией по n, что описанный алгоритм порождает все r-сочетания n-множества.2. Перейдем теперь к вопросу порождения n-перестановокn-множества А = {1, 2, … , n}. Определим сначала индуктивный алгоритм А(n).