Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет

Математический факультет

Кафедра алгебры и геометрии

Выпускная квалификационная работа

Связь комбинаторики с различными разделами математики

Выполнила:

студентка V курса математического факультета

Бородулина Юлия Анатольевна

Научный руководитель:

к. ф-м. н., доцент кафедры алгебры и геометрии

Е.М. Ковязина

Рецензент:

к. ф-м. н., доцент кафедры алгебры и геометрии

О.С. Руденко

Допущена к защите в государственной аттестационной комиссии

«___» __________2005 г. Зав. кафедрой Е.М. Вечтомов

«___»___________2005 г. Декан факультета В.И. Варанкина

Киров

2005

Содержание

Введение 3

§1. Применение леммы Бернсайда к решению комбинаторных задач 5

1.1. Орбиты группы перестановок 5

1.2. Длина орбиты группы перестановок. Лемма Бернсайда 5

1.3. Комбинаторные задачи 8

§2. «Метод просеивания» 21

2.1. Формула включения и исключения 21

2.2. Общий «метод просеивания» или «пропускания через решето». Решето Сильва-Сильвестра 23

2.3. Использование общего метода решета в теории чисел 23

§3. Разбиение фигур на части меньшего диаметра 28

§4. «Счастливые билеты» 34

Библиографический список 39

Введение

Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов называется комбинаторикой. Комбинаторика возникла в XVI веке. Вопросы, касающиеся азартных игр, явились движущей силой в развитии комбинаторики. Сейчас комбинаторные методы применяются как в самой математике, так и вне её – теория кодирования, планирование эксперимента, топология, конечная алгебра, математическая логика, теория игр, кристаллография, биология, статистическая физика, экономика и т.д.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования.

Цель дипломной работы: показать связь комбинаторики с различными разделами математики.

Задачи:

1. Изучить лемму Бернсайда и решить комбинаторные задачи о раскраске с её применением;

2. Показать применение метода «просеивания» для подсчёта количества простых и взаимно простых чисел;

3. Рассмотреть теорему Борсука, которая решает задачу для плоских фигур о разбиении их на части меньшего диаметра;

4. Решить задачу о «счастливых билетах».

Дипломная работа состоит из четырёх частей:

В § 1 рассмотрена связь теории групп с комбинаторикой: применение группы перестановок к решению комбинаторных задач. Основной используемый факт в этом параграфе – лемма Бернсайда.

В § 2 показан наиболее общий метод пересчёта (известный ещё в XVIII веке), а также приведены примеры его использования в теории чисел.

Параграф 3 посвящён вопросу комбинаторной геометрии – вопросу о разбиении фигуры на несколько меньших частей. Рассмотренная теорема Борсука является тем стержнем, вокруг которого возможно дальнейшее рассмотрение этого вопроса.

В § 4 решается известная задача о счастливых билетах с привлечением методов из математического анализа.

§ 1. Применение леммы Бернсайда к решению комбинаторных задач [3]

1.1. Орбиты группы перестановок

Пусть G – группа перестановок на множестве М={1, 2, …, n}. Подмножество О М называется орбитой группы G, если: а) α(a) O для любого α G и любого a O, то есть действие перестановок из G на элементы О не выводит за пределы О; б) любые два элемента из О можно перевести друг в друга некоторой перестановкой из G.

Легко показать, что всякая группа перестановок G={ε=α₀, α₁, …, α_k-1} имеет орбиты.

Орбитами подобного вида исчерпываются все типы орбит, то есть, если О – орбита группы G и а О, то О=О(а).

Любые две орбиты О(а) и О(b) либо совпадают (если b O(a)), либо не пересекаются (если b O(a)).

Таким образом, множество М распадается в объединение непересекающихся подмножеств – орбит группы G. В связи с разбиением множества М на орбиты группы перестановок G возникают следующие два вопроса:

1) Сколько орбит имеет группа G на множестве М?

2) Какова длина каждой из этих орбит, то есть из скольких элементов они состоят?

Ответим на эти вопросы.

1.2. Длина орбиты группы перестановок. Лемма Бернсайда

Ответим на второй вопрос. Для любого элемента а М можно рассмотреть группу G_a всех перестановок из G, для которых точка а является неподвижной. Она называется стабилизатором точки а. Ответим на вопрос, доказав следующую теорему:

Длина орбиты О(а) равна индексу стабилизатора G_a в группе G, то есть |O(a)|= | G |:| G_a |.

Доказательство. Пусть G={ε=α₀, α₁, …, α_k-1}, G_a={ε=β₀, β₁, …, β_s-1}. Для подсчёта различных элементов в последовательности a=α₀(a), α₁(a), …, α_k-1(a) удобно особым образом расположить в ряд элементы группы G. Для этого используем тот факт, что группу G можно представить в виде объединения всевозможных непересекающихся правых классов смежности по подгруппе G_a, имеющих одинаковое число элементов. То есть существуют перестановки γ₀=ε, γ₁, …, γ_l-1 из группы G такие, что все перестановки ряда

α₀₌ β₀° γ₀= ε, α₁= β₁° γ₀, …, α_s-1= β_s-1° γ₀,

α_s= β₀° γ₁, α_s+1= β₁° γ₁, …, α_2s-1= β_s-1° γ₁, (*)

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

α_(l-1)s= β₀° γ_l-1, α_(l-1)s+1= β₁° γ_l-1, …, α_ls-1= β_s-1° γ_l-1

попарно различны и исчерпывают всю группу G.

Для любого i=0, …, l-1 применение s перестановок α_is, α_is+1, …, α_(i+1)s-1, образующих i-тую строку таблицы (*), к элементу а даёт один и тот же элемент γ_i(а) (так как β₀, β₁, …, β_s-1 оставляют а неподвижным). Все l элементов γ_i(а) попарно различны. Действительно, если бы γ_i(а)=γ_j(а) для некоторых i, j, то а=(γ_j ° γ_i^-1) (a), то есть перестановка (γ_j ° γ_i^-1) G_a. Но это возможно только тогда, когда γ_i и γ_j содержатся в одном правом классе смежности группы G по подгруппе G_a, чего быть не может. Таким образом, длина орбиты О(а) равна l, то есть числу строк в таблице (*): k=l∙s (то есть l является индексом подгруппы в группе). По теореме Лагранжа l=| G |:| G_a |, то есть |O(a)|= | G |:| G_a |. Теорема доказана.

Теперь ответим на первый вопрос. Для этого сформулируем и докажем лемму Бернсайда.

Пусть λ(α) – число неподвижных точек перестановки α, t(G) – число орбит группы перестановок G={ε=α₀, α₁, …, α_k-1}, действующей на множестве М={1, 2, …, n}. Тогда для любой группы перестановок имеет место равенство:

t(G)= λ(α), где α G.

Доказательство. Рассмотрим отношение «перестановка α сохраняет неподвижным элемент m » между перестановками группы G и элементами множества М. Сопоставим парам (α, m), α G, m M, вершины прямоугольной сети и отметим те из них, для которых соответствующая пара (α, m) находится в указанном отношении, то есть α(m)=m (рис. 1).

Ины ми словами, построим график указанного отношения.

Error: Reference source not found

Число отмеченных точек (точек, принадлежащих графику) можно подсчитать двумя способами: определить число отмеченных точек на каждой вертикали и просуммировать полученные величины или же определить число таких точек на каждой горизонтали и вычислить их сумму. Согласно определению отношения на каждой вертикали отмечаются все точки, сохраняемые перестановкой α, соответствующей этой вертикали. Их число равно λ(α). Поэтому число всех точек графика равно

λ(α₀) + λ(α₁) + … +λ(α_k-1)= λ(α), где α G.

С другой стороны, на каждой горизонтали отмечаются все перестановки, сохраняющие элемент m M, отвечающий этой горизонтали. А такие перестановки образуют группу G_m – стабилизатор элемента m, - и их число, по теореме, доказанной ранее, равно |G_m|=|G|:|O(m)|. Поэтому при втором способе подсчёта числа отмеченных точек графика рассматриваемого отношения получаем выражение |G₁| + |G₂| + … + |G_n| = |G_m |(m M).

Однако, если элементы i, j M содержатся в одной орбите, то О(i)=O(j), и поэтому |G_i|=|G|:|O(i)|=|G|:|O(j)|=|G_j|. Пусть О₁, О₂, …, О_t – все орбиты группы G такие, что , и слагаемые в этом объединении не пересекаются. Разобьём |G_m | (где m M) на части так, чтобы внутри каждой из этих частей суммирование шло по элементам некоторой орбиты:

_m| = _m| + _m| + … + _m|.

Каждое из t слагаемых в правой части этого равенства можно преобразовать следующим образом:

_m| = = = = |G|.

Поэтому _m| = |G| + … +|G| = t∙|G|.

Таким образом, при втором способе подсчёта мы получили t∙|G| отмеченных точек графика. Приравнивая величины, полученные при первом и втором способах, получим

t|G| = ,

то есть t = t(G) = .

Лемма доказана.

1.3. Комбинаторные задачи

Рассмотрим несколько примеров, иллюстрирующих возможности применения леммы Бернсайда при решении комбинаторных задач на перечисление.

Задача 1. Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зелёный)?