Применение теории групп в комбинаторике

Московский государственный технический университет
имени Н.Э. Баумана
А.Н. Щетинин
Применение теории групп
в комбинаторике
Рекомендовано Научно-методическим советом
МГТУ им. Н.Э. Баумана
в качестве учебного пособия
Москва
Издательство МГТУ им. Н.Э. Баумана
2013

УДК 519.8(075.8)
ББК 22.141
Щ70
Рецензенты: Ю.В. Селиванов, В.И. Алехнович
Щ70
Щетинин А. Н.
Применение теории групп в комбинаторике : учеб. пособие / А. Н. Щетинин. — М.: Изд-во МГТУ им. Н. Э. Баумана, 2013. — 23, [5] с. : ил.
ISBN 978-5-7038-3657-6
В пособии доказана лемма Бернсайда и приведена без доказательства теорема Пойа о производящей функции запаса
классов эквивалентности раскрашиваний. Изложение не предполагает никаких предварительных сведений и доступно студентам первого курса. Введены основные алгебраические понятия, начиная с множеств, отображений и бинарных отношений
и заканчивая действием группы на множестве. Пособие содержит многочисленные примеры, а также варианты домашнего
задания по вычислению количества способов раскрашивания
вершин, ребер и граней многогранников.
Для студентов младших курсов МГТУ им. Н. Э. Баумана,
изучающих алгебру и дискретную математику.
УДК 519.8(075.8)
ББК 22.141
Учебное издание
Щетинин Александр Николаевич
Применение теории групп
в комбинаторике
Редактор С.А. Серебрякова
Корректор
М.А. Василевская
Компьютерная верстка А.Н. Щетинин
Подписано в печать 26.04.2013. Формат 60×84/16.
Усл. печ. л. 1,63. Тираж 500 экз. Изд. №20.
Заказ
Издательство МГТУ им. Н. Э. Баумана.
Типография МГТУ им. Н. Э. Баумана.
105005, Москва, 2-я Бауманская ул., д. 5, стр. 1.
ISBN-978-5-7038-3657-6
c
⃝МГТУ им. Н. Э. Баумана, 2013

ПРЕДИСЛОВИЕ
Не вызывает сомнения, что знакомство с основами алгебры, в частности с теорией групп, необходимо каждому квалифицированному специалисту в области прикладной математики. Теория групп — наука очень абстрактная, и уследить за
всеми тонкостями неискушенному человеку сложно. Нашей целью было продемонстрировать пользу этой науки, приведя ее
конкретные применения к задачам комбинаторики, имеющим
практическое значение. Сформулированная в пособии теорема
Пойа (G. Polya) отличается как математической красотой, так
и полезными приложениями.
1. МНОЖЕСТВА И ОТОБРАЖЕНИЯ
Множества. Под множеством понимают любую совокупность объектов, называемых элементами множества. Запись
x ∈X означает, что элемент x принадлежит множеству X.
Множества с конечным числом
различных элементов могут
быть описаны путем перечисления их элементов. Например,
J5 = {1, 2, 3, 4, 5} — множество первых пяти натуральных чисел. Мы будем также использовать запись
M = {x | P(x)}.
Это означает, что множество M состоит из всех элементов x,
обладающих свойством P.
Используем стандартное обозначение Z для множества всех
целых чисел.
Напомним, что X есть подмножество множества Y , X ⊆Y ,
если любой элемент X принадлежит Y . Пустое множество ∅
3