Xreferat.com » Рефераты по математике » Связь комбинаторики с различными разделами математики

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

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

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

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

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

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

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

Выполнила:

студентка 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 показан наиболее общий метод пересчёта (известный ещё в XVIII веке), а также приведены примеры его использования в теории чисел.

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

α0= β0° γ0= ε, α1= β1° γ0, …, αs-1= βs-1° γ0,

αs= β0° γ1, αs+1= β1° γ1, …, α2s-1= βs-1° γ1, (*)

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

α(l-1)s= β0° γl-1, α(l-1)s+1= β1° γl-1, …, αls-1= βs-1° γl-1

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

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

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

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

t(G)=Связь комбинаторики с различными разделами математикиλ(α), где αСвязь комбинаторики с различными разделами математикиG.

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

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

Error: Reference source not found

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

λ(α0) + λ(α1) + … +λ(αk-1)= Связь комбинаторики с различными разделами математикиλ(α), где αСвязь комбинаторики с различными разделами математикиG.

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

Однако, если элементы i, j Связь комбинаторики с различными разделами математикиM содержатся в одной орбите, то О(i)=O(j), и поэтому |Gi|=|G|:|O(i)|=|G|:|O(j)|=|Gj|. Пусть О1, О2, …, Оt – все орбиты группы G такие, что Связь комбинаторики с различными разделами математики, и слагаемые в этом объединении не пересекаются. Разобьём Связь комбинаторики с различными разделами математики|Gm | (где mСвязь комбинаторики с различными разделами математикиM) на части так, чтобы внутри каждой из этих частей суммирование шло по элементам некоторой орбиты:

Связь комбинаторики с различными разделами математикиm| =Связь комбинаторики с различными разделами математикиm| + Связь комбинаторики с различными разделами математикиm| + … +Связь комбинаторики с различными разделами математикиm|.

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

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

Поэтому Связь комбинаторики с различными разделами математикиm| = |G| + … +|G| = t∙|G|.

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

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

то есть t = t(G) = Связь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математики.

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


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

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

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

Решение. (В остальных задачах будем использовать обозначения, аналогичные обозначениям в этой задаче). Поскольку каждую из восьми вершин куба можно раскрасить тремя способами, причём независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить 38=6561 различными способами (по формуле Связь комбинаторики с различными разделами математики). Однако при таком подходе к решению задачи молчаливо предполагается, что мы умеем различать вершины куба перед окраской, то есть, скажем, куб жёстко закреплён или его вершины занумерованы. При этом полученный ответ можно интерпретировать следующим образом: можно так раскрасить 38 абсолютно одинаковых, жёстко закреплённых кубов, что все они будут различаться. Для 38+1 кубов этого сделать уже нельзя. Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жёстко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис.2).

Связь комбинаторики с различными разделами математикиЕстественно считать, что два куба раскрашены одинаково, если их раскраски совпадают вплоть до способа размещения кубов в пространстве, то есть вплоть до некоторого вращения одного из кубов. Будем говорить, что такие раскраски кубов геометрически неотличимы. Поэтому естественным уточнением задачи о раскраске является следующая задача: сколькими геометрически различными способами можно раскрасить вершины куба в три цвета.

Переформулируем теперь эту задачу так, чтобы стала понятной её связь с леммой Бернсайда. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано (|M|=38), G – группа всех вращений куба. Группа G естественным образом определяет группу перестановок на множестве М. Именно, если αСвязь комбинаторики с различными разделами математикиG – некоторое вращение, то каждому кубу из М можно сопоставить некоторый другой куб, который получается из первого при вращении α. Это соответствие является перестановкой на М, которую будем обозначать Связь комбинаторики с различными разделами математики. Группу всех таких перестановок множества М, определяемых перестановками из G будем обозначать Связь комбинаторики с различными разделами математики. Ясно, что |Связь комбинаторики с различными разделами математики| = |G|. То, что два куба К1 и К2 из М раскрашены геометрически одинаково, означает, что один из них можно перевести вращением в такое положение, в котором они неразличимы. Иными словами, существует такая перестановка Связь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математики, что Связь комбинаторики с различными разделами математики(К1) = К2, то есть К1 и К2 содержатся в одной орбите группы Связь комбинаторики с различными разделами математики, действующей на множестве М. Таким образом, для того чтобы определить число геометрически различимых способов раскраски вершин куба, нужно найти количество орбит группы Связь комбинаторики с различными разделами математики на множестве М. Считая вершины кубов занумерованными числами 1, 2, 3, 4, 5, 6, 7, 8, раскраску каждого из 38 кубов можно однозначно охарактеризовать «словом» из восьми букв, каждая из которых есть либо к, либо с, либо з. То, что i-тая буква слова равна к (или с, или з) означает, что i-тая вершина при выбранной нумерации окрашена в красный цвет (или в синий, или в зелёный соответственно). Перестановки из группы Связь комбинаторики с различными разделами математики переставляют последовательности букв к, с, з. Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из Связь комбинаторики с различными разделами математики. Последовательность букв к, с, з будет неподвижной для перестановки Связь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математики тогда и только тогда, когда при разложении соответствующей перестановки αСвязь комбинаторики с различными разделами математикиG в произведение циклов вершины куба, номера которых входят в один и тот же цикл, окрашены одним цветом. Если перестановка αСвязь комбинаторики с различными разделами математикиG разложена в произведение k циклов, то число её неподвижных точек равно 3k, где Связь комбинаторики с различными разделами математики, так как вершины куба, номера которых входят в один цикл, можно раскрасить тремя способами. Опишем разложения в произведение циклов для всех перестановок из группы G вращений куба.

а) Вокруг каждой из трёх осей, соединяющих центры противоположных граней, имеется три вращения на углы Связь комбинаторики с различными разделами математики, Связь комбинаторики с различными разделами математики, Связь комбинаторики с различными разделами математики. Им соответствуют перестановки:

1) (1, 5, 8, 4) (2, 6, 7, 3)

2) (1, 8) (2, 7) (3, 6) (4, 5)

3) (1, 4, 8, 5) (2, 3, 7, 6)

4) (1, 4, 3, 2) (5, 8, 7, 6)

5) (1, 3) (2, 4) (5, 7) (6, 8)

6) (1, 2, 3, 4) (5, 6, 7, 8)

7) (1, 5, 6, 2) (3, 4, 8, 7)

8) (1, 6) (2, 5) (3, 8) (4, 7)

9) (1, 2, 6, 5) (3, 7, 8, 4)

б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:

10) (1) (2, 5, 4) (3, 6, 8) (7)

11) (2) (1, 3, 6) (4, 7, 5) (8)

12) (3) (1, 6, 8) (2, 7, 4) (5)

13) (4) (1, 3, 8) (2, 7, 5) (6)

14) (1) (2, 4, 5) (3, 8, 6) (7)

15) (2) (1, 6, 3) (4, 5, 7) (8)

16) (3) (1, 8, 6) (2, 4, 7) (5)

17) (4) (1, 8, 3) (2, 5, 7) (6)

в) Вокруг каждой из шести осей, соединяющих середины противоположных рёбер куба, имеется одно вращение. Им соответствуют перестановки:

18) (1, 5) (2, 8) (3, 7) (4, 6)

19) (1, 2) (3, 5) (4, 6) (7, 8)

20) (1, 7) (2, 3) (4, 6) (5, 8)

21) (1, 7) (2, 6) (3, 5) (4, 8)

22) (1, 7) (2, 8) (3, 4) (5, 6)

23) (1, 4) (2, 8) (3, 5) (6, 7)

Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6)(7)(8) получаем 24 перестановки – все элементы группы G. Итак, в группе G вращений куба имеется:

1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,

6 перестановок типа <4, 4>,

9 перестановок типа <2, 2, 2, 2>,

8 перестановок типа <1, 1, 3, 3>.

Тогда перестановка первого типа имеет 38 неподвижных точек, любая из перестановок второго типа – 32, третьего и четвёртого типов – 34 неподвижных точек (по формуле Связь комбинаторики с различными разделами математикиnk = nk). Поэтому согласно лемме Бернсайда, имеем Связь комбинаторики с различными разделами математики(38 + 6∙32 + 9∙34 + 8∙34) = 333.

Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.

Задача 2. Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов – красного и синего?

Решение. Переформулируем эту задачу следующим равносильным образом: сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета? Пусть М – множество всевозможных по-разному раскрашенных правильных семиугольников одного размера, положение которых в пространстве фиксировано. Тогда имеется 27 = 128 различных вариантов раскраски вершин семиугольника, так как каждую вершину независимо от других можно раскрасить двумя способами. Здесь два

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: