Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Посмотрим, удастся ли нам породить их сразу в лексикографическом по- рядке? Для этого заметим, что расположение перестановок в лексикографиче- ском порядке обладает следующими свойствами: • Нумерация начинается с тождественной перестановки (12 . . . n). • Все перестановки разбиваются на n блоков порядка (n − 1)!, в соответ- ствии с возрастающим значением элемента i = 1, . . . , n в первой позиции. • Внутри i-го блока перестановки множества {1, . . . , i − 1, i + 1, . . . , n} расположены лексикографически. Ясно, что это является готовой рекуррентной процедурой для построения перестановок n-элементного множества в лексикографическом порядке. 4.1. Дайте рекуррентную процедуру генерации перестановок в лексико- графическом порядке. Ответ. Например, так lex[ {}]:={{}}; lex[x ]:=Apply[Join, Table[Map[Prepend[#,x[[i]]]&,lex[Delete[x,i]]], {i,1,Length[x]}]] Обратите внимание, что здесь x произвольный список. Таким образом, чтобы породить перестановки {1, . . . , n} нужно вычислить lex[Range[n]]. Попробуем теперь дать нерекуррентную процедуру генерации переста- новок в лексикографическом порядке. Ясно, что для решения этой задачи необходимо уметь находить для каждой перестановки ту перестановку, ко- торая следует за ней в лексикографическом порядке. 4.2. Задайте функцию, сопоставляющую перестановке непосредственно следующую за ней в лексикографическом порядке. Ответ. Ограничимся возможным ответом, предоставляя читателю само- стоятельно разобраться — как советует Кнут! — в том, что здесь происхо- дит и почему эта программа вообще работает. 191 next[x ]:=Module[ {n=Length[x],i,j,t,y=x},i=n-1; While[Order[y[[i]],y[[i+1]]]==-1,i--]; j=n; While[Order[y[[j]],y[[i]]]==1,j--]; {y[[i]],y[[j]]}={y[[j]],y[[i]]}; Join[Take[y,i],Reverse[Drop[y,i]]]] Эта откровенно жульническая программа устроена так, что вычисление next[ {4,3,2,1}] дает {1,2,3,4}, как и задумано. Но почему это происхо- дит? 191 Детали на чуть другом языке можно найти в книге В. Липский. Комбинаторика для программистов – М:”Мир”, 1988, 213 C. 429 4.3. Задайте функцию, сопоставляющую перестановке непосредственно предшествующую ей в лексикографическом порядке. 4.4. А теперь снова задайте функцию, генерирующую перестановки в лек- сикографическом порядке. Ответ. Ну чего там, NestList[next,Range[n],n!-1]. Примерно так и работает команда LexicographicPermutations, опреде- ленная в пакете Combinatorica. Часто удобнее пользоваться не лексикографическим, а антилексикогра- фическим порядком, при котором смотрят не на возрастание элементов начиная слева, а на убывание элементов, начиная справа. Для примера перечислим элементы S 3 в антилексикографическом порядке: (1 2 3), (2 1 3), (1 3 2), (3 1 2), (2 3 1), (3 2 1). 4.5. Дайте рекуррентную процедуру генерации перестановок в антилекси- кографическом порядке. Указание. Для этого опишите свойства расположения перестановок в ан- тилексикографическом порядке — это и будет почти готовой рекуррентной процедурой. Ответ. Как и выше, mutatis mutandis: antilex[ {}]={{}}; antilex[x ]:=Apply[Join, Table[Map[Append[#,x[[i]]]&,antilex[Delete[x,i]]], {i,Length[x],1, -1}]] 4.6. Дайте итеративную процедуру генерации перестановок в антилекси- кографическом порядке. Указание. Для этого, наверное, полезно определить перестановку, непо- средственно следующую за данной в антилексикографическом порядке. 4.7. Задайте функцию, сопоставляющую перестановке непосредственно предшествующую ей в антилексикографическом порядке. 5. Транспозиции. 192 В настоящем разделе мы покажем, что симметрическая группа порож- дается самыми простыми мыслимыми перестановками. Циклы длины 2 на- зываются транспозициями. Таким образом, каждая транспозиция имеет вид w ij = (ij), 1 ≤ i 6= j ≤ n, она переставляет элементы i 6= j и оставляет все остальные элементы множества n на месте. Ясно, что w ij = w ji , так что в действительности различных транспозиций вдвое меньше, чем пар (i, j), i 6= j, они отвечают тем парам (i, j), в которых i < j. По определе- нию каждая транспозиция является инволюцией, т. е. элементом порядка 2. Иными словами, w −1 ij = w ij 192 На практике колокол неудобно сдвигать более, чем на одно место за один раз. Остановить колокол в верхнем положении равновесия — дело довольно тонкое. c Алиса Дикинсон Переборы с вариациями: теория и практика из книги Узоры симметрии. — М.: Мир, 1980, с.69–78. 430 5.1. Докажите, что каждая перестановка является произведением транс- позиций (ij), i < j. Решение. В следующем параграфе мы докажем, что каждая переста- новка является произведением циклов — даже независимых циклов. По- кажем поэтому, что каждый цикл является произведением транспозиций. Мы утверждаем, что каждый цикл длины l является произведением l − 1 транспозиции. В самом деле, легко видеть, что (i 1 i 2 . . . i l −1 i l ) = (i 1 i 2 ) . . . (i l −2 i l −1 )(i l −1 i l ). Назовем фундаментальной транспозицией транспозицию двух со- седних символов, s i = w i,i+1 = (i, i + 1), i = 1, . . . , n − 1. 5.2. Докажите, что каждая перестановка является произведением фунда- ментальных транспозиций s 1 , . . . , s n −1 5.3. С учетом предыдущей задачи нам достаточно доказать, что любая транспозиция w ij , i < j, является произведением фундаментальных. Бу- дем вести индукцию по j − i. База индукции j − i = 1, когда транспозиция w ij сама является фундаментальной. Пусть j − i ≥ 2, причем для всех транспозиций с меньшей разностью j − i утверждение уже доказано. Так как j − i ≥ 2, то можно найти такое h, что j < h < j. Легко видеть, что w ij = w ih w hj w ih , причем по индукционному предположению w ih и w hj уже являются произведениями фундаментальных транспозиций. Вот яв- ная формула для w ij , которая получается на этом пути: w ij = s i . . . s j −2 s j −1 s j −2 . . . s i . 5.4. Докажите, что группа каждая перестановка является произведением транспозиций (12), (13), . . . , (1n). 5.5. Докажите, что группу S n невозможно породить менее, чем n − 1 транспозицией. 5.6. Докажите, что группа S n порождается транспозицией (12) и длинным циклом (123 . . . n). 5.7. Верно ли, что группа S n порождается длинным циклом (123 . . . n) и любой транспозицией? Найдите необходимое и достаточное условие для того, чтобы S n порождалось длинным циклом (123 . . . n) и транспозицией (1m). Решение. Так как группа H = h(123 . . . n), (1m)i содержит все транспози- ции (i, i+m −1), то она содержит и все транспозиции вида (i, i+j(m−1)), где второй индекс понимается по модулю n. В случае, когда d = gcd(n, m −1) = 1 можно выбрать j такое, что j(m − 1) ≡ 1 (mod n). Тем самым, в этом 431 случае H содержит (12) и мы оказываемся в условиях предыдущей зада- чи. Если же d ≥ 2, то разобьем n на d блоков {1, 1 + d, . . . , n − d + 1}, {2, 2+d, . . . , n−d+2}, . . . , {d, 2d, . . . , n}. Ясно, что как (123 . . . n), так и (1m) переставляет блоки, так что никакое их произведение не может отобразить 1 в 2, оставив при этом 1+d на месте. Тем самым, H собственная подгруппа в S n . В действительности можно доказать, что порядок H равен d((n/d)!) d Минимальный пример, когда d ≥ 2 – это группа h(1234), (13)i ≤ S 4 порядок которой равен 8. 5.8. Докажите, что группа S n порождается транспозицией (12) и циклом (23 . . . n). 6. Переборы с вариациями. 193 При порождении перестановок в лексикографическом порядке каждая вторая получалась из предыдущей одной транспозицией. Но есть и такие, которые требуют b(n + 1)/2c транспозиций. Между тем для многих прило- жений важно уметь порождать перестановки в таком порядке, что каждая следующая отличается от предыдущей одной фундаментальной транспо- зицией — такой порядок перестановок называется minimum change order. Например, при умножении перестановки на фундаментальную транспо- зицию многие комбинаторные инварианты мало меняются, скажем увели- чиваются или уменьшаются на 1. Поэтому на списке перестановок, записан- ном в minimum change order, многие комбинаторные алгоритмы работают значительно быстрее. Исторически эта задача возникла в связи с вызваниванием переборов с вариациями = change ringing 194 . Чтобы понять, о чем идет речь, необ- ходимо знать, что традиция английского колокольного звона радикально отличается как от русской, так и от континентальной европейской. В то время как на Руси звонарь ударяет в колокол раскачивая его язык , в Ан- глии он поворачивает сам колокол при помощи специального колеса. Это значит, что на английских колоколах невозможно вызванивать сложные мелодии. Вызванивание переборов с вариациями начинается с нисходящей гаммы, в которой звучат все колокола начиная с самого маленького до са- мого большого. После этого вызваниваются всевозможные перестановки восьми колоколов — вариации = changes. Максимум того, что физически осуществимо в очередной вариации, это придержать один их колоколов с тем, чтобы переставить его с соседним колоколом по сравнению с преды- дущей вариацией. Это и есть генерация перестановок в minimum change order. 193 Если бы ты был младенцем с Криптона, то умел бы, к примеру, летать... — Я не раз летал, — с достоинством ответил Жихарь. — Я целых два раза летал посред- ством горячего воздуха. Правда, второй раз в полном беспамятстве... — Посредством горячего воздуха нынче только ленивый не летает, — сказал Колобок. — Нет, тебе бы полагалось лететь без пара и без крыльев, одною силою духа. c Михаил Успенский, Кого за смертью посылать 194 A. T. White, Ringing the cosets. — Amer. Math. Monthly, 1987, October, p.721–746. 432 Для примера перечислим элементы S 3 в обычном кампанологическом порядке, где принято гонять самый маленький колокол: (1 2 3), (2 1 3), (2 3 1), (3 2 1), (3 1 2), (1 3 2). Обратите внимание, что здесь происходит. Вначале первый колокол пе- ремещается на последнюю позицию — на кампанологическом языке это называется hunting up, после чего происходит перестановка двух других колоколов и первый колокол снова перемещается на первую позицию — hunting down. При генерации S n первый колокол попеременно перемещается между первой и последней позицией (n − 1)! раз. Эту процедуру генерации пере- становок называют алгоритмом Джонсона–Троттера 195 . Она реализо- вана в функции MinimumChangePermutations пакета Combinatorica 196 С точки зрения удобства программирования несколько естественнее го- нять не первый, а последний колокол, иными словами порождать S 3 в сле- дующем порядке: (1 2 3), (1 3 2), (3 1 2), (3 2 1), (2 3 1), (2 1 3). 6.1. Напишите рекуррентную программу, реализующую алгоритм Джон- сона—Троттера в варианте с гоном последнего элемента. Ответ. Вот вариант такой процедуры, реализованный с особым цинизмом. На четных перестановках 1, . . . , n −1 происходит гон n вниз, а на нечетных — гон вверх. Вероятно, большинство пользователей вместо Range[n,1,- 1] предпочли бы использовать Range[n] и заменили условие и порядок исходов в условном операторе на противоположные. minperm[0]= {{}}; minperm[n ]:=Flatten[Outer[ If[Signature[#1]==1, Insert[#1,n,#2],Insert[#1,n,n-#2+1]]&, minperm[n-1],Range[n,1,-1],1],1] 6.2. То же, но с гоном первого элемента. 6.3. Напишите итеративную программу, реализующую алгоритм Джонсо- на—Троттера в варианте с гоном последнего элемента. Указание. При желании можно написать примерно такую же процедуру, как та, которую мы использовали при построении перестановок в лексико- графическом порядке. 197 195 S.M.Johnson, Generation of permutations by adjacent transpositions. – Math. Com- put., 1963, vol.17, p.282–285. 196 Начиная с версии 10, основная функциональность пакета Combinatorica включена в ядро Mathematica 197 Детали изложены в упомянутой выше книге В. Липский. Комбинаторика для программистов – М:”Мир”, 1988, 213 C. 433 7. Декремент. 198 В этом разделе мы построим гомоморфизм sgn : S n −→ {±1}. Обо- значим через m = |n/σ| число орбит перестановки σ ∈ S n . По определе- нию m = r + s, где r — количество истинных циклов перестановки σ, а s = | Fix(σ)|. Разность decr(σ) = n − m называется декрементом переста- новки σ. Знаком перестановки σ ∈ S n называется sgn(σ) = ( −1) decr(σ) = ( −1) n −m = m Y i=1 ( −1) |X i |−1 , где произведение берется по всем орбитам X 1 , . . . , X m перестановки σ. Достоинством этого определения является то, что, с одной стороны, лег- ко доказать его совпадение с обычным определением в терминах транспо- зиций, к которому мы вернемся в следующих двух параграфах, а с другой стороны, так как знак определен в терминах самой перестановки σ, вопро- са о корректности при этом не возникает. В следующих параграфах мы дадим еще два определения знака, но проверить их корректность и совпа- дение друг с другом заметно сложнее. В некоторых старых книгах знак перестановки назывался ее сигнатурой, в связи чем в Mathematica знак перестановки x вычисляется посредством Signature[x]. Signature[x] знак перестановки x 7.1. Докажите, что τ 1 , . . . , τ l если транспозиции, то sgn(τ 1 . . . τ l ) = ( −1) l Решение. Индукция по l. Случай l ≤ 1 очевиден. Для индукционно- го перехода достаточно показать, что знаки τ 2 . . . τ l и τ 1 . . . τ l различны. Мы покажем, что если π — любая перестановка, а τ — транспозиция, то sgn(τ π) = − sgn(π). Достаточно показать, что число орбит изменяется на 1. Пусть τ = (pq). Орбиты π, не содержащие ни p, ни q, продолжают оставаться орбитами τ π. Поэтому нам нужно рассмотреть следующие два случая: p, q лежат в различных орбитах, p, q лежат в одной орбите. Если p, q лежат в различных орбитах, то (pq)(pi 2 . . . i r )(qj 2 . . . j s ) = (pi 2 . . . i r qj 2 . . . j s ) так что в этом случае две орбиты сливаются в одну. Если p, q лежат в одной орбите, то (pq)(pi 2 . . . i r qj 2 . . . j s ) = (pi 2 . . . i r )(qj 2 . . . j s ), так что в этом случае одна орбита распадается на две. Проанализировав это рассуждение, внимательный читатель может за- метить, что оно доказывает значительно более точное утверждение. 198 Все, что дается даром, наиболее ценно. Все наиболее ценное должно даваться даром. c Поль Валери., Тетради 434 7.2. Пусть d = decr(σ). Докажите, что σ можно представить как про- изведение d транспозиций, причем d наименьшее число, обладающее этим свойством. Таким образом, декремент перестановки σ есть в точности длина этой перестановки по отношению к множеству транспозиций, т. е. наименьшее число d ∈ N 0 такое, что σ можно представить в виде произведения d транс- позиций. Поскольку m ≥ 1, декремент принимает наибольшее значение на множестве длинных циклов: длинные циклы и только они требуют для своего выражения n − 1 транспозиции. 8. Знакопеременная группа. 199 8.1. Докажите, что отображение sgn : S n −→ {±1} является гомоморфиз- мом. Решение. Если перестановку π можно представить как произведение l транспозиций, а перестановку σ — как произведения m транспозиций, то, конкатенируя эти представления, мы выразим πσ как произведение l + m транспозиций. Таким образом, sgn(πσ) = ( −1) l+m = sgn(π) sgn(σ). Назовем перестановку σ четной, если sgn(σ) = 1, и нечетной, если sgn(σ) = −1. Например, l-цикл требует для своего выражения l − 1 транс- позиции и, тем самым, цикл четной длины нечетен, а цикл нечетной длины четен. Ядро sgn называется знакопеременной группой и обозначается A n , от первой буквы слова alternating. По определению A n состоит из всех четных перестановок. Множество S n \ A n всех нечетных перестановок образует смежный класс S n по A n в качестве представителя которого можно выбрать, например, любую транс- позицию: S n = A n t (S n \ A n ) = A n t A n (12). Для любого n ≥ 2 группа A n является подгруппой индекса 2 в S n и, значит A n E S n . Порядок группы A n равен n!/2. 8.2. Постройте вложение S n в A n+2 . Покажите, что S n нельзя вложить в A n+1 По определению группа A n порождается всевозможными произведени- ями двух различных транспозиций (ij)(hk). Однако обычно удобнее поль- зоваться другой системой образующих. 8.3. При любом n ≥ 3 группа A n порождается 3-циклами. 199 При любом числе колоколов ровно половина всех вариаций имеет одну природу и ровно половина — другую. В чем именно заключается эта природа, мне не дано судить, но, как станет мало-помалу ясно, в ней непременно следует разобраться, прежде чем мы сможем постичь науку композиции звонов и их исполнения. c C.A.W.Troyte, Change Ringing 435 Решение. Для доказательства теоремы нам нужно выразить произведе- ние двух транспозиций (ij)(hk) как произведение 3-циклов. Если оказыва- ется |{i, j, h, k}| = 3, то это произведение само является 3-циклом. С другой стороны, если |{i, j, h, k}| = 4, то (ij)(hk) = (ij)(ih)(ih)(hk) является про- изведением двух 3-циклов. 8.4. Докажите, что группа A n порождается 3-циклами (123), (124), . . . , (12n). 8.5. Докажите, что группа A n порождается 3-циклами (123), (234), . . . , (n − 2, n − 1, n). Указание. Группа A n порождается подгруппой A n −1 , стабилизирующей n, и одним (любым) циклом, перемещающим n. 8.6. Пусть n нечетно, верно ли, что группа A n порождается 3-циклами (123), (145), . . . , (1, n − 1, n)? 8.7. Докажите, что группа A n порождается 3-циклом (123), и либо длин- ным циклом (12 . . . n) при нечетном n, либо циклом (23 . . . n) при четном. 8.8. Покажите, что при n ≥ 4 центр группы A n тривиален. Решение. Для любого π 6= id найдется i такое, что π(i) 6= i. Так как n ≥ 4, то найдутся j, h такие, что все четыре индекса i, π(i), j, h различны. Тогда π(ijh)π −1 = (π(i), π(j), π(h)) 6= (i, j, h). 8.9. Докажите, что при n ≥ 5 все 3-циклы в A n сопряжены. Верно ли это для n = 4? Решение. Мы уже знаем, что 3-циклы сопряжены в S n . Пусть (ijh) и (klm) — два любых 3-цикла, а π ∈ S n – перестановка такая, что π(ijh)π −1 = (klm). Если перестановка π четна, мы достигли своей цели. Если пере- становка π нечетна, но n ≥ 5, то найдутся такие r, s, что все 5 индек- сов i, j, h, r, s различны. Тогда (rs) коммутирует с (ijh) и, тем самым, π(rs)(ijh)(π(rs)) −1 = (klm), причем π(rs) четна. С другой стороны, цен- трализатор 3-цикла содержит по крайней мере 3 элемента, поэтому в A 4 имеется не более 12/3 = 4 циклов, сопряженных с данным. Это значит, что 3-циклы в A 4 разбиваются на два класса сопряженности. 9. Инверсии. 200 Забудем про определение из § 9 и дадим другое определение знака. Поло- жим sgn(σ) = ( −1) l , если σ можно представить как произведение l транс- позиций σ = τ 1 . . . τ l . Это определение эквивалентно нашему основному определению через декремент. Однако, из этого нового определения совер- шенно неясно, почему знак определен корректно, т. е. почему перестанов- ку σ нельзя представить в виде σ = τ 1 . . . τ l = ρ 1 . . . ρ m , 200 Мне, конечно, легче сойти с ума, чем им. Я, например, увижу на карте Пакиста- на: там, где должен быть Исламабад — там оказалось Равалпинди, а там, где прежде было Равалпинди, увижу Исламабад — и все, я сбрендил. А они все даже не заме- тят. c Венедикт Ерофеев, Из записных книжек 436 где l и m имеют разную четность? Это можно доказать методом совместной индукции 201 , но мы не будем обсуждать доказательство здесь. Вместо это- го покажем, что знак вполне характеризуется тем, что это гомоморфизм, переводящий транспозиции в −1. 9.1. Для любого n ≥ 2 знак sgn является единственным нетривиальным гомоморфизмом ϕ : S n −→ {±1}. Решение. В самом деле, пусть (pq), (rs) — две транспозиции в S n , а π — любая перестановка такая, что π(p) = r, π(q) = s. Тогда π(pq)π −1 = (rs), так что при всех гомоморфизмах ϕ : S n −→ {±1} в абелеву группу {±1} транспозиции принимают одно и то же значение. Если это значение равно 1, то гомоморфизм ϕ тривиален. Если же оно равно −1, то ϕ = sgn. 9.2. При n ≥ 2 знакопеременная группа A n является единственной под- группой индекса 2 в S n Сейчас мы дадим третье определение знака перестановки, в терминах длины этой перестановки по отношению к множеству фундаментальных транспозиций. Говорят, что пара (i, j) образует инверсию = inversion = Fehlstand для перестановки σ ∈ S n , если i < j, но σ(i) > σ(j). Обозначим через inv(σ) общее число инверсий перестановки σ, т. е. количество всех пар (i, j), 1 ≤ i < j ≤ n, образующих инверсию для σ. Заметим, что многие авторы называют инверсией не саму пару (i, j), а ее образ (σ(i), σ(j)) под действием σ. Кнут утверждает, что понятие ин- версии ввел в 1750 году Крамер в книге Introduction ` a l’analyse des lignes courbes alg´ ebriques, но, конечно, трудно себе представить, чтобы Секи Кова и фон Лейбниц не владели этим понятием лет за 70 до Крамера, когда они одновременно — и, насколько мы в состоянии судить, независимо — ввели понятие определителя. Однако в шпенглеровском смысле понятие инверсии гораздо старше и уже абсолютно отчетливо выступает в китайских текстах III в. до н.э. 9.3. Докажите, что для любой перестановки sgn(σ) = ( −1) inv(σ) Решение. Каждая транспозиция есть произведение нечетного числа фун- даментальных транспозиций. Умножение на фундаментальную транспози- цию создает или убивает ровно одну инверсию. В действительности, имеет место гораздо более точное утверждение. 9.4. Пусть d = inv(σ). Докажите, что σ можно представить как произ- ведение d фундаментальных транспозиций, причем d наименьшее число, обладающее этим свойством. Теперь мы в состоянии дать еще одно определение знака перестановки — можно думать, что это шутка, но в действительности, это цитата взято из учебника высшей алгебры Куроша: sgn(σ) = Y 1 ≤i σ(i) − σ(j) i − j . 201 А.И.Кострикин, Введение в алгебру, ч.I: Основы алгебры. – М.: Наука, 1994 437 При всей своей неестественности 202 это определение обладает одним тех- ническим преимуществом, а именно, для этого определения очевидно, что sgn является гомоморфизмом. Для этого нужно лишь заметить, что в дей- ствительности произведение в этой формуле берется по {i, j} ∈ V 2 (n). В частности, для любой перестановки π имеем Y 1 ≤i σ(i) − σ(j) i − j = Y 1 ≤π(i)<π(j)≤n σ(i) − σ(j) i − j Это значит, что следующее свойство получается даром. 9.5. Отображение ( −1) inv : S n −→ {±1}, π 7→ (−1) inv(π) , является гомо- морфизмом. Решение. В самом деле, ( −1) inv(πσ) = Y 1 ≤i πσ(i) − πσ(j) i − j = = Y 1 ≤i πσ(i) − πσ(j) σ(i) − σ(j) Y 1 ≤i σ(i) − σ(j) i − j = ( −1) inv(π) ( −1) inv(σ) . 9.6. Дайте еще одно доказательство того, что для любого n ≥ 2 знак sgn является единственным нетривиальным гомоморфизмом ϕ : S n −→ {±1}. Решение. Как мы только что показали, отображение ( −1) inv является гомоморфизмом S n −→ {±1}. Этот гомоморфизм нетривиален, так как, например, у транспозиции τ = (1, 2) всего одна инверсия, и, следовательно, ( −1) inv(τ ) = −1. В силу единственности знака гомоморфизм (−1) inv обязан совпадать с sgn. 10. Принцип инволюций. 203 Перестановка называется инволюцией, если ее квадрат равен id. Меж- ду большинством математиков и специалистами по теории групп существу- ет расхождение в понимании того, является ли сама тождественная пере- становка id инволюцией. Большинство математиков считают ее тривиаль- ной инволюцией. В то же время в теории групп инволюцией называется только элемент порядка 2. 202 Эпитет неестественность относится не к выражению ( −1) inv(σ) как таковому, на- оборот, с точки зрения теории групп Вейля inv(σ) совпадает с n(σ), числом положи- тельных корней, которые становятся отрицательными под действием σ и, тем самым, с l(σ) — длиной σ в Коксетеровских образующих. Нет ничего естественнее этого опре- деления! Однако выражать ( −1) inv(σ) как дурацкое произведение!!! Такое определение было бы уместно в учебнике математического анализа, как часть общей перверсивно- декадентской парадигмы. Но цель курса алгебры прямо противоположна — культи- вировать радость, силу, вкус и привычку к естественности ! 203 Решением Комиссии по переименованиям астероиду номер 35627 возвращено ис- торическое название “астероид номер 27635”. c ВНиколай Фоменко 438 10.1. Напишите программу, порождающую все инволюции. Указание. Каждая инволюция n либо оставляет n на месте и тогда она получается из инволюции n − 1, либо она переставляет n с каким-то i, 1 ≤ i ≤ n − 1, и тогда она получается из такой инволюции n − 1, кото- рая оставляет на месте i. 10.2. Вычислите количество инволюций в симметрической группе S n Под действием инволюции π множество X разбивается на одноэлемент- ные орбиты {x}, отвечающие инвариантным элементам x = πx, и двух- элементные орбиты {x, y}, отвечающие энантиоморфным парам x, y, где y = πx 6= x. Обозначим через X π множество неподвижных точек. Только что сказанное означает, что если π, σ — любые две инволюции на конеч- ном множестве X, то порядки множеств X π и X σ сравнимы по модулю 2. В частности, если инволюция π имеет на X нечетное количество непо- движных точек, то и любая другая инволюция σ имеет на X по крайней мере одну неподвижную точку. Это несложное соображение, называемое принципом инволюций, имеет далеко идущие следствия. Стандартное доказательство теоремы Лагранжа о том, что любое це- лое представляется в виде суммы четырех квадратов, приводимое в любом учебнике теории чисел, состоит из двух частей: • тождества Эйлера, сводящего все к представимости простого числа, • (доказанной Эйлером) теоремы Ферма о представлении простых чисел в виде суммы двух квадратов. При этом обычно считается, что именно вторая часть требует некоторых усилий, скажем построения арифметики целых гауссовых чисел. Surprise!!! 10.3. Докажите следующую теорему Ферма: любое простое p ≡ 1 (mod 4) представимо в виде суммы двух квадратов. Иными словами, найдутся та- кие m, n ∈ N, что p = m 2 + n 2 Решение. Приведем совершенно замечательное доказательство Цагира, основанное на принипе инволюций 204 . Рассмотрим множество X = {(x, y, z) | x, y, z ∈ N, x 2 + 4yz = p }. Легко видеть, что отображение h : X −→ X заданное посредством (x, y, z) 7→ (x + 2z, z, y − x − z), если x < y − z, (2y − x, y, x − y + z), если y − z < x < 2y, (x − 2y, x − y + z, y), если 2y < x, является инволюцией (проверьте!). Ясно, что у этой инволюции ровно одна неподвижная точка на X, а именно, (1, 1, l), где p = 4l + 1. По принципу инволюций тогда инволюция g : X −→ X, (x, y, z) 7→ (x, z, y), тоже имеет 204 D.Zagier, A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares. — Amer. Math. Monthly, 1990, vol.97, N.2, p.144. 439 по крайней мере одну неподвижную точку (m, n, n), так что p = m 2 + 4n 2 , как и утверждалось. 11. Беспорядки. Перестановка π называется беспорядком = derangement, если она не оставляет на месте ни одного символа, иными словами, если π(i) 6= i для всех i. Задача вычисления количества беспорядков D n называется задачей Монмора. Вот ее простой частный случай. 11.1. Сколькими способами можно расставить шахматной доске 8 ладей так, чтобы ни одна из них не била другие и чтобы ни одна не стояла на главной диагонали a8–h1? 11.2. Определите функцию, выясняющую, является ли данная переста- новка беспорядком. Ответ. Например, вот как это сделано в пакете Combinatorica: DerangementQ[x ]:=FreeQ[Range[Length[x]]-x,0] 11.3. Напишите программу, порождающую все беспорядки степени n. 11.4. Проведя численный эксперимент, постарайтесь угадать, к чему стре- мится отношение количества беспорядков порядка n к общему количеству всех перестановок степени n при росте n. Ответ. Ответ совершенно удивителен, это отношение чрезвычайно быст- ро стремится к 1/e. С точки зрения всех практических целей уже для небольших значений n (порядка нескольких десятков) вероятность того, что случайно выбранная перестановка является беспорядком, не зависит от n. Например, если пальто в гардеробе выдаются случайным образом, то вероятность того, что уходя из театра каждый зритель возьмет чужое пальто, не зависит от количества зрителей. А теперь объясним получившийся ответ. 11.5. Вычислите количество D n беспорядков в общем случае. Ответ. По формуле решета получаем, что D n = n! 1 − 1 1! + 1 2! − . . . + (−1) n 1 n! . Интересно, что формула в скобках – это начало разложения в ряд для e −1 Таким образом, для не слишком маленьких n число e −1 > 1/3 является очень хорошим приближением для отношения D n /n!, т.е. вероятности то- го, что наугад взятая перестановка n символов не оставляет на месте ни одного символа. Совершенно удивительно, что эта вероятность практиче- ски не зависит от n! Как замечает по этому поводу Райзер, для всех практических целей вероятность равна e −1 = для гренладских китов π = 3. В действительности, совсем легко указать и явную рекуррентную фор- мулу для определения количества беспорядков степени n. Следующее про- 440 стое рассуждение взято из книги 205 . Пусть D n есть количество беспорядков степени n. • Пусть π — беспорядок степени n − 1. Умножая π на транспозицию (i, n), для какого-то 1 ≤ i ≤ n − 1, мы получим беспорядок степени n. Эта процедура даст (n − 1)D n −1 беспорядков степени n. • Однако, не каждый беспорядок степени n получается таким образом. А именно, пусть π перестановка степени n −1, оставляющая на месте ровно один элемент, а именно, i, 1 ≤ i ≤ n − 1. Тогда π(i, n) также является беспорядком степени n. Ясно, что эти две процедуры дадут нам все беспорядки степени n. А имен- но, для любого беспорядка степени n найдется такое i, 1 ≤ i ≤ n − 1, что π(i, n) оставляет на месте n. Но тогда ограничение π(i, n) на первые n − 1 символ либо является беспорядком, либо имеет единственную неподвиж- ную точку i, причем эти возможности являются взаимоисключающими. 11.6. Напишите программу, вычисляющую количество беспорядков степе- ни n, и сравните ее с Round[N[n!/E]]. Ответ. Вот непосредственная реализация описанного выше алгоритма: derang[1]=0; derang[2]=1; derang[n ]:=derang[n]=(n-1)*derang[n-1]+(n-1)*derang[n-2] 11.7. Сколько перестановок из S n оставляют на месте ровно m символов? 11.8. Напишите программу, порождающую все перестановки степени n, имеющие ровно m неподвижных точек. Указание. Вначале породите все перестановки, оставляющие на месте точки 1, . . . , m и только их. The game never ends, but not the players. § 5. Циклы Наша стратегия состоит в том, чтобы одному биться против деся- ти, наша тактика — в том, чтобы десяти биться против одного. Мао Цзе-Дун 1. Циклы. 206 Фиксируем какую-то перестановку π ∈ S n . Определим на множестве n = {1, . . . , n} отношение ∼, полагая i ∼ j, если j = π k (i) для k ∈ Z. Очевидно, что отношение ∼ является эквивалентностью. Иными словами, оно • рефлексивно: i = id(i) = π 0 (i); • симметрично: если j = π k (i), то i = π −k (j); 205 J.L.Snell, Introduction to probability theory with computing. — Prentice Hall, 1975. 206 Revolution is the opiate of the intellectuals. c Karl Marx 441 • транзитивно: если j = π k (i) и h = π l (j), то h = π k+l (i). Таким образом, с каждой перестановкой π связано разбиение множе- ства n на классы эквивалентности ∼, эти классы называются орбитами π. Тем самым, n = X 1 t . . . t X m , где X 1 , . . . , X m суть орбиты пере- становки π. Иногда множество орбит перестановки σ обозначается через n/σ = {X 1 , . . . , X m }. Орбиты, содержащие более одного элемента, будут называться нетривиальными. С каждой перестановкой π ∈ S n можно связать два подмножества в n, а именно, множества Fix(π) = {i ∈ n | π(i) = i}, Mob(π) = {i ∈ n | π(i) 6= i} неподвижных alias стабильных точек и подвижных alias мобильных точек. Иными словами, Fix(π) является объединением всех одноэлемент- ных орбит, в то время как Mob(π) является объединением всех нетривиаль- ных орбит. Ясно, что Fix(π) и Mob(π) устойчивы под действием π, причем n = Fix(π) t Mob(π). Перестановки π и σ называются независимыми, если Mob(π) ∩ Mob(σ) = ∅. Перестановка σ ∈ S n называется циклом, если множество ее мобильных элементов представляет собой одну орбиту под действием σ. В этом случае Mob(σ) часто называется также носителем цикла σ, а порядок | Mob(σ)| — его длиной. Циклы длины 1 называются тривиальными, цикл длины ≥ 2 называется истинным циклом. Обычно, говоря о циклах, математики имеют в виду истинные циклы, однако, из программистских соображений нам будет удобнее считать id циклом и писать id = (1) = (2) = . . . = (n). Циклы настолько часто используются в вычислениях, что нам будет удобно ввести для них специальные обозначения. Пусть i 1 , . . . , i l ∈ n — набор попарно различных символов. Тогда через (i 1 . . . i l ), обозначается цикл длины l с носителем {i 1 , . . . , i l }, под действием которого i 1 7→ i 2 7→ i 3 7→ . . . 7→ i l 7→ i 1 , а все остальные элементы множества n остаются на месте. Один и тот же цикл может быть записан по разному: (i 1 i 2 . . . i l ) = (i 2 . . . i l i 1 ) = . . . = (i l i 1 . . . i l −1 ). Обычно для записи циклов мы будем пользоваться именно такой записью, которая называется циклической. 1.1. Напишите программу, возвращающую запись цикла (i 1 i 2 . . . i l ) как перестановки степени n. Ответ. В пакете Combinatorica это делается при помощи функции 442 PermutationWithCycle[n ,l ]:= FromCycles[Append[( {#}&) /@ Complement[Range[n],l],l]] 1.2. Вычислите обратный к циклу. Ответ. Ясно, что обратный к циклу (i 1 . . . i l ) равен (i l . . . i 1 ), так что для нахождения обратного достаточно применить к циклической записи функ- цию Reverse. 2. Длинные циклы. Перестановка σ называется длинным циклом, если все множество n образует одну орбиту под действием σ. Длинные циклы, называемые так- же элементами Коксетера, представляют собой один из наиболее инте- ресных типов перестановок. Особенно часто используются следующие два взаимнообратных длинных цикла: RotateRight = (1 2 3 . . . n), RotateLeft = (n n − 1 n − 2 . . . 1). 2.1. Найдите количество длинных циклов в S n Решение. Запись длинного цикла имеет вид (π(1), . . . , π(n)) для некоторо- го π ∈ S n . Таким образом, количество различных записей длинных циклов равно n!. Однако, как было уже замечено, применение RotateRight к за- писи длинного цикла не меняет этот цикл. Так как порядок RotateRight равен n, то любой длинный цикл допускает ровно n различных записей. Это значит, что количество n-циклов на n-элементном множестве равно n!/n = (n − 1)!. 2.2. Напишите программу, генерирующую все длинные циклы степени n в циклической записи. Ответ. Среди всех n циклических записей такого цикла ровно одна на- чинается с 1. Поэтому грубое решение состоит в том, чтобы выбрать те перестановки степени n, сокращенная запись которых начинается с 1 и ин- терпретировать их как запись цикла длины n. Для чуть более экономного решения можно записать все перестановки степени n − 1 и приаппендить к ним n. Либо, еще лучше, взять все перестановки 2, . . . , n и приписать к ним 1 слева: Map[Prepend[#,1]&,Permutations[Range[2,n]]] Вот, например, все длинные циклы степени 4 в циклической записи: (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2). 2.3. Напишите программу, осуществляющую переход от циклической за- писи длинного цикла к обычной. Решение. Перейти от циклической записи к полной записи совсем про- сто. Нужно лишь приписать к циклу x тот же цикл, сдвинутый на одну позицию влево {x,RotateLeft[x]}. Можно поступить и наоборот, а имен- но, предварить цикл тем же циклом, сдвинутым на одну позицию вправо, 443 {RotateRight[x],x}. Теперь обычная конструкция с Transpose и Sort поз- воляет найти сокращенную запись. 2.4. Напишите программу, генерирующую все длинные циклы степени n в сокращенной записи. Ответ. Нужно лишь скомбинировать результаты двух предыдущих задач посредством Map. Например, так long[n ]:=Map[Last[Transpose[ Sort[Transpose[ {#,RotateLeft[#]}]]]]&, Map[Prepend[#,1]&,Permutations[Range[2,n]]]] Вот, например, все длинные циклы степени 4 в сокращенной записи: (2 3 4 1) (2 4 1 3) (3 4 2 1) (3 1 4 2) (4 3 1 2) (4 1 2 3). 3. Каноническое разложение на циклы. 207 В соответствии с общим определением два цикла называются независи- мыми, если их носители дизъюнктны. Иными словами, циклы (i 1 , . . . , i l ) и (j 1 , . . . , j m ) независимы, если {i 1 , . . . , i l } ∩ {j 1 , . . . , j m } = ∅. Следующий результат, известный как разложение на независимые циклы, лежит в основе всей теории групп перестановок. Каждую переста- новку можно представить как произведение попарно независимых истин- ных циклов. Такое представление единственно с точностью до переста- новки сомножителей. Следующий способ позволяет сделать разложение на циклы единствен- ным. А именно, обозначим через π 1 цикл, содержащий наименьший эле- мент из Mob(π), через π 2 – цикл, содержащий наименьший элемент из Mob(π), который не попал в Mob(π 1 ), через π 3 — цикл, содержащий наи- меньший элемент из Mob(π), который не попал в Mob(π 1 ) ∪ Mob(π 2 ), и т. д. Полученное в результате разложение называется каноническим разло- жением π на циклы. Для того, чтобы единственным было не только само разложение на неза- висимые циклы, но и его запись, математики обычно начинают запись каж- дого цикла с наименьшего элемента. Например, при этом соглашении 1 2 3 4 5 6 7 8 9 3 5 1 8 9 4 7 6 2 = (13)(259)(486) При вычислениях вручную тривиальные циклы обычно опускаются, но при реализации эффективных компьютерных алгоритмов часто естествен- но явно выписывать и все тривиальные циклы и мы обычно так и будем поступать. Например, к приведенному выше разложению следовало бы дописать тривиальный цикл (7). 207 Это вам так показалось. Ведь я знаю, что они на рынке покупают. Купит вон тот каналья повар, что выучился у француза, кота, обдерет его, да и подает на стол вместо зайца. c Николай Гоголь, Мертвые души 444 Сейчас мы определим функции, восстанавливающие по перестановке ее каноническое разложение и по каноническому разложению исходную пере- становку в обычной записи. 3.1. Напишите программу, возвращающую по перестановке ее канониче- ское разложение на циклы. Решение 1 (функциональное программирование). Следующий текст является вариацией на тему определения команды ToCycles, определенной в пакетах SymmetricGroup и Combinatorica. Вот как вычисляется циклен- ный тип перестановки x степени n: toCycles[x ]:=Block[ {i},Fold[If[MemberQ[Flatten[#1],#2],#1, Append[#1,NestWhileList[x[[#]]&,i=#2,x[[#]]!=i&]]]&, {},Range[Length[x]]] Эта программа работает следующим образом. Два слота #1 и #2 заполня- ются соответственно • списком циклов, начиная с пустого списка циклов {}, • текущим номером i от 1 до n. Если индекс i использован в каком то из уже образованных циклов, про- грамма не меняет список циклов. В противном случае она начинает об- разовывать список, состоящий из образов i под действием перестановки x до тех пор, пока снова не получится i. В этот момент она прекращает вы- полнение команды NestWhileList и добавляет получившуюся орбиту i к списку циклов. Решение 2 (процедурное программирование). Для циклоидов при- ведем процедурную программу, решающую ту же задачу: toCycles[x ]:=Block[ {n=Length[x],list={},cycle,test,i,j}, test=Table[True, {n}]; For[i=1,i<=n,i++,If[test[[i]],For[j=i;cycle= {}, test[[j]],AppendTo[cycle,j];j=x[[j]], test[[j]]=False]; AppendTo[list,cycle]]];Return[list]] Здесь происходит следующее. Прежде всего, мы вводим шесть локальных переменных — степень n перестановки x, список циклов list, текущий цикл cycle, тест свежести индекса test, начало текущего цикла i и теку- щий индекс в текущем цикле j. Тест test[[j]] дает значение True, если индекс j свежий, иными словами, еще не учтен ни в перечисленных ранее циклах, ни в составе текущего цикла. В противном случае тест test[[j]] дает значение False, в этом случае j не может ни служить началом нового цикла, ни аппендиться к текущему циклу. Изначально ни один индекс не учтен, поэтому первое присваивание в теле блока говорит, что все индексы свежие. Далее, в первом цикле мы по порядку перебираем все индексы i от 1 до n и, если индекс i свежий, мы начинаем с него новый текущий цикл cycle= {}, текущий элемент которого обозначается j. До тех пор, пока 445 элемент j является свежим, мы добавляем его к циклу cycle, делаем его несвежим и присваиваем j следующее значение j=x[[j]]. В качестве примера приведем вычисленный при помощи этой функции канонические разложения перестановок степени 4. (1 2 3 4) = (1)(2)(3)(4) (1 2 4 3) = (1)(2)(3 4) (1 3 2 4) = (1)(2 3)(4) (1 3 4 2) = (1)(2 3 4) (1 4 2 3) = (1)(2 4 3) (1 4 3 2) = (1)(2 4)(3) (2 1 3 4) = (1 2)(3)(4) (2 1 4 3) = (1 2)(3 4) (2 3 1 4) = (1 2 3)(4) (2 3 4 1) = (1 2 3 4) (2 4 1 3) = (1 2 4 3) (2 4 3 1) = (1 2 4)(3) (3 1 2 4) = (1 3 2)(4) (3 1 4 2) = (1 3 4 2) (3 2 1 4) = (1 3)(2)(4) (3 2 4 1) = (1 3 4)(2) (3 4 1 2) = (1 3)(2 4) (3 4 2 1) = (1 3 2 4) (4 1 2 3) = (1 4 3 2) (4 1 3 2) = (1 4 2)(3) (4 2 1 3) = (1 4 3)(2) (4 2 3 1) = (1 4)(2)(3) (4 3 1 2) = (1 4 2 3) (4 3 2 1) = (1 4)(2 3) Обратите внимание, что запись (ijhk) в левой и в правой частях имеет совершенно разный смысл. Слева это приведенная запись перестановки, а справа — ее каноническое разложение на циклы. Иными словами, в левой части (1 2 3 4) обозначает тождественную перестановку, а в правой части (1 2 3 4) обозначает длинный цикл 1 7→ 2 7→ 3 7→ 4 7→ 1. 3.2. Напишите программу, возвращающую по каноническому разложению перестановки на циклы ее полную запись. Решение. Ну, это совсем просто, из предыдущего параграфа мы знаем, как превратить в полную запись один цикл, теперь мы должны просто сделать то же самое для всех циклов, входящих в цикленную запись z перестановки, а потом убрать лишний уровень вложенности: {Flatten[z],Flatten[Map[RotateLeft,z]]} или, что то же самое, {Flatten[Map[RotateRight,z]],Flatten[z]} 3.3. Напишите программу, возвращающую по каноническому разложению перестановки на циклы ее сокращенную запись. Ответ. Нужно просто совместить функцию, построенную в предыдущей задаче, с функцией перехода от полной записи к сокращенной. Например, так fromCycles[z]:=Last[Transpose[Sort[Transpose[ {Flatten[z],Flatten[Map[RotateLeft,z]]}]]]] Именно так, по существу, и устроена функция FromCycles, определенная в пакете Combinatorica. Сейчас мы предложим задачу, которая объясняет, почему программисты называют каноническим разложением перестановки на циклы реверсиро- ванное каноническое разложение. Рассмотрим отображение f сопоставля- ющее перестановке π перестановку, которая получается из нее следующим образом: мы записываем каноническое разложение π на циклы, а потом стираем все внутренние скобки в получившемся разложении и интерпре- тируем его как сокращенную запись перестановки f (π). Например, стирая 446 внутренние скобки в канонических разложениях (1)(2)(3), (12)(3), (1)(23) (123) мы каждый раз получим (123), а стирая внутренние скобки в (13)(2) и (132), мы получим перестановку (132), каноническое разложение которой равно (1)(23). 3.4. Изучите динамику функции f . Ответ. Можно, конечно, провести компьютерный эксперимент применив Flatten[toCycles[x]] ко всем перестановкам небольших степеней, но каж- дому и так ясно, что однократное применение функции f к любой переста- новке приводит к перестановке, для которой 1 является неподвижной точке. Тем самым, ее двухкратное применение приводит к перестановке, для ко- торой неподвижны 1 и 2, etc. Это значит, что не более чем за n −1 шагов от каждой перестановки мы дойдем до тождественной перестановки, которая является единственной неподвижной точкой функции f . 3.5. Докажите, что сушествует перестановка, от которой применением f нельзя дойти до тождественной перестановки меньше, чем за n − 1 шаг. Опишите все такие перестановки. Ответ. Имеется ровно (n − 1)! такая перестановка степени n, а именно, это все перестановки π такие, что π(1) = n. В самом деле, разложение та- кой перестановки на циклы начинается с (1n . . . ) и, значит, f (π) = (1n . . . ). Иными словами, разложение f (π) на циклы начинается с (1)(2n . . . ) и, зна- чит, f 2 (π) = (12n . . . ). При каждом дальнейшем применении f индекс n будет сдвигаться вправо на одну позицию. 4. Реверсированное каноническое разложение на циклы 208 Программисты обычно называют каноническим разложением переста- новки ее реверсированное каноническое разложение, т.е. разложение, получающееся записью циклов ее канонического разложения в обратном порядке. Кроме того, они, конечено, явно выписывают все тривиальные циклы. Вот, для примера, реверсированное каноническое разложение пе- рестановки, рассмотренной в предыдущем пункте: 1 2 3 4 5 6 7 8 9 3 5 1 8 9 4 7 6 2 = (7)(486)(259)(13). Таким образом, по прежнему каждый цикл начинается с наименьшего эле- мента, но теперь циклы расположены не в порядке возрастания, а в порядке убывания своих наименьших элементов. Ясно, что реверсированное кано- ническое разложение перестановки получается из ее канонического разло- жения применением функции Reverse. С другой стороны, поскольку вхо- дящие в реверсированное каноническое разложение циклы по прежнему независимы, исходная перестановка восстанавливается по нему при помо- щи той же самой функции fromCycles. 208 Never make anything simple and efficient when a way can be found to make it complex and wonderful. The Tao of Real Programming 447 Важным техническим преимуществом реверсированного канонического разложения является то, что — в отличие от обычного канонического раз- ложения! — в нем можно вообще не ставить внутренние скобки, так как их положение однозначно восстанавливается. А именно, если стереть в ревер- сированном каноническом разложении все внутренние скобки, то, чтобы вернуться к исходному разложению, достаточно вставить пару скобок )( перед каждым элементом, слева от которого нет ни одного меньшего эле- мента. Например, (8 5 9 2 6 4 3 1 7) может получиться только из разложения (8)(5 9)(2 6 4 3)(1 7). 4.1. Напишите программу, восстанавливающую внутренние скобки в ре- версированном циклическом разложении перестановки. Это типичный формальный экзерсис, относительно которого абсолютно все равно, как именно добиваться поставленной цели. Наоборот, в таких случаях на занятиях мы обычно поощряли студентов найти решение при помощи тех функций, с которыми они еще не встречались, или, наоборот, не используя тех функций, использование которых они уже хорошо понимают. Решение 1. Вот как, примерно, это делается в пакете Combinatorica. Прежде всего, составим список, состоящий из позиций тех элементов, слева от которых нет меньших элементов: nodes[x ]:=Module[ {m=Infinity},DeleteCases[ Table[If[x[[i]] Например, вычисление nodes[ {4,10,8,2,5,9,3,1,6,7}] вернет {1,4,8}. Осталось расставить скобки в исходном списке перед номерами, содержа- щимися в этом списке. Это можно сделать, например, при помощи коман- ды Take. Вначале мы добавляем n + 1 к списку узлов, потом разбиваем получившийся список номеров на подсписки длины 2 с отступом 1. Для приведенного выше примера при этом получится {{1,4},{4,8},{8,11}}. Каждый такой подсписок состоит из номера позиции, в которой начинает- ся текущий цикл, и номера позиции, в которой начинается следующий цикл — в том числе несуществующий цикл, начинающийся с n + 1. Наконец, мы выбираем в x фрагменты с соответствующим началом и концом: RevealCycles[x ]:=Map[Take[x, {First[#],Last[#]-1}]& Partition[Append[nodes[x],Length[x]+1],2,1]] Решение 2. Сейчас мы продемонстрируем несколько другое решение, ис- пользующее Split для той цели, для которой в первом решении применя- ется Take. Прежде всего, определим список, где на i-м месте стоит номер начала того цикла перестановки x, в который попадает i-й элемент. Эту функцию было бы естественно назвать runs, но, поскольку это имя уже занято, мы назовем ее corsa: corsa[x ]:=Module[ {m=Infinity,j=1}, Table[If[x[[i]] Для того примера, который рассмотрен в предыдущем решении, вычисле- ние corsa[ {4,10,8,2,5,9,3,1,6,7}] дает {1,1,1,4,4,4,4,8,8,8}. А те- перь проделаем обычный трюк с двойным транспонированием, который мы 448 уже много раз использовали с функцией Sort. Впрочем, имеются два отли- чия. Во-первых, Sort по умолчанию сортирует пары по первому элементу, а для Split нужно явно задать тест, определяющий эквивалентность на множестве пар, в данном случае совпадение элементов списка corsa[x] с соответствующими номерами. Во-вторых, после применения Sort мы полу- чали табличную запись самой перестановки, а после применения Split мы получим список, состоящий из табличных записей составляющих ее циклов и, значит, Last[Transpose[#]] нужно применять не к списку в целом, а к его элементам. Таким образом, мы получаем примерно следующий текст: revealCycles[x ]:=Map[Last[Transpose[#]]&, Split[Transpose[ {Range[10],x}], corsa[x][[First[#1]]]==corsa[x][[First[#2]]]&]] Рассмотрим теперь отображение f , сопоставляющее перестановке π пере- становку, которая получается из нее следующим образом: мы записываем реверсированное каноническое разложение π на циклы, а потом стираем все внутренние скобки в получившемся разложении и интерпретируем его как сокращенную запись перестановки f (π). Действие этого отображения значительно интереснее, чем действие аналогичного отображения, рассмат- ривавшегося в предыдущем параграфе. Если в предыдущем случае тожде- ственная перестановка была неподвижной точкой, то теперь тождественная перестановка (1, . . . , n) переходит в реверсию (n, . . . , 1). 4.2. Найдите все неподвижные точки отображения f . Ответ. При n ≥ 2 у этого отображения нет неподвижных точек. 4.3. Постарайтесь понять динамику отображения f . Ответ. Здесь без компьютерного эксперимента, использующего функцию Flatten[Reverse[toCycles[x]]] обойтись не удастся. Перестановки сте- пени 3 образуют одну орбиту под действием f : (1 2 3) (3 2 1) (2 1 3) (3 1 2) (1 3 2) (2 3 1) Перестановки степени 4 образуют две орбиты, при этом орбита тожде- ственной перестановки состоит из 15 элементов: (1 2 3 4) (4 3 2 1) (2 3 1 4) (4 1 2 3) (1 4 3 2) (3 2 4 1) (2 1 3 4) (4 3 1 2) (1 4 2 3) (2 4 3 1) (3 1 2 4) (4 1 3 2) (3 1 4 2) (1 3 4 2) (2 3 4 1) Вторая орбита состоит из 9 элементов: (1 2 4 3) (1 3 2 4) (2 1 4 3) (2 4 1 3) (3 2 1 4) (3 4 1 2) (3 4 2 1) (4 2 1 3) (4 2 3 1) Еще интересней картина для степени 5. Здесь тоже имеется две орбиты, одна из них трехэлементная: (2 1 3 5 4) (4 5 3 1 2) (3 2 5 1 4) 449 В то же время орбита тождественной перестановки состоит из остальных 117 перестановок степени 5. Дальше эта закономерность сохраняется: почти все перестановки данной степени попадают в орбиту тождественной перестановки, например, для степени 6 это 694 перестановки из 720, для степени 7 это 4804 перестановки из 5040. Остальные элементы образуют несколько совсем маленьких орбит. Скажем, для степени 6 порядки этих орбит равны 17, 5 и 4, соответственно. 5. Умножение циклов Чтобы разложение на циклы стало удобным интсрументом, нужно вы- разить все основные конструкции над перестановками в терминах циклов. Мы уже убедились, что обратная перестановка чрезвычайно естественно выражается в терминах циклов — и еще раз вернемся к этой теме в сле- дующем параграфе. А вот как в терминах циклов ищется произведение перестановок? 5.1. Задайте функцию, вычисляющую каноническое разложение на цик- лы двух перестановок, заданных своими каноническими разложениями на циклы. Ответ. Нет ничего проще, нужно просто перейти от цикленной записи к обычной, перемножить перестановки и снова вернуться к цикленной запи- си: cycleProduct[x ,y ]:=ToCycles[FromCycles[x][[FromCycles[y]]]] в общей алгебре это называется перенос структуры. Конечно, это совсем не то, что имелось в виду! Цикленная запись не только компактнее полной, но — при некотором навыке — удобнее для вычислений. Чтобы убедиться в этом, рассмотрим более общую задачу. Пусть σ = σ 1 . . . σ s — произвольное произведение циклов. Как вычислить обычную и/или цикленную запись σ? Разумеется, как и выше, мы можем просто превратить каждый из этих циклов в обычную запись перестановки степени n и перемножить все эти перестановки. 5.2. Задайте функцию, вычисляющую каноническое разложение на циклы перестановки, заданной как какое-то произведение циклов. Перестановку σ можно вычислить следующим образом. Чтобы опреде- лить образ i под действием σ, начнем с того, что найдем самый правый цикл, скажем, σ p , в запись которого входит фрагмент вида (. . . ij . . . ) либо (j . . . i), этот цикл переводит i в j. Если i не входит в запись ни одного из циклов σ p , то σ(i) = i. Найдем теперь самый правый цикл σ q левее σ p , в запись которого входит фрагмент вида (. . . jh . . . ) либо (h . . . j), этот цикл переводит j в h. Если j не входит в запись ни одного из циклов σ q , q < p, то σ(i) = j. В противном случае, продолжая действовать таким же образом, мы в конце концов найдем σ(i). Для иллюстрации этого алгоритма рассмотрим перестановку σ = (1753)(162)(46)(3574). 450 Вычислим, для примера, σ(7). Цикл (3574) переводит 7 в 4, цикл (46) пе- реводит 4 в 6, цикл (162) переводит 6 в 2, наконец, цикл (1753) оставляет 2 на месте. Поэтому σ(7) = 2. В действительности, вычисляя теперь об- раз σ(2), мы видим, что σ(2) = 7, так что в разложение σ на независимые циклы входит цикл (27). Прежде, чем переходить к следующему упражне- нию, мы предлагаем читателю довести это вычисление до конца и записать каноническое разложение σ на независимые циклы. 5.3. Напишите программу, реализующую описанный выше алгоритм умно- жения циклов. |