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

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




Не нашли то, что вам нужно?
Посмотрите вашу тему в базе готовых дипломных и курсовых работ:

(Результаты откроются в новом окне)

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


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

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

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

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

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

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

Выполнила:

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

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

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

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

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

Рецензент:

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

О. С. Руденко

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

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

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

Киров

2005

Заказать написание дипломной - rosdiplomnaya.com

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

Содержание

Введение........................................................................................................... 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={ε=α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=ls (то есть 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).

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

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

λ(α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 различных вариантов раскраски вершин семиугольника, так как каждую вершину независимо от других можно раскрасить двумя способами. Здесь два способа раскраски неотличимы, если один из них можно получить из другого, применяя к семиугольнику либо преобразования вращения, либо симметрии относительно осей. Будем описывать раскраски «словами» длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). Проделаем те же действия, что и в задаче 1 для применения леммы Бернсайда. Опишем разложения в произведение циклов для всех перестановок из группы G.

а) Тождественному преобразованию соответствует перестановка:

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

б) Поворотам на углы Рисунок убран из работы и доступен только в оригинальном файле. соответствуют перестановки:

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

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

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

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

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

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

в) Симметриям относительно осей, соединяющих вершины семиугольника с серединами противоположных сторон, соответствуют перестановки:

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

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

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

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

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

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

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

где 1, 2, 3, 4, 5, 6, 7 – числа, с помощью которых занумерованы вершины семиугольника.

Итак, в группе G имеется:

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

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

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

Слово неподвижно относительно перестановки Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле. тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке α, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на М, перестановки второго типа – по 2, а перестановки третьего типа – по 24. Применяя лемму Бернсайда, получаем

(27 + 6∙2 + 7∙24) = 18.

Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.

Задача 3. Грани куба можно раскрасить: а) все в белый цвет; б) все в чёрный цвет; в) часть в белый, а остальные в чёрный. Сколько имеется разных способов раскраски?

Решение. Рисунок убран из работы и доступен только в оригинальном файле.

Грань (1' 4' 5' 8') – 1

Грань (2' 3' 6' 7') – 2

Грань (3' 4' 7' 8') – 3

Грань (1' 2' 5' 6') – 4

Грань (1' 2' 3' 4') – 5

Грань (5' 6' 7' 8') – 6

Рис. 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому тождественная перестановка имеет 26 неподвижных точек на М, перестановки второго и пятого типов имеют по 23 неподвижных точек на М, перестановки третьего типа – по 24, а перестановки четвёртого типа – по 22. Тогда по лемме Бернсайда получаем Рисунок убран из работы и доступен только в оригинальном файле.(26 + 6∙23+ 3∙24+ 8∙22 + 6∙23) = 10.

Итак, число геометрически различных способов раскраски граней куба в два цвета равно 10.

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

Решение. Переформулируем задачу так: сколькими геометрически различными способами можно раскрасить вершины правильного шестиугольника так, чтобы две были синего цвета, две – белого, две – красного? а) Вокруг центра шестиугольника имеется пять поворотов на углы Рисунок убран из работы и доступен только в оригинальном файле.. Им соответствуют перестановки:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определим количество неподвижных точек для перестановок каждого типа. Так как количество различных цветов, в которые нужно раскрасить шестиугольник, равно трём, то минимальное количество циклов в перестановке должно быть равно трём, чтобы она имела неподвижные точки. То есть перестановки 1), 2), 4), 5) неподвижных точек не имеют. Для перестановки первого типа получим Рисунок убран из работы и доступен только в оригинальном файле.36 = Рисунок убран из работы и доступен только в оригинальном файле. = 90 неподвижных точек. Для каждой перестановки типа <2, 2, 2> по принципу умножения получаем по Р3 =3∙2∙1= 6 неподвижных точек. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения получим по Р3 =3∙2∙1∙1= 6 неподвижных точек. Применим лемму Бернсайда: Рисунок убран из работы и доступен только в оригинальном файле.(1∙90+ 4∙6+ 3∙6) = 11.

Итак, 11 различных ожерелий можно составить из двух синих, двух белых, двух красных бусин.

Задача 5. Сколькими геометрически различными способами три абсолютно одинаковые мухи могут усесться в вершинах правильного пятиугольника?

Решение. Обозначим М – множество различных способов расположения трёх одинаковых мух в вершинах пятиугольника, если вершины занумерованы. Тогда |M| = Рисунок убран из работы и доступен только в оригинальном файле.25 (3, 2)=Рисунок убран из работы и доступен только в оригинальном файле.=10 способов расположения мух, где 2 – количество элементов множества М1 = {м, с} (где м – муха, с – свободная вершина),

3, 2 – кратности соответственно м и с.

а) Вокруг центра пятиугольника имеется четыре поворота на углы Рисунок убран из работы и доступен только в оригинальном файле.. Им соответствуют перестановки:

1) (1, 2, 3, 4, 5)

2) (1, 3, 5, 2, 4)

3) (1, 4, 2, 5, 3)

4) (1, 5, 4, 3, 2)

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

5) (1) (2, 5) (3, 4)

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

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

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

9) (5) (1, 4) (2, 3),

где 1, 2, 3, 4, 5 – числа, с помощью которых занумерованы вершины пятиугольника. Вместе с тождественной перестановкой (1)(2)(3)(4)(5) имеем 10 элементов группы G. Итак, в группе G имеется:

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

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

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

Определим количество неподвижных точек для перестановок каждого типа. Чтобы перестановка имела неподвижные точки, минимальное количество циклов в перестановке должно быть равно двум, так как множество М1 состоит из двух элементов м и с. Поэтому перестановки 1) – 4) не имеют неподвижных точек. Тогда для перестановки типа <1, 1, 1, 1, 1> имеем по формуле: Рисунок убран из работы и доступен только в оригинальном файле.25 (3, 2) = Рисунок убран из работы и доступен только в оригинальном файле.= 10 неподвижных точек. Для каждой перестановки типа <1, 2, 2> получим по принципу умножения по Р2 =2∙1∙1= 2 неподвижные точки. По лемме Бернсайда получаем Рисунок убран из работы и доступен только в оригинальном файле.(1∙10+ 5∙2) = 2.

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

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

Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по формуле Рисунок убран из работы и доступен только в оригинальном файле.nk (k1, k2, …, kn) = получим |M| = Рисунок убран из работы и доступен только в оригинальном файле.28 (4,4) = Рисунок убран из работы и доступен только в оригинальном файле.= 70 по-разному раскрашенных кубов. Так как нам нужно раскрасить вершины в два цвета (4 - в красный, 4 - в синий), то минимальное количество циклов в перестановке должно быть равно двум. Поэтому все перестановки 1) – 24) (задача 1) имеют неподвижные точки. В результате в группе G имеется:

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

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

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

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

Тогда перестановка типа <1, 1, 1, 1, 1, 1, 1, 1> имеет Рисунок убран из работы и доступен только в оригинальном файле.28 (4,4) = Рисунок убран из работы и доступен только в оригинальном файле.= 70 неподвижных точек. Каждая перестановка типа <4, 4> имеет (по принципу умножения Р2 =2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2, 2, 2> имеется Рисунок убран из работы и доступен только в оригинальном файле.24 (2, 2) = Рисунок убран из работы и доступен только в оригинальном файле.= 6 неподвижных точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу умножения) Р2 =2∙1∙2∙1= 4 неподвижные точки. По лемме Бернсайда получаем Рисунок убран из работы и доступен только в оригинальном файле.(1∙70+ 6∙2 + 9∙6 + 8∙4) = 7.

Итак, семью способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну.

Задача 7. Сколькими различными способами можно грани куба раскрасить в четыре цвета так, чтобы все четыре цвета присутствовали в раскраске каждого куба?

Решение. Для решения этой задачи воспользуемся задачей 3. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по принципу умножения: первую грань можно раскрасить 4 способами, вторую – тремя, третью – двумя, четвёртую – одним способом, пятую – четырьмя, шестую – четырьмя способами. Получим |M| = 4∙3∙2∙1∙4∙4 = 384. Найдём геометрически различные способы раскраски. Для этого используем описанные в задаче 3 разложения в произведение циклов всех перестановок из группы G вращений куба. Так как в раскраске куба должны присутствовать четыре разных цвета, то минимальное количество циклов в перестановке должно быть равно четырём. Поэтому перестановки 1), 3), 4), 6), 7), 9) – 23) в задаче 3 неподвижных точек не имеют. Таким образом, неподвижные точки имеют 3 перестановки типа <1, 1, 2, 2> и 1 перестановку типа <1, 1, 1, 1, 1, 1>. Определим количество неподвижных точек для перестановок каждого типа. Для перестановки типа <1, 1, 1, 1, 1, 1> имеем по принципу умножения Р4 = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения имеется Р4 = 4∙3∙2∙1 = 24 неподвижные точки. По лемме Бернсайда получаем Рисунок убран из работы и доступен только в оригинальном файле.(1∙384+3∙24) = 19.

Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.

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

Познакомимся с наиболее общим методом пересчёта, который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с любым свойством P можно связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А1, образованное элементами, обладающими свойством Р, и А2, образованное элементами, не обладающими свойством Р, т. е. обладающими свойством Рисунок убран из работы и доступен только в оригинальном файле.. Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.

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

Пусть А – конечное множество и Рисунок убран из работы и доступен только в оригинальном файле.. Будем обозначать через Рисунок убран из работы и доступен только в оригинальном файле. дополнение А1 по отношению к А, а через Card A – число элементов в А.

Тогда

Рисунок убран из работы и доступен только в оригинальном файле..

Если Рисунок убран из работы и доступен только в оригинальном файле.и Рисунок убран из работы и доступен только в оригинальном файле., то

Рисунок убран из работы и доступен только в оригинальном файле. (1)

Рисунок убран из работы и доступен только в оригинальном файле..

Покажем, что формула (1) обобщается на случай n подмножеств Рисунок убран из работы и доступен только в оригинальном файле., i=1, 2, ... n:

Рисунок убран из работы и доступен только в оригинальном файле. (2)

Действуем по индукции. Имеем

Рисунок убран из работы и доступен только в оригинальном файле. (3)

Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:

Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле. (4)

Рассмотрим следующие подмножества множества An:

Рисунок убран из работы и доступен только в оригинальном файле.

Применяя (4) с A=An, имеем

Рисунок убран из работы и доступен только в оригинальном файле. (5)

Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:

Рисунок убран из работы и доступен только в оригинальном файле. (6)

Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы Рисунок убран из работы и доступен только в оригинальном файле. обладают свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество Рисунок убран из работы и доступен только в оригинальном файле.обладает свойством Рисунок убран из работы и доступен только в оригинальном файле.. Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).

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

Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.

Пример. Рассмотрим множество

Рисунок убран из работы и доступен только в оригинальном файле.

и следующие свойства:

четное число,

и А >6, (7)

и 2 < A < 8.

Подсчитаем число элементов А, обладающих свойством Рисунок убран из работы и доступен только в оригинальном файле.. Обозначим подмножества, соответствующие свойствам Р1, Р2, Р3, через А1, А2, А3. Тогда

Рисунок убран из работы и доступен только в оригинальном файле.

«Просеиваем» сначала А через Р1: Card A1=6. Затем просеиваем А1 через Р2 и Р3: Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.. Просеиваем Рисунок убран из работы и доступен только в оригинальном файле. через Р3: Рисунок убран из работы и доступен только в оригинальном файле. Итак, Рисунок убран из работы и доступен только в оригинальном файле.

Формула (6) не позволяет, однако, перечислить элементы искомого множества. Находим его, выписывая последовательно: Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.. Разумеется, для множества с небольшим числом элементов проще выписать искомое подмножество, однако это трудно сделать при большой мощности множества.

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

Теорема 1. Пусть А={1, 2, …,n} и а1, а2, …, аr, , i=1, 2, …,r, попарно взаимно просты. Количество целых чисел k таких, что 0 < k n, ai не делит k, i=1, 2, …,r, равно

(8)

Доказательство. Обозначим Рисунок убран из работы и доступен только в оригинальном файле. и выпишем формулу (2):

Рисунок убран из работы и доступен только в оригинальном файле. (9)

Имеем

Card A=n,

Card Ai=Рисунок убран из работы и доступен только в оригинальном файле., i=1, 2, …,r,

Рисунок убран из работы и доступен только в оригинальном файле., i≠j, i, j=1, 2, …,r,

∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ (10)

Рисунок убран из работы и доступен только в оригинальном файле.= Рисунок убран из работы и доступен только в оригинальном файле..

Подставляя (10) в (9), получаем (8).

Пример. Пусть Рисунок убран из работы и доступен только в оригинальном файле., а1=3, а2=7, а3=8.

Количество целых чисел, не превосходящих 35 и не делящихся ни на 3, ни на 7, ни на 8, равно

Рассмотрим другие приложения.

Количество целых чисел k таких, что

0 < kn, (k, n)=1, ,

обозначают через φ(n) и называют функцией Эйлера.

Теорема 2. Пусть . Тогда

Рисунок убран из работы и доступен только в оригинальном файле., (11)

где произведение берётся по всем простым делителям аi числа n.

Доказательство. Так как все ai делят n и взаимно просты, то имеем

Рисунок убран из работы и доступен только в оригинальном файле.=Рисунок убран из работы и доступен только в оригинальном файле..

По формуле (8)

Рисунок убран из работы и доступен только в оригинальном файле.

т. е. получаем (11).

Пример. Пусть n=84. Простыми делителями 84 являются 2, 3, 7; поэтому

Рисунок убран из работы и доступен только в оригинальном файле.

Функция Мёбиуса. Представим (11) в другом виде, используя функцию Мёбиуса μ(n), определяемую следующим образом:

μ(1)=1;

μ(n)=0, если n делится на квадрат простого числа;

μ(а1а2…аr)=(-1)r, если ai – различные простые множители, i=1, 2, …,r.

Преобразуем равенство (11), используя функцию Мёбиуса:

Рисунок убран из работы и доступен только в оригинальном файле.

Тогда

Рисунок убран из работы и доступен только в оригинальном файле., (12)

где суммирование производится по всем k, делящим n (включая 1).

Пример. Имеем

μ(1)=1, Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.

При n=84 формула (12) даёт

Рисунок убран из работы и доступен только в оригинальном файле.

Решето Эратосфена. Известен следующий способ перечисления простых чисел pi, pin: вычисляется Рисунок убран из работы и доступен только в оригинальном файле. и из последовательности 2, 3, …, n вычеркиваются последовательно все числа, кратные 2, затем кратные 3, …, кратные c. Оставшиеся числа и есть искомые.

Используя теорему 2, можно получить следующую формулу пересчёта. Если через M(n) обозначить количество простых чисел q таких, что Рисунок убран из работы и доступен только в оригинальном файле., то в силу (8)

M(n)= (13)

где pi -, i=1, 2, …,r, - простые числа, не превосходящие Рисунок убран из работы и доступен только в оригинальном файле. (- 1 в правой части добавляется, так как 1 не считается простым).

В силу (12)

M(n)= Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле., (14)

где суммирование в (14) производится по всем простым делителям n (включая 1).

Пример. Сколько простых среди чисел 2, 3, …, 84? Имеем Рисунок убран из работы и доступен только в оригинальном файле.=9. Простыми числами между 2 и 9 будут 2, 3, 5, 7. Согласно (13)

Рисунок убран из работы и доступен только в оригинальном файле.

Таким образом, имеется всего 19 + 4 = 23 простых числа среди 2, 3, …, 84. Решето Эратосфена перечисляет их: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.

Расширения данной темы: иногда подмножества не выделяются, а фиксируется число свойств, которыми обладают их элементы. Для этого случая можно вывести формулу, используя формулу (6).

§3. Разбиение фигур на части меньшего диаметра [1, 2]

Диаметром фигуры F назовём такое расстояние d, что, во-первых, расстояние между любыми двумя точками M и N фигуры F не превосходит d, и, во-вторых, можно отыскать в фигуре F хотя бы одну пару точек A, B, расстояние между которыми в точности равно d.

Примеры:

-   Если фигура F представляет собой сегмент круга, ограниченный дугой l и хордой а, то в случае, когда дуга l не превосходит полуокружности, диаметр фигуры F равен а; в случае же, когда дуга l больше полуокружности, диаметр фигуры F совпадает с диаметром всего круга.

-   Если фигура F представляет собой многоугольник, то его диаметром является наибольшее из расстояний между вершинами.

В фигуре может существовать и много пар точек, расстояние между которыми равно d: в случае эллипса такая пара точек только одна, в случае квадрата их две, в случае правильного треугольника – три, в случае круга таких пар бесконечно много.

Постановка задачи: Круг диаметра d нельзя разбить на две части, диаметр каждой из которых будет меньше d, но можно разбить на три такие части (рис. 4(а, б)).

Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.

Тем же свойством обладает равносторонний треугольник со стороной d. Но имеются фигуры, которые можно разбить на две части меньшего диаметра (рис. 5(а, б)).

Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.

Мы можем рассматривать для любой фигуры F задачу о разбиении её на части меньшего диаметра. Наименьшее число частей, которые для этого потребуются, обозначим через a(F). Если F – круг или равносторонний треугольник, то a(F) = 3, а для эллипса или параллелограмма a(F) = 2. Возникает вопрос, нельзя ли найти плоскую фигуру, для которой a(F)>3, то есть такую фигуру, что для разбиения её на части меньшего диаметра нельзя обойтись тремя частями, а потребуется 4 или большее число частей?

Ответ даёт теорема Борсука: Всякая плоская фигура F диаметра d может быть разбита на три части диаметра меньше d, то есть a(F) ≤ 3.

Лемма: Всякая плоская фигура диаметра d может быть заключена в правильный шестиугольник, у которого расстояние между параллельными сторонами равно d.

Доказательство леммы.

Проведём к фигуре F опорные прямые l1 и l2, причём l2 параллельна l1. Вся фигура будет находиться в полосе между прямыми l1 и l2, расстояние между которыми не превосходит d (так как диаметр фигуры F равен d) (рис. 6). Проведём к фигуре F две параллельные опорные прямые m1 и m2, составляющие с l1 угол 60°. Прямые l1, l2, m1, m2 образуют параллелограмм ABCD с углом 60° и высотами не превосходящими d, внутри которого целиком заключается фигура F. Проведём две опорные прямые p1, p2 фигуры F, составляющие с l1 угол 120°, и обозначим через M и N основания перпендикуляров, опущенных на эти прямые из концов диагонали AC параллелограмма (рис. 6). Покажем, что направление прямой l1 можно выбрать таким образом, чтобы выполнялось равенство AM=CN. Допустим, AMCN, и пусть, для определённости, AM<CN. Таким образом, величина y= AMCN отрицательна. Начнём непрерывно изменять направление прямой l1 так, чтобы она повернулась на 180° (фигуру F будем оставлять неподвижной). Вместе с прямой l1 будут менять своё положение прямые l2, m1, m2, p1, p2 (так как их положение определяется выбором l1). Поэтому при повороте прямой l1 будут непрерывно перемещаться и точки A, C, M, N, а значит, будет неЕсли у вас нет возможности самостоятельно написать дипломную - закажите её написание опытному автору»


Просмотров: 606

Другие дипломные работы по специальности "Математика":

Интеграл Лебега-Стилтьеса

Смотреть работу >>

Расширение кольца с помощью полутела

Смотреть работу >>

Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых второго и первого порядков

Смотреть работу >>

Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых третьего и первого порядков

Смотреть работу >>

Кольцо целых чисел Гаусса

Смотреть работу >>