Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 18
Текст из файла (страница 18)
Именно поэтому этот многочлен называется знаколеременным многочленом с л переменными. Пусть г(х„х„..., х„) — некоторый многочлен. Действуя на него всевозможными перестановками из Я„, получим, вообще говоря, какой-то набор разных многочленов: 1,(х,, х„..., х„), ~,(х„х„..., х„), ..., (,(хь х„..., х„). Сам многочлен ~(хм х„..., х„) в этом ряду обязательно встретится, так как Г' =- ). Многочлен )1(хь хэ ° ° » хл)+~2(хь хм..., х»»)+.' +~»(хм хм ...» Х»») будем называть орбитальным для ~(хь х,, ..., х„).
Орбитальный многочлен, как легко понять, инвариантен относительно любой перестановки из Я„. 4 Пример 3, а) Для одночлена х~ орбитальным многочленом с л переменными будет многочлен аэ=х,"+х~+...+х~. Такие многочлены называЮтся степенными суммами от л переменных. В частности, степенными суммами с двумя переменными будут многочлены з,=х,+х„' э»=х1+х,', а,=х,'+х',.
б) Для одночлена х,'х,'ха орбитальным многочленом с тремя переменными будет многочлен х1х~хе + х1хэхз + х)х»ха + хгх»х» + х1х~х~+ х1х»х». $» Орбитальный многочлен с л переменными для одночлена х,"х,"...х,' будем обозначать о„(х',»х',*...х',»), 94 Например, о, (х,х ) = х,х,'+ х,'х„ Оз (хгхз) =ктхзз+ хтхз+хзхз+х)хз+хтхз+хзхз Легко убедиться, что для любого а многочлен о„(х,'х,') выражается через степенные суммы. Проверим это для случая а=3. И!леем вза, — (хз+ кз+ х')(х'+х'+х ) — х'+'+ х"+ '+х'+1+ Следовательно, о, (кзх,') = в„в, — 3„,. Интересным является вопрос о нахождении количества слагаемых в орбитальных многочленах.
Понятно, что количество одночленов в многочленах о„(Х1зх',з...х', ) не может превышать а! Максимальное количество одночленов будем иметь только тогда, когда все переменные будут входить в одночлен с разными степенями, а если показатели переменных в одночлене будут повторяться, то оно будет меньше. Упражнении 1.
Пусть о I! 2 3 4! (2 ! 3 4)' 1, а / — один нз многочленов; а) хгхзхзх)а+ 2х(хьтзхз+ Зхзх)~ б) х(хзхьтз+ х', + хз) в) х", + х)+ хз+ хз. Найти )". 2. Найти группу инерпин многочлена ) (хг, хз, хз, хз) =х,хзх)аз+ 2х(хзх)хз+бхз+зхз+ 1. 3. Из какого числа перестановок состоит группа инерции много- члена А (хн хз хз. хз)7 4. Длв произвольной группы перестановок существует многочлен, длв которого зта группа является группой инерции. Доказать вто.
5. Сколько одиочлепов содеРжит многочлен оз(хзхзх)хз). Зависаешь этот многочлен. а. Доказать, что многочлен о„(хзх'] выражается через степенные суммы длв любого и. 7. Сколько одночленов содерзкит многочлен вида о„ (х,хз ... х1) длн разных и, !7 й 15. ЧЕТНЫЕ И НЕЧЕТНЫЕ ПЕРЕСТАНОВКИ. ЗНАКОПЕРЕМЕННАЯ ГРУППА Разложение перестановок из 5„в произведение транс- позиций, вообще говоря, не однозначно, например: (1, 2, 3) = (1, 3) (2, 3) = (1, 2) (1, 3).
95 Все-таки определенную характеристику, которая остается одинаковой для каждого из таких разложений, указать можно. Такой характеристикой является четность числа сомножителей в разложении. Точнее, справедлива такая важная Теорема. Если и„сс, ... а, и ~1~ рч ....()~ — разложения перестановки в произведение транспозиций, то числа в и 1 имеют одинаковую четкость.
Доказательство. Пусть ф — некоторая перестановка на множестве М=(1, 2, ..., и), сс,.а, ... и„ р1 ()х" "()~ — разложения ф в произведение транспозиций. Подействуем перестановкой ф на знакопеременный много- член А(х„х,, ..., х„). Как было установлено в предыдущем параграфе, А и Ач могут отличаться лишь знаком, причем если а транспозиция, то А"= — А. Рассмотрим две последовательности многочленов: А, А" =Рь Р""=Р, ..., Р °,=Р, А, Аэ'=бь бв'=бм ..., Ф =б В каждой из них два соседних выражения отличаются лишь знаком.
А поэтому Р, = ( — 1)'А, бс = ( — 1)'А. С другой стороны, Р, =б,= Ач. Следовательно, ( — 1)'А =( — 1)'А, т. е. в и 1 — числа одинаковой четности. Теперь можно дать такое определение. Перестановка называется четной, если она раскладывается в произведение четного числа транспозиций. В противном случае перестановка называется нечетной.
Таким образом, четными будут те и только те перестановки, которые оставляют без изменения знакопеременный многочлен А (х„ х„...., х„). Обозначим через А„ множество четных перестановок из Вт а через „— множество всех нечетных. По доказанной теореме каждая перестановка ф еи Я„принадлежит одному из этих множеств, причем А, и В„не имеют общих элементов. Покажем, что множества А и В„состоят из одинакового количества перестановок, т.
е. (А„(=) В„(. (1) Для этого построим взаимно однозначное отображение 1х множества А„на множество ' В„. Зафиксируем некоторую транспозицию и. и поставим.в Еоответствие каждому эб элементу в ен А„ перестановку в *а.' Ч': в-~в а. Перестановки в и в.а — разной четности, т, е, в ась В„ и отображение Ч' определено правильно. Убедимся в том, что отображение Чг биективно. Если (), у еи А„ и б чь у, то и б аФ у а, потому что равенство (1 а=у а можно было сократить на а и получить, вос преки условию, что б = у. Для каждой перестановки реп В„существует перестановка уев А„, а именно у =р а-'=() а, такая, что (у)Ч'=б.
Следовательно, отображение Чг является одновременно и инъекцией, и сюръекц ней Отсюда вытекает спра. ведливость равенства (1). Каждая транспозиция — нечетная перестановка. Равенство (2) $ 7 показывает, что цикл нечетной длины — перестановка четная, Четной будет также тождественная перестановка е. Понятно, что произведение четных Перестановок — перестановка четная, произведение двух нечетных перестановок — также четная, а произведение четной на нечетную (или наоборот) — нечетная. Если перестановка ф разложена в произведение транс-.
позиций Ф ф=бг ° 6, ... б 16„ то обратной к ф будет перестановка "р-'=6, 6„, 6,.6ь так как из равенства (бг.бз 6-1" "6,) (б '6,' ~ ....6,'.6,')=и вытекает, что ф-'=6,' ° 6,' ~ °... 6,' 6,', а для транспозиций 6~'=бь Отсюда получаем, что множество А„образует подгруппу группы Я„. Эта подгруппа называется знакоперелеллой группой перестановок. Она играет очень важную роль в теории групп перестановок и в ее применениях.
Заметим, что четность перестановки можно определить, не раскладывая ее в произведение транспозиций. Достаточно лишь разложить перестановку в произведение циклов и подсчитать количество циклов четной длины. Если найденное число будет четным, то перестановка четная, в противном случае — нечетная (см.
упражнение 11), 97 Упражнении 1. Какую карактериую особенношь имеет граф четнэй пере> етановки? 2. Какой наивысший порядок могут иметь элементы группы А>? 8. Составить таблицу умножения группы А>. 4. Какая иэ описанных нами в 4 8 подгрупп 8» будет знако. переменной? 6. Найти центр группы А„ (см. упражнение 4 э 9). 6. Донаэать, что А„ †максимальн подгруппа 8ю отличная от 8„, т. е. кажйая подгруппа, которая содержит А„, совпадает или о А„, или с 8„. ' 7. Доказать, что каждую четную перестановку можно разложить в произведение циклов длины трн, 8. Можно ли разложить каждую четную перестановку зз 8», где и нечетно, в произведение циклов (1> 2, 3), (1, 4, 5), ..., (1, и — 1, и)? 9.
Говорят, что пара чисел 1, ) образует ивверсию, если >)/, Доказать, что перестановка (1> (з (з - )») будет четной тогда и только тогда, когда количество инверсий, обре. воваиных элементами>ее второго ряда, †чис четное. 1В. Сколько имеется перестановок из 8ю, в которых алементы второго ряда образуют ровно 6 инверсий? !1. Пусть (йь йз, ..., й ) †т перестановки >р еэ 8„, Разность и†> называется декрементом втой перестановки. Доказать, что четиость перестановки совпадает о четностью ее декремента, й 16. СИММЕТРИЧЕСКИЕ И ЧЕТНОСИММЕТРИЧЕСКИЕ МНОГОЧЛЕНЫ Многочлен 1 (хь хь "., х„) называетсЯ симметРическим, если он является инвариантным относительно действия любой перестановки из 8„, т.
е. группой инерции гпакого многочлена япляется еся симметрическая группа 8,. Например, симметрическими будут такие многочлены с и переменными: от(хт> хз> ° °, х„) =ха+хе+...+х», оз (хт, хз, "°, х») =хтхз+х>хз+ ° ° +х»-тх», оа (хь хь ° ° °, х») =хххааа+х>хьта+ ° ° ° +х»-зх»-тх», о» (хт> хз> ° . ° > х») =хтхэ ° ° ° х». Действительно, орбитальный многочлен любого одночлена — симметрический, а а1(х1> хг> ° > хл) =о» (х1), ае (хт, хе, ° ° °, х») = =о„(х,х,), ..., а„(хм хм ..., х„) =о„(х,х, ... х„).
Многочлены а,, а„..., а„называются элементарными симметрическими многочленоми. Запишем их полностью для о=2, и =3: а,(хь хг)=х1+хм а,(хм хм хв)=х1+х»+хм а,(х,, «,) =х,х„а,(х„хм хг) =х,х,+х,х,+х,хг, аг (хн х„хг) =х,хьха. Непосредственно видно, что а) сумма симметрических многочленов — ' симметрический многочлен; б) произведение симметрических многочленов — симметрический многочлен. Поэтому если в произвольный многочлен у(уь ум ..., у„) с и переменными подставить вместо уь ум ..., у, элементарные симметрические многочлены а„а„..., а„, то получим некоторый многочлен от хм хм ..., х„, который будет симметрическим.
Например, если у(уь у,) =у',у,+бу,+2, то д (а„а,) = (х1+ хг)'х1хг+ бх,х, + 2 = х,'хе+ 2х>хг>+ х,х3+ бх>х, + 2 — симметрический многочлен. Оказывается, что так можно получить каждый симметрический многочлен. Т е о р е м а. Каждый симметрический многочлен является многочленом от элементарных симметрических многочленов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
