Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
5.4. Как изменится каноническое разложение перестановки на циклы при умножении на некоторую транспозицию? 6. Цикленный тип. Пусть π ∈ S n и n/π = {X 1 , . . . , X t }. Обозначим через n i = |X i | порядок орбиты X i . Цикленным типом пе- рестановки π ∈ S n называют набор [n 1 , . . . , n t ] порядков ее орбит. Обычно этот набор принято записывать как тупель (n 1 , . . . , n t ), располагая n i в порядке убывания. Обратите внимание, что говорят о цикленном или, изредка, цикловом, (но не циклическом!) типе. Впрочем, часто эпитет цикленном опускают и говорят просто о типе перестановки. Смысл введения цикленного типа состоит в том, что он полностью опи- сывает классы сопряженности в симметрической группе. Иными словами, две перестановки в S n тогда и только тогда сопряжены, когда их цикленные типы совпадают. Ясно, что n 1 + . . . + n t = n, так что с точки зрения комбинаторики (n 1 , . . . , n t ) определяет разбиение числа n. Порядок длин здесь безразли- чен, поэтому n i принято располагать не в том порядке, в котором они идут в каноническом разложении на циклы, а в порядке убывания. 6.1. Задайте функцию, сопоставляющую перестановке ее цикленный тип. Ответ. С учетом введенной в предыдущем параграфе функции toCycles это легче всего сделать так: cycleType[x ]:=Map[Length,toCycles[x]] 6.2. Вычислите все возможные цикленные типы перестановок степени ≤ 10. Количество всевозможных цикленных типов перестановок степени n рав- но количеству не??упорядоченных разбиений числа n на натуральные сла- гаемые и вычисляется внутренней функцией PartitionsP. 6.3. Перечислите все возможные типы перестановок на 5,6,7,8 и 9 симво- лах. 6.4. Докажите, что две перестановки в S n тогда и только тогда сопряжены, когда их цикленные типы совпадают. 451 Решение. Пусть вначале π, σ ∈ S n — две сопряженные перестановки, скажем, π = ρσρ −1 для некоторого ρ ∈ S n . Ясно, что если σ(i) = j, то πρ(i) = ρ(j). Тем самым, если X 1 , . . . , X t — орбиты σ, то ρ(X 1 ), . . . , ρ(X t ) — орбиты π, а так как ρ ∈ S n , то |ρ(X h ) | = |X h |, так что цикленные типы сопряженных перестановок совпадают. Обратно, предположим, что π = (i 11 . . . i 1l ) . . . (i t1 . . . i tm ), σ = (j 11 . . . j 1l ) . . . (j t1 . . . j tm ), две перестановки одинакового цикленного типа. Мы утверждаем, что π = ρσρ −1 , где ρ = i 11 . . . i 1l . . . i t1 . . . i tm j 11 . . . j 1l . . . j t1 . . . j tm . В самом деле, посмотрим, во что h-й элемент r-го цикла переходит под действием перестановки ρσρ −1 : i rh 7→ j rh 7→ j r,h+1 7→ i r,h+1 . Поскольку то же верно для всех элементов, перестановка ρσρ −1 совпадает с π. Но это и означает, что две перестановки одинакового цикленного типа сопряжены. 7. Количество перестановок степени n с m циклами. Мы уже знаем, что количество длинных циклов, которые можно образо- вать из n символов, равно (n − 1)! = h n 1 i . Это простейший частный случай следующего результата, который, собственно, и объясняет, в чем состоит комбинаторный смысл чисел Стирлинга первого рода. 7.1. Докажите, что количество перестановок n символов, в разложение которых входит ровно m циклов, равно h n m i Решение. Обозначим количество перестановок n символов, в разложение которых входит ровно m циклов, через x(n, m). Ясно, что x(0, 0) = 1, x(n, 0) = 0 для всех m ≥ 1 и x(n, m) = 0 для всех m > n. Поэтому для того, чтобы убедиться в том, что x(n, m) = h n m i , достаточно доказать, что x(n, m) удовлетворяет тому же рекуррентному соотношению, что и числа Стирлинга первого рода. В самом деле, рассмотрим перестановку π ∈ S n и сфокусируемся на символе n. Имеется следующая альтернатива: • n образует отдельную орбиту π. Убирая эту орбиту мы получаем пе- рестановку σ ∈ S n с m − 1 орбитой, так что количество таких перестановок равно x(n − 1, m − 1). • n входит в какой-то цикл длины ≥ 2. В этом случае вычеркивая в цикленной записи перестановки π символ n мы получим перестановку σ ∈ S n −1 , у которой по прежнему m орбит, причем каждая такая переста- новка получится из некоторой перестановки π ∈ S n с m орбитами. Обрат- но, рассмотрим произвольную перестановку σ ∈ S n −1 с m циклами длин l 1 , . . . , l m . Чтобы восстановить из нее перестановку π, мы должны врисо- вать символ n в какой-то цикл. Имеется ровно l + 1 способов врисовать n в 452 цикл (i 1 . . . i l ) длины l, но (ni 1 . . . i l ) = (i 1 . . . i l n) являются просто разными записями одного и того же цикла. Таким образом, среди этих l + 1 способов ровно l различных. Так как мы можем врисовать n в каждый из m циклов перестановки σ, это значит, что общее количество перестановок π, превра- щающихся в σ после вычеркивания n, равно l 1 +. . .+l m = n −1, и не зависит от σ. Таким образом, общий вклад этого случая равен (n − 1)x(n − 1, m) Суммируя полученные результаты, получаем x(n, m) = (n − 1)x(n − 1, m) + x(n − 1, m − 1), как и утверждалось. 7.2. Докажите, что n n m o ≤ h n m i Решение. Число Стирлинга второго рода n n m o совпадает с количеством всевозможных разбиений X = n на m орбит, и для каждого такого раз- биения имеется по крайней мере одна перестановка c данным разбиени- ем на орбиты. В случае, когда имеется хотя бы одна трехэлементная ор- бита, существует более одной такой перестановки. Поэтому как правило n n m o < h n m i Следующая задача легко решается от руки. 7.3. Перечислите все перестановки четырех символов, представимые в виде произведения двух циклов. Решение. Так как h 4 2 i = 11, то существует 11 таких перестановок, а именно (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), (4)(132), (12)(34), (13)(24), (14)(23). 7.4. Напишите программу, порождающую все перестановки степени n представимые как произведения m циклов. 8. Статистика циклов. В этом разделе мы вычислим, сколько циклов в среднем имеет переста- новка степени n. 8.1. Чему равно общее число циклов в канонических разложениях всех перестановок степени n? Ответ. Следующая функция дает общее количество циклов в перестанов- ках степени n: grandtotal[n ]:=Total[Map[Length[toCycles[#]]&,Permutations[n]] Вот несколько первых значений этой функции 1 2 3 4 5 6 7 8 9 10 1 3 11 50 274 1764 13068 109584 1026576 10628640 453 Секундное наблюдение наводит на мысль, что числа во второй строке пред- ставляют собой n!H n 8.2. Вычислите, сколько элементных циклов длины m содержат все пере- становки степени n и докажите полученный в предыдущей задаче резуль- тат. Решение. Прежде всего заметим, что каждый цикл длины m входит в (n − m)! перестановок, так как их действие на элементах, не входящих в цикл, может быть совершенно произвольным. Посчитаем теперь количе- ство возможных циклов длины m. В качестве первого элемента такого цик- ла может фигурировать любой из n элементов, в качестве второго — любой из оставшихся n − 1 элемента, в качестве третьего — любой из оставшихся n − 2 элементов и т.д. Наконец, в качестве последнего элемента может фи- гурировать любой из оставшихся n −m+1 элемента. Таким образом, общее количество записей циклов длины m равно [n] m , но при этом каждый цикл будет представлен m раз. Таким образом, количество возможных циклов равно [n] m /m и, значит, общее количество m-циклов во всех перестановках равно (n − m)![n] m /m = n!/m. Складывая получившиеся значения по всем m, мы как раз и получим n! 1 + 1 2 + 1 3 + . . . + 1 n = n!H n . 8.3. Сколько в среднем циклов имеет перестановка степени n? Решение. Естественно, H n , для этого нужно лишь разделить вычислен- ное в предыдущей задаче общее количество циклов во всех перестановках степени n на общее количество перестановок. Поставим теперь вопрос в другую сторону. 8.4. С какой вероятностью перестановка степени n имеет m циклов? Решение. Естественно, h n m i /n!, для этого нужно разделить вычисленное в предыдущем параграфе количество перестановко степени n с m циклами на общее количество перестановок. 8.5. Чему равна средняя длина цикла, входящего в перестановку степени n? Решение. Ответ на этот вопрос зависит от того, как конкретно опре- деляется средняя длина — что именно считается равновероятным? Если считать, что равновероятны сами циклы, то, естественно, n/H n , для этого нужно просто разделить степень перестановки на среднее количество цик- лов. Однако, если случайным образом выбирать символ от 1 до n, то с большей вероятностью он будет содержаться в более длинном цикле. 9. Наибольший порядок элемента S n Рассмотрим стандартную карточную колоду P = pack из 52 карт. Элементы симметрической группы S(P ) ∼ = S 52 принято называть тасов- ками = shuffles. Сколько раз нужно повторить фиксированную тасовку, 454 чтобы порядок карт совпал с первоначальным? Какое наибольшее число раз нам может при этом понадобиться стасовать колоду? В настоящем параграфе мы установим, что это число равно 180180, см., например, 209 С математической точки зрения речь здесь идет о нахождении наиболь- шего порядка перестановки π ∈ S n , который мы обозначим через G(n). Что можно сказать о функции n 7→ G(n)? Ясно, что для n = 2, 3, 4 наибольший порядок в группе S n имеет соответствующий длинный цикл. Но для n = 5 это уже не так, порядок длинного цикла равен 5, в то время принадлежа- щий S 5 элемент цикленного типа (3, 2) имеет порядок 3 · 2 = 6. Еще более замечательные явления происходят для n = 6, в этом случае как длинный цикл, так и элемент цикленного типа (3, 2, 1) имеют порядок 6. В то же время, как мы установили в предыдущем параграфе, они не сопряжены в S 6 . Однако, сюрпризы здесь не кончаются! 9.1. Найдите количество 6-циклов и количество перестановок цикленного типа (3, 2, 1) в S 6 Решение. Как мы знаем, количество 6-циклов в группе S 6 равно 5! = 120. Количество же элементов типа (3, 2, 1) там равно 2! 6 3 3 2 = 120. Тем самым, порядки обоих классов элементов максимального порядка в S 6 рав- ны. В действительности, у группы S 6 существует внешний автоморфизм, переставляющий эти два класса. С этим явлением связано исключительное поведение групп S 5 и S 6 , которое накладывает отпечаток на всю теорию симметрических групп. Как уже было сказано, в случае n ≤ 4 наибольший порядок в S n имеет длинный цикл, так что G(n) = n. Однако, начиная с n = 5 жизнь ста- новится веселее. Следующий экзерсис проделывал каждый, кто начинал изучать теорию групп. 9.2. Вычислите G(n) при n ≤ 11. Ответ. Ограничимся ответом. В рубрике cycle type указаны цикленные типы элементов наибольшего порядка: n: 5 6 7 8 9 10 11 G(n): 6 6 12 15 20 30 30 cycle type: (3, 2) (3, 2, 1) или (6) (4, 3) (5, 3) (5, 4) (5, 3, 2) (5, 3, 2, 1) или (6, 5) Вот еще несколько значений, которые легко вычисляются от руки: n: 12 13 14 15 16 17 18 G(n): 60 60 84 105 140 210 210 cycle type: (5, 4, 3) (5, 4, 3, 1) (7, 4, 3) (7, 5, 3) (7, 5, 4) (7, 5, 3, 2) (7, 5, 3, 2, 1) или (7, 6, 5) 209 M.B.Nathanson, On the greatest order of an element of the symmetric group. — Amer. Math. Monthly, 1972, vol.79, p.500–501. 455 Уильям Миллер 210 обрывает свою таблицу в этом месте. Сейчас мы вычис- лим еще несколько значений G(n), так как начиная с n = 19 они становится интереснее в нескольких отношениях. Как вычислять эти значения? Пусть π — перестановка цикленного типа (m 1 , . . . , m s ). Ее порядок m = lcm(m 1 , . . . , m 2 ) является наименьшим об- щим кратным длин циклов. Сейчас мы убедимся в том, что единственный интересный случай с точки зрения максимизации порядка — это случай примарных m 1 , . . . , m s . Следующие соображения приводятся на страни- цах 500–501 работы Миллера. 9.3. Пусть m = lcm(m 1 , . . . , m s ) — наименьшее общее кратное натураль- ных чисел m 1 , . . . , m s ∈ N, а m = p 1 l 1 . . . p s l s — его каноническое разложе- ние на простые. Докажите, что тогда spread(m) = p 1 l 1 + . . . + p s l s ≤ m 1 + . . . + m s . Решение. По уровню и типу это образцовая задача районной олимпиа- ды для 6-го класса, поэтому ограничимся следующим комментарием. До- статочно показать, что если m 1 , . . . , m s не являются степенями попар- но различных простых, то существует другая последовательность нату- ральных чисел (n 1 , . . . , n t ) такая, что m = lcm(n 1 , . . . , n t ), но при этом n 1 + . . . + n t < m 1 + . . . + m s 9.4. В группе S n тогда и только тогда существует элемент порядка m, когда spread(m) ≤ n. 9.5. Если в группе S n существует элемент порядка m, то в ней существует элемент порядка m, все длины нетривиальных циклов которого являются степенями попарно различных простых. В частности, это относится к элементам наибольшего порядка. Тем са- мым мы получаем следующую характеризацию G(n), при помощи которой на компьютере легко вычислить первые несколько десятков значений этой функции. 9.6. Имеет место равенство G(n) = max(m), где максимум берется по всем m ≤ n! таким, что spread(m) ≤ n. 9.7. Напишите программу, вычисляющую G(n) и вычислите первые несколько десятков значений этой функции. Решение. Вот следующие пять значений c указанием какого-то класса наибольшего порядка: n: 19 20 21 22 23 G(n): 420 420 420 420 840 cycle type: (7, 5, 4, 3) (7, 5, 4, 3, 1) (7, 5, 4, 3, 1, 1) (7, 5, 4, 3, 1, 1, 1) (8, 7, 5, 3) 210 W.Miller, The maximum order of an element of a finite symmetric group. — Amer. Math. Monthly, 1987, June–July, p.497–506. 456 Сразу бросаются в глаза два обстоятельства. Во-первых, появляется длин- ная серия G(19) = G(20) = G(21) = G(22) = 420 когда G(n) не растет. Во-вторых, начиная с n = 21 известный нам контрпример, связанный с су- ществованием двух классов сопряженности элементов максимального по- рядка, перестает быть единственным. Например, ясно, что элемент цик- ленного типа (7, 5, 4, 3, 2) имеет тот же порядок, что элемент цикленного типа (7, 5, 4, 3, 1, 1) — кстати, это служит контрпримером к заявлению на странице 501 упомянутой выше статьи Миллера. Приведем еще несколько значений G(n), уже без указания соответству- ющих элементов: G(24) = 840, G(25) = G(26) = 1260, G(27) = 1540, G(28) = 2310, G(29) = 2520, G(30) = G(31) = 4620, G(32) = G(33) = 5460, G(34) = G(35) = 9240, G(36) = G(37) = 13860, G(38) = G(39) = 16380 Ну и, как уже отмечалось в самом начале раздела, G(52) = 180180. Хотя вычисление этого значения в дуболомном стиле, используя разложение на простые множители всех чисел до нескольких миллионов, займет несколько минут машинного времени. Итак, вычисление G(n) сводится к теоретико-числовой задаче. Одна- ко, получение явной формулы для G(n) представляется довольно сомни- тельным предприятием. Лучшее, на что мы можем надеяться, — это асимптотические оценки. Первый нетривиальный результат в этом направ- лении был получен Эдмундом Ландау 211,212 А именно, он доказал, что ln(G(n)) ∼ p n ln(n)). Первоначальное доказательство Ландау в полном объеме использовало теорему о распределении простых. 10. Участки подъема. В первом параграфе настоящей главы мы уже определили число Эйлера D n m E как количество перестановок (x 1 . . . x n ) степени n с m участками подъема, т.е. таких, для которых существует ровно m индексов i таких, что x i < x i+1 . Композиция с реверсией (n n − 1 . . . 2 1) показывает, что мы могли бы определять числа Эйлера в терминах участков спуска x i > x i+1 Рассмотрим теперь восходящие серии, состоящие из последователь- ных участков подъема, ограниченных двумя участками спуска и/или кон- цами перестановки: x h −1 > x h < x h+1 < . . . < x k −1 < x k > x k+1 . Ясно, что количество восходящих серий на 1 больше, чем количество участ- ков спуска. Точно так же количество нисходящих серий x h −1 < x h > x h+1 > . . . < x k −1 > x k < x k+1 211 E.Landau, ¨ Uber die Maximalordnung der Permutation gegebenen Grades. — Archiv der Math. u. Phys., Ser.3, 1903, Bd.5, S.92–103. 212 E.Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd. I, 2nd ed., Chelsea, N.Y., 1953, S.222–229. 457 на 1 больше, чем количество участков подъема. Поэтому мы могли бы определять числа Эйлера в терминах восходящих или нисходящих серий. 10.1. Напишите программу, которая разбивает перестановку на восходя- щие серии. Решение. Вот как эта функция определяется в пакете Combinatorica: runs[x ]:=Map[Take[x, {First[#]+1,Last[#]}]&, Partition[Join[ {0},Select[Range[Length[x]-1], x[[#]]>x[[#+1]]&], {Length[x]}],2,1]] 10.2. Напишите программу, которая ищет в перестановке самую длинную восходящую серию. 10.3. Напишите программу, которая разбивает перестановку на нисходя- щие серии. При нашей новой интерпретации легко получить комбинаторные дока- зательства основных соотношений для чисел Эйлера. 10.4. Докажите рекуррентное соотношение для чисел Эйлера. Согласно нашей новой интерпретации число Эйлера D n m E представляет собой количество перестановок степени n с m + 1 восходящей серией. Как может получиться такая перестановка из перестановок степени n − 1? Рас- смотрим произвольную перестановку степени n − 1 и будем врисовывать n во все возможные места. • Если исходная перестановка содержала m + 1 серию, то врисовывание n в конец серии не меняет количество серий. Таким образом, имеется ров- но m + 1 способ получить из перестановки степени n − 1 с m + 1 серией перестановку степени n с m + 1 серией. • С другой стороны, врисовывание n в любое другое место увеличивает количество серий на 1. Таким образом, второй способ получить переста- новку с m + 1 состоит в том, чтобы взять перестановку степени n − 1 с m сериями и врисовать n в любую позицию, кроме концов уже имеющихся серий. Это и есть искомое рекуррентное соотношение. Gauls! We have nothing to fear; except perhaps that the sky may fall on our heads tomorrow. But as we all know, tomorrow never comes!! Adventures of Asterix 458 Глава 9. МНОГОЧЛЕНЫ И МАТРИЦЫ Математика слишком обширна и овладеть ею всей невозможно. Теорфизикой же можно овладеть всей. Лев Ландау Если нет обмана, это уже не теорфизика, а математика. Александр Ахиезер Человек, не знающий и не желающий знать основных законов на- уки, в мирное время вреден, а в военное — опасен. Аркадий Мигдал Sometimes attaining the deepest familiarity with a question is our best substitute for actually having the answer. Brian Greene, The Elegant Universe It is most important to have a beautiful theorem. And if the proofs don't support it, don't be too distressed, but wait a bit and see if some error in the proofs doesn't show up. Paul Dirac A mathematician's life would be a happy one if he had only to discover and never to write proofs. Daniel Gorenstein Just because something happens to be true, it does not follow that it should be taken for granted. |