Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 17
Текст из файла (страница 17)
6) (2, 5) (3, 8) (4, 7), (1, 2, б, 5) (3, 7, 8, 4). 6) Вокрчг каждой из четырех диагоналей, т. е. осей, соединяющих противоположные вершины куба, имеется по два нетривиальных вращения. Им соответствуют перестановки (1) (2, 5, 4) (3, 6, 8) (7), (2) (1, 3, 6) .(4, 7, 5) (8), (3) (1, 6, 8) (2, 7, 4) (5), (4) ° (1, 3, 8) *(2, 7, 5) ° (6), (1) (2, 4, 5) (3, 8, 6) (7), (2) (1, 6, 3) (4, 5, 7) (8), (3) ° (1, 8, 6) ° (2, 4, 7) ° (5), (4) ° (1, 8, 3) ° (2, 5, 7) ° (6).
в) Вокруг каждой из шести осей, соединяющих середины противоположных ребер, имеется одно нетривиальное вращение. Им соответствуют перестановки (1, 5) (2, 8) (3, 7) (4, 6), (1, 2) (3, 5) (4, 6) (7, 8), (1, 7) (2, 3) ° (4, 6) (5, 8), (1, 7) (2, 6) (3, 5) ° (4, 8), (1, 7) (2, 8) (3, 4) (5, 6), (1, 4) (2, 8) (3, 5) (6, 7). 69 Вместе с тождественной получаем 24 перестановки.
Итак, в группе 6 вращений куба имеется 1 перестановка типа (1, 1, 1, 1, 1, 1, 1, 1), 6 перестановок типа (4, 4), 9 перестановок типа (2, 2, 2, 2), 8 перестановок типа (1, 1, 3, 3). Перестановка первого типа имеет 3' неподвижных точек, любая из перестановок второго типа — 3', третьего и ч твертого типов — 34 неподвижных точек. Поэтому согласно лемме Бернсайда имеем 1(6) = — (3'+6.3'+9 3" +8 3') =333. Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета ровно 333. 2. Составление ожерелий. Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов— красного и синего? Для того чтобы стала понятной аналогия этой задачи с предыдущей, переформулируем ее следующим равносильным образом: Сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета? Здесь два способа раскраски неотличимы, если один нз них можно получить из другого, применяя к семиугольнику либо преобразования вращения, либо симметрии относительно осей, т.
е. перестановки из группы диэдра Р,. Если ' вершины семиугольника пронумерованы, имеется 2' = 128 различных вариантов их раскраски, так как каждую вершину независимо от других можно раскрасить двумя способами. Снова будем описывать раскраски словами длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). На множестве Ж всех таких слов действует группа О, перестановок, задаваемых перестановками из О,. Например, если и= =(1, 2, 3, 4, 5, 6, 7), то перестановка й последнюю букву каждого слова переставляет в его начало, а остальные буквы не изменяет.
Для того чтобы определить число орбит группы О, на множестве У, несбходимо найти типы перестановок из О,. Эта задача гораздо проще аналогичного вопроса для группы 6 из примера 1. Группа О, состоит нз 14 перестановок множества (1, 2, 3, 4, 5, 6, 7), 90 которые распределены по возможным типам так: 1 перестановка .имеет тип (1, 1, 1, 1, 1, 1, 1), 6 перестановок имеют тип (7), 7 перестановок имеют тип (1, 2, 2, 2). Слово неподвижно относительно перестановки а ее 7)„ тогда и только тогда, когда буквы, стоягцие на местах с номерами из одного цикла в перестановке се, совпадают. Поэтому тождественная перестановка имеет 2' неподвижных точек на Л?, перестановки второго типа — по 2, а перестановки третьего типа — по 2'. Применяя лемму Берн- сайда, получаем 1(4)т) 14(2'+6 2+7 2')=!8.
Итак, из бусин двух цветов мохсно составигпе 18 семибусенных ожерелий. Упражнения 1. Грани куба можно раскрасить: а) все в белый цвет; б) все в черный цвет; в) часть в белый, а остальные в черный. Сколько ° имеется разных способов раскраски? 2. Сколько различных ожерелий можно составить нз двух синих, двух белых и двух красных бусин? 3.
Сколькими геометрически различными способами три абсолютно одинаковые мухи могут усесться в вершинах правильного пятиугольника? 4. Снольно существует различных ориентированных графов с тремя вершинами? б. Сколько существует различных неориентированных графов с четырьмя вершинамн? 6. Сколькими способами можно раскрасить вершины куба в два цвета тан, чтобы вершин каждого цвета было поровну? 7. Сколькими различными способамн можно грани куба раскрасить в четыре цвета? 6 14. ДЕИСТВИЕ ПЕРЕСТАНОВКИ НА МНОГОЧЛЕН Напомним, что многочлен — это сумма каких-то одно- членов.
Если все одночлены многочлена 7 образованы нз символов х,, х,, ..., х„, то будем обозначать такой много- член 7(хт, х„..., х,) и говорить, что это многочлен с л переменными. Например, ~(хм хз) =х1ха+2хгхз+бхь — многочлен с двумя переменными, а и(хь хз, х,) =2х,'хзх3+5хзхз+бхз — многочлен с тремя переменными. Пусть ! (хь х„..., х,) — некоторый многочлен с и переменными, М=(1, 2, ..., и) — множество индексов при переменных. Для произвольной перестановки а ен Я„определим Действие а на многочлен 1(хз, хз,..., х„), положив (! (хь х„..., х„))з=~'(хь хм ..., х,) = з (хы>з х<зпп ° -., х(л)з)- 4 Пример 1.
а) Если !(хь х„хз, хз)=х„х,хзх*,+ +х,'х,хзхз+х,+хз+1, а 12 3 1 4)' то ~'(хь хз, х„х,) =хзхзх,хз+х хзхзхз+хз+хз+1 б) Для многочлена й(хь хз, хз, хз) = х)хзхзхз+хзхзхзхз+хзхзхзхз и перестановки а из предыдущего примера имеем Л (хь х„хз, хз)=хзхзхзхз+хзх,*х,хз+хзхзх,'хз= =д(хь х„х„хз). 3 Из этого примера видно, что многочлеи ~з(х„х„... ..., х„) может отличаться от Г(хь х„..., х„), а может и совпадать с ним. Если ~з(хз, х„..., х„) =~(хь х„..., х„), то говорят, что миогочлен 1 ие изменяется под действием перестановки а, или, иначе, инвприантен относительно действия а.
Понятно, что каждый многочлен от и переменных инвариантен относительно действия тождественной перестановки: 1з(хз, хз ..., х„) =~(хь хз, ..., х,). Поскольку операция умножения двух перестановок означает их последовательное выполнение, то для любых пеРестановок а, т и пРоизвольного миогочлена1(хь хз, ... ..., х„) имеем (() (хь хз, ..., х„))з)з=)з'(хь хз, ..., хз). Отсюда вытекает, что когда многочлен Г(хз, х„..., х„) не изменяется под действием перестановок а н т, то он будет инвариаытеи и относительно их произведения.
Кроме того, каждый многочлен 1(х„ х„ ..., х„), инвариантный 92 относительно перестановки о, будет инвариантным и относительно перестановки а-'. Поэтому множество всех перестановок, которые не меняют заданный многочлен 1(х„х„..., х„), образует группу. Эта группа называется группой инерции многочлена Цх„х„..., х„). 4 Пример 2. Найдем группу инерции многочлена А (х>, хз, хз) = (х> хз) (хэ — хз) (хз — хз). Имеем А> с '> (хь х„х,) = (х, — х,) (х, — х,) (х, — х,) = — А (хь х>ь хз), А<з э> (хь хэ, хз) = (х> — хз) (х> — хз) (хэ — хз) = — А (хь хь хз), АП '> (Хь Хь Хз) = (Хэ — Хз) (Хз — Х>) (Хз — Х>) = — А (Хь Хь Хз)1 Аш ' '> (хь хэ, хз) = (х, — х,)(хэ — х,) (х, — х,) = А (хь х„ х,), А>Ь ' '> (Хь Хь Хз) =- (Хз — Х>) (Хэ — Хэ) (Х> — Хз) = А (Хь Хэ, Хз).
Следовательно, группой инерции многочлена А (х>, хэ, х,) является множество (е,(1, 2, 3), (1, 3, 2)). Ь Из этого примера видно, что многочлен А (хь х„х,) меняв>п знак под действием любой транспозиции. Этот результат обобщается на многочлены такого вида с ббльшим числом переменных. Многочлен А (х>, хэ, хз) является произведением разностей х> — хт длЯ 1(1, >,1=1, 2, 3; поэтомУ многочлен такого вида с п переменными будет такой: А (ХЬ Х„..., Хл) = (Х» — Хз) (Х> — Хэ) (Х» — КЭ)...
(Х> — Хл) Х х (х, — х,) (х, — хэ)... (хэ — х„) >с >~ (хз — хэ)... (х, — хл) Х >с(х, > — х„). Он содержит (и — 1)+(и — 2)+...+1 =п(п — 1)/2 сомножителей. Пусть (>, 1), > ( > — произвольная транспозиция. Она действует лишь на те сомножители х» — хь й(1, в которых по меньшей мере один из индексов й, 1совпадает с 1 или 1. Под действием транспозиции (>, 1) знак сомножителя х> — хт меняется на противоположный: '(х; — хт)>' » = хт — х> = — (х; — хт). Для других сомножителей, которые изменяются под действием транспозиции (1, /), имеем а) если 1, 1(й, то х> — х„пеРеходит в хт — х» и наоборот, не меняя знака; б) если >, у ) й, то х„ — х; переходит в х» — ху и наоборот, не меняя знака; 93 в) если ( =й(1, то х; — хх переходит в х~ — ха= = — (х,— хт), а х„— х, переходит в ха — х;= — (х; — хх), т е.
произведение (х; — хх)(х„— х,) под действием ((, )) не изменяет знака. Следовательно, произведение всех сомножителей много- члена А (хг, х,, ..., х„), кроме х; — хм под действием ((, )) не изменяет знака, а сомножитель х; †изменяет знак на противоположный. Поэтому произведение всех сомножителей — многочлен А (х,, х„..., х„) — также изменяет знак: Ась П(хь хм ..., х„) = — А (хп хм ..., х„). Поскольку каждую перестановку можно разложить в произведение транспозиций, то под действием любой перестановки многочлен А(х,, х„..., х„) может лишь изменить знак.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
