Применение теории групп в комбинаторике : учеб. пособие / А. Н. Щетинин. <...> ISBN 978-5-7038-3657-6 В пособии доказана лемма Бернсайда и приведена без доказательства теорема Пойа о производящей функции запаса классов эквивалентности раскрашиваний. <...> Введены основные алгебраические понятия, начиная с множеств, отображений и бинарных отношений и заканчивая действием группы на множестве. <...> Пособие содержит многочисленные примеры, а также варианты домашнего задания по вычислению количества способов раскрашивания вершин, ребер и граней многогранников. <...> Теория групп — наука очень абстрактная, и уследить за всеми тонкостями неискушенному человеку сложно. <...> Это означает, что множество M состоит из всех элементов x, обладающих свойством P. <...> Наконец, f : X →Y биективно, когда оно одновременно сюръективно и инъективно. <...> Преобразование, заданное формулой idX(x)=x для всех x ∈X, называют тождественным. <...> Отображения f :X →X называют преобразованиями мнов множество Y называют правило, сопоставляющее каждому элементу x ∈X элемент f(x) ∈ Y . <...> Ясно, что для любого f :X →Y имеем f ◦ idX =f, отображения. <...> Из биективности отображения f : X →Y Пусть, далее, f : X →Y,h: Y →Z — биективные отображения. <...> Множество называют конечным, если существует его биективное отображение на одно из множеств Jn ={1, 2, .,n}. <...> Число элементов конечного множества M обозначают через |M|. <...> Рассмотрим множество RM всех отображений f :M →R. <...> Таким образом, множество RM находится в биективном соответствии с множеством целочисленных наборов (y1, y2, ., ym), где yi =f(i) и yi принимает одно из значений 1, 2, ., q. <...> Рассмотрим множество Sn всех биективных преобразований множества Jn (n=1, 2, .) <...> Так как подстановки являются преобразованиями одного множества, их можно перемножать. <...> Такая подстановка называется циклом (длины l) и обозначается (i1 i2 . il). <...> Эта подстановка разложена в произведение независимых (т. е. не содержащих одинаковых элементов) циклов. <...> Каждая подстановка σ = e в Sn является произведением независимых циклов длины 2 <...>
Применение_теории_групп_в_комбинаторике.pdf
УДК 519.8(075.8)
ББК 22.141
Щ70
Рецензенты: Ю.В. Селиванов, В.И. Алехнович
Щ70
Щетинин А. Н.
Применение теории групп в комбинаторике : учеб. пособие
/ А. Н. Щетинин. — М.: Изд-во МГТУ им. Н. Э. Баумана,
2013. — 23, [5] с. : ил.
ISBN 978-5-7038-3657-6
В пособии доказана лемма Бернсайда и приведена без доказательства
теорема Пойа о производящей функции запаса
классов эквивалентности раскрашиваний. Изложение не предполагает
никаких предварительных сведений и доступно студентам
первого курса. Введены основные алгебраические понятия,
начиная с множеств, отображений и бинарных отношений
и заканчивая действием группы на множестве. Пособие содержит
многочисленные примеры, а также варианты домашнего
задания по вычислению количества способов раскрашивания
вершин, ребер и граней многогранников.
Для студентов младших курсов МГТУ им. Н. Э. Баумана,
изучающих алгебру и дискретную математику.
Учебное издание
Применение теории групп
в комбинаторике
Редактор С.А. Серебрякова
Корректор М.А. Василевская
Компьютерная верстка А.Н. Щетинин
Подписано в печать 26.04.2013. Формат 60×84/16.
Усл. печ. л. 1,63. Тираж 500 экз. Изд. № 20.
Заказ
Издательство МГТУ им. Н. Э. Баумана.
Типография МГТУ им. Н. Э. Баумана.
105005, Москва, 2-я Бауманская ул., д. 5, стр. 1.
ISBN-978-5-7038-3657-6
- МГТУ им. Н. Э. Баумана, 2013
c
УДК 519.8(075.8)
ББК 22.141
Щетинин Александр Николаевич
Стр.2
ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1. Множества и отображения . . . . . . . . . . . . . . . . . . . 3
2. Понятие группы . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Теорема Лагранжа . . . . . . . . . . . . . . . . . . . . . . . 14
4. Группы движений . . . . . . . . . . . . . . . . . . . . . . . . 15
5. Действие группы на множестве . . . . . . . . . . . . . . . . 17
6. Лемма Бернсайда . . . . . . . . . . . . . . . . . . . . . . . 19
7. Теорема Пойа . . . . . . . . . . . . . . . . . . . . . . . . 21
Домашнее задание . . . . . . . . . . . . . . . . . . . . . . . . 25
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Стр.27