Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Дії групи на множині




Означення 5. Нехай - група з нейтральним елементом , а -множина. Будемо говорити, Що діє на , якщо задана операція (образ пари позначається просто ), якщо виконуються такі умови:

1.

2.

Означення 6. Нехай - множина. Множина всіх бієктивних функції з операцією композиції називається симетричною групою на множині і позначається .

Помітимо, що будь-який гомоморфізм задає дію групи на множині за правилом . Навпаки, якщо задано на множині , то можна задати гомоморфізм формулою . Таким чином можна вважати, що дія групи на множині – це гомоморфізм , що і висувається в якості означення дії групи на множині в деякій літературі.

Уведемо тепер деякі поняття пов’язані з дією групи на множині , які використовуються у формулюванні й доведенні леми Бернсайда.

Означення 7. Орбітою елементу під дією називається множина . Кількістю елементів в даній орбіті називається довжина орбіти (в різних орбітах може бути різна кількість елементів).

Будь-які дві орбіти або не перетинаються, або співпадають. Таким чином множина розбивається на диз’юнктивне об’єднання орбіт.

Означення 8. Нерухомими точками елемента називають такі для яких . Множину нерухомих точок елемента позначимо .

Означення 9. Множина елементів групи , що залишають на місці даний елемент називається стабілізатором елемента і позначається через Іншими словами, . Очевидно, що стабілізатор є підгрупою в .

Зауваження 6. Зверніть увагу на те, що кількість пар , для яких можна обчислити двома способами, які вказані в різних частинах наступної рівності:

Остання рівність, не дивлячись на свою очевидність, грає дуже важливу роль при доведенні леми Бернсайда. Інша важлива думка показана в наступній лемі.

Лема1. Довжина орбіти елемента рівна індексу стабілізатора цього елементу. Тому, якщо група - скінченна, то

Доведення.

Індекс підгрупи – це кількість лівих суміжних класів даної підгрупи. Нехай позначає множину лівих суміжних класів. Задамо функцію формулою (очевидно, що права частина не залежить від вибору представника суміжного класу) доведемо, що бієктивна. Сюр’єктивність одразу слідує з означення орбіти. Припустимо, що , тобто . Таким чином бієктивна функція, що відображає на а це можливо лише при умові якщо .

Теорема 5. Для довільного елемента y з орбіти Y групи A справджується така рівність

Доведення.

Подамо групу A об’єднанням правих класів суміжності ajA(y) за підгрупою Позначимо кількість таких класів суміжності через m. Для кожного класу суміжності поставимо у відповідність елемент з орбіти .

1. При різних і різними також є і , бо інакше добуток належить до групи , а тому належить до . Останнє висловлювання суперечить відсутності спільних елементів множин та , тобто розбиттю на класи суміжності. Отже, вказане відображення є відображенням «в» (ін’єкцією).

2. Згідно з означенням орбiти, для довільного елемента орбіти існує елемент групи , при якому . У свою чергу, згідно з розбиттям на праві класи суміжності існують та елемент групи , при яких . В результаті маємо .

Отже, вказане відображення є відображенням «на» (сюр’єкцією). Інакше кажучи, кожний елемент орбіти є образом деякого класу суміжності. Таким чином, доведено існування взаємно однозначного відображення з множини класів суміжності в обіту , тому вони мають однакову кількість елементів. Теорему доведено.

6. Лема Бернсайда (Коші-Фробеніуса)

Існують декілька варіантів леми: звичайний, спрощений, ваговий і т.д. Запишемо формулювання леми Бернсайда, використовуючи зазначений вище теоретичний матеріал.

Теорема 6. (спрощений вигляд)

Кількість орбіт групи підстановок дорівнює середньому арифметичному кількості нерухомих точок групи :

, де - кількість вузлів (циклів довжиною 1) в перестановці .

Доведення.

Позначимо через різні орбіти групи A. Для кожного виберемо довільним чином елемент з . Додавши праві та ліві частини рівностей у твердженні попередньої теореми, записаних для для кожного j =1, 2,..., m, отримаємо таку рівність:

Вже встановлено, що для елементів з однієї орбіти їхні стабілізатори спряжені, а тому мають однакову кількість елементів. Праву частину останньої рівності можна подати таким чином:

 

Теорема 7. (звичайний вигляд)

Кількість орбіт дії групи на множині рівна:

Доведення.

Позначимо число орбіт через . Кожний елемент лежить в орбіті . Співставимо йому число . Сума цих чисел по всім з даної орбіти очевидно рівна 1. (ми раз складаємо число з самим собою). Тому кількість орбіт можна обчислити за формулою . Підставивши сюди формулу для довжини орбіти, отримаємо . Використовуючи формулу із зауваження1, отримаємо , що й потрібно було довести.

Теорема 8. (ваговий вигляд)

де - вага орбіти (вага будь-якого його представника), - вага елемента.

Перш ніж розв’язати «задачу про намиста» нам потрібно сформулювати та довести теорему Рефілдера-Пойа, на основі якої ґрунтується розв’язання. В свою чергу доведення цієї теореми ґрунтується на основі леми Бернсайда.




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 1312; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.024 сек.