Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

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

Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники
Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Вятский государственный гуманитарный университет Математический факультет Кафедра алгебры и геометрии Выпускная квалификационная работа Связь комбинаторики с различными разделами математики Выполнила: студентка 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. Применение леммы Бернсайда к решению комбинаторных задач 1.1. Орбиты группы перестановок Пусть G – группа перестановок на множестве М={1, 2, , }. Подмножество ОМ называется орбитой группы G, если: а) α(a)O для любого αG и любого aO, то есть действие перестановок из G на элементы О не выводит за пределы О; б) любые два элемента из О можно перевести друг в друга некоторой перестановкой из G. Легко показать, что всякая группа перестановок G={&epsilo ;=α0, α1, , αk-1} имеет орбиты. Орбитами подобного вида исчерпываются все типы орбит, то есть, если О – орбита группы G и аО, то О=О(а). Любые две орбиты О(а) и О(b) либо совпадают (если bO(a)), либо не пересекаются (если bO(a)). Таким образом, множество М распадается в объединение непересекающихся подмножеств – орбит группы G. В связи с разбиением множества М на орбиты группы перестановок G возникают следующие два вопроса: 1) Сколько орбит имеет группа G на множестве М? 2) Какова длина каждой из этих орбит, то есть из скольких элементов они состоят? Ответим на эти вопросы. 1.2. Длина орбиты группы перестановок. Лемма Бернсайда Ответим на второй вопрос. Для любого элемента аМ можно рассмотреть группу Ga всех перестановок из G, для которых точка а является неподвижной. Она называется стабилизатором точки а. Ответим на вопрос, доказав следующую теорему: Длина орбиты О(а) равна индексу стабилизатора Ga в группе G, то есть O(a) = G : Ga . Доказательство. Пусть G={&epsilo ;=α0, α1, , αk-1}, Ga={&epsilo ;=&be a;0, &be a;1, , &be a;s-1}. Для подсчёта различных элементов в последовательности a=α0(a), α1(a), , αk-1(a) удобно особым образом расположить в ряд элементы группы G. Для этого используем тот факт, что группу G можно представить в виде объединения всевозможных непересекающихся правых классов смежности по подгруппе Ga, имеющих одинаковое число элементов. То есть существуют перестановки γ0=&epsilo ;, γ1, , γl-1 из группы G такие, что все перестановки ряда α0= &be a;0° γ0= &epsilo ;, α1= &be a;1° γ0, , αs-1= &be a;s-1° γ0, αs= &be a;0° γ1, αs 1= &be a;1° γ1, , α2s-1= &be a;s-1° γ1, ( ) - - - - - - - - - - - - - - - - - - - - - - - - - - - - α(l-1)s= &be a;0° γl-1, α(l-1)s 1= &be a;1° γl-1, , αls-1= &be a;s-1° γl-1 попарно различны и исчерпывают всю группу G. Для любого i=0, , l-1 применение s перестановок αis, αis 1, , α(i 1)s-1, образующих i-тую строку таблицы ( ), к элементу а даёт один и тот же элемент γi(а) (так как &be a;0, &be a;1, , &be a;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 . Теорема доказана. Теперь ответим на первый вопрос. Для этого сформулируем и докажем лемму Бернсайда. Пусть λ(α) – число неподвижных точек перестановки α, (G) – число орбит группы перестановок G={&epsilo ;=α0, α1, , αk-1}, действующей на множестве М={1, 2, , }. Тогда для любой группы перестановок имеет место равенство: (G)=λ(α), где αG. Доказательство. Рассмотрим отношение «перестановка α сохраняет неподвижным элемент m» между перестановками группы G и элементами множества М. Сопоставим парам (α, m), αG, mM, вершины прямоугольной сети и отметим те из них, для которых соответствующая пара (α, m) находится в указанном отношении, то есть α(m)=m (рис. 1). Иными словами, построим график указанного отношения. Error: Refere ce source o fou d Число отмеченных точек (точек, принадлежащих графику) можно подсчитать двумя способами: определить число отмеченных точек на каждой вертикали и просуммировать полученные величины или же определить число таких точек на каждой горизонтали и вычислить их сумму. Согласно определению отношения на каждой вертикали отмечаются все точки, сохраняемые перестановкой α, соответствующей этой вертикали. Их число равно λ(α). Поэтому число всех точек графика равно λ(α0) λ(α1) λ(αk-1)= λ(α), где αG. С другой стороны, на каждой горизонтали отмечаются все перестановки, сохраняющие элемент mM, отвечающий этой горизонтали. А такие перестановки образуют группу Gm – стабилизатор элемента m, - и их число, по теореме, доказанной ранее, равно Gm = G : O(m) . Поэтому при втором способе подсчёта числа отмеченных точек графика рассматриваемого отношения получаем выражение G1 G2 G = Gm (mM). Однако, если элементы i, j M содержатся в одной орбите, то О(i)=O(j), и поэтому Gi = G : O(i) = G : O(j) = Gj . Пусть О1, О2, , О – все орбиты группы G такие, что , и слагаемые в этом объединении не пересекаются. Разобьём Gm (где mM) на части так, чтобы внутри каждой из этих частей суммирование шло по элементам некоторой орбиты: m =m m m . Каждое из слагаемых в правой части этого равенства можно преобразовать следующим образом: m = = = = G . Поэтому m = G G = ∙ G . Таким образом, при втором способе подсчёта мы получили ∙ G отмеченных точек графика. Приравнивая величины, полученные при первом и втором способах, получим G = , то есть = (G) = . Лемма доказана. 1.3. Комбинаторные задачи Рассмотрим несколько примеров, иллюстрирующих возможности применения леммы Бернсайда при решении комбинаторных задач на перечисление. Задача 1. Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зелёный)? Решение. (В остальных задачах будем использовать обозначения, аналогичные обозначениям в этой задаче). Поскольку каждую из восьми вершин куба можно раскрасить тремя способами, причём независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить 38=6561 различными способами (по формуле ).

Многие из использованных им методов еще не были созданы, когда он приступил к работе. Он слил воедино труды многих превосходных математиков, установил взаимосвязи между различными идеями и разработал новые понятия, о которых другие математики боялись даже думать. В каком-то смысле, как сказал Барри Мазур, оказалось, что все размышляли над проблемой Ферма, но размышляли порознь, не помышляя о том, чтобы найти ее решение, потому что доказательство Великой теоремы Ферма потребовало бы всей мощи современной математики. То что сделал Эндрю, сводилось к восстановлению связей между разделами математики, казалось, разошедшимися навсегда. Его работа поэтому стала своего рода оправданием всей диверсификации, которую претерпела математика с тех пор, как была сформулирована проблема Ферма. История Великой теоремы Ферма завершилась самым эффективным образом. Для Эндрю Уайлса найденное им доказательство означало конец изоляции, почти чуждой математике, которая обычно представляет собой коллективную деятельность. В нарушение всех традиций Уайлс хранил молчание о своей работе вплоть до ее заключительной стадии

1. Разработка системы задач (алгоритмы-программы) по дискретной математике

2. Билеты по математике для устного экзамена и задачи по теме

3. Применение методов дискретной математики в экономике

4. Решение смешанной задачи для уравнения гиперболического типа методом сеток

5. Дискретная математика: "Графы"

6. Дискретная математика (Конспекты 15 лекций)
7. Задачи Пятого Турнира Юных Математиков
8. Конспект лекций по дискретной математике

9. Решение задачи Дирихле для уравнения Лапласа методом сеток

10. Экзаменационные билеты по математике

11. Экзаменационные билеты по численным методам за первый семестр 2001 года

12. Задачи к билетам для 11-го класса для общеобразовательных школ

13. Предмет и метод экономической теории

14. Билеты по математике

15. Дискретная математика

16. Математические методы в теории принятия решений

Микрофон "Новогодние песенки".
Этот удивительный микрофон превратит новогодний праздник в настоящее шоу! Он светится под музыку, как настоящий диско-шар! Слушай и пой 15
314 руб
Раздел: Микрофоны
Подставка для ножей, 11x22 см, синий.
Размеры: 11х22 см. Материал корпуса: пластик. Внутренняя часть: полипропиленовое волокно. Цвет: синий. Предназначена для безопасного и
628 руб
Раздел: Подставки для ножей
Настольная семейная игра "Ловушка для пингвина".
Настольная игра "Ловушка для пингвина" - это еще один повод собрать всю семью за одним столом. Игра состоит в том, чтобы
435 руб
Раздел: Игры на ловкость

17. Основы дискретной математики

18. Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг

19. Настоящая теория чисел

20. Об интегральных формулах Вилля-Шварца для трехсвязных областей и ее применение к краевым задачам Дирихле

21. Задача квадратичного программирования с параметром в правых частях ограничений и ее применение

22. Протокол динамического распределения адресов DHCP. Интернет-технология и ее применение для задач управления организацией
23. Формирование умений учащихся решать физические задачи: эвристический подход
24. Производная и ее применение в экономической теории

25. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

26. Задачи и методы теории знания

27. Применение методов математической статистики и теории вероятностей в задачах теоретической лингвистики при анализе устной и звучащей речи на русском и английском языках

28. Теория и методика русского языка (экзаменационные билеты)

29. Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

30. Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

31. Метод последовательных уступок (Теория принятия решений)

32. Методы и приемы решения задач

Масло Mommy care для отпугивания комаров, 50 мл, арт. MC_1696.
Масло для отпугивания комаров смесь натуральных и органических масел Москитуш обладает нежным ароматом, способным притуплять обоняние
890 руб
Раздел: Крем
Поильник–непроливайка Lubby "Русские мотивы" с трубочкой, 240 мл.
Мягкая силиконовая трубочка поильника нежно соприкасается с ртом Малыша. Оптимальная длина трубочки позволяет выпить все содержимое
387 руб
Раздел: Поильники, непроливайки
Бутылочка для кормления "Avent Classic+", 260 мл (розовая, рисунок: бабочка), от 1 месяца.
Ограниченная серия - бутылочка для кормления розовая c рисунком (бабочка), серия Classic+. Зарекомендовавшая себя серия Classic была
403 руб
Раздел: Бутылочки

33. Решение задач линейной оптимизации симплекс – методом

34. Теория графов. Задача коммивояжера

35. Решение задач на построение сечений в многогранниках методом следов

36. Новый метод «дополнительных краевых условий» Алексея Юрьевича Виноградова для краевых задач

37. Предмет психологии, ее задачи и методы

38. 6 задач по теории электрических цепей
39. Т.Парсонс: Аналитический реализм и понимание задач социологической теории (Доклад)
40. Плоская задача теории упругости

41. Задачи и методы планирования производства

42. Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

43. Предмет экономической теории. Методы экономического анализа

44. Вычисление интеграла методом Ньютона-Котеса (теория и программа на Паскале)

45. Роль теории дифференциальных уравнений в современной математике и ее приложениях

46. Методы решения некорректно поставленных задач

47. Решение задач по прикладной математике

48. Способ доказательства теоремы Ферма в общем виде с помощью методов элементарной математики

Настольная игра №23 "Стану отличником. Азбука + арифметика".
НИ "Стану отличником: Азбука-арифметика" предназначена для игр и занятий с детьми от 3 до 8 лет. Игра включает в себя
479 руб
Раздел: Алфавит, азбука
Набор для автолюбителя зимний "3 в 1".
Замучились удалять снег на автостоянке подручными средствами? Тратите уйму времени на осторожную очистку стёкол и кузова от ледяной корки?
1316 руб
Раздел: Прочее
Антимоскитная сетка для дверного проема, 2.1x1.0 м (арт. CF84-136).
Антимоскитная сетка предназначена для размещения на дверном проеме у Вас дома или на даче. Сетка выполнена в виде занавесок, оснащена
444 руб
Раздел: Сетки противомоскитные

49. Новые представления о задачах и методах гипербарической медицины

50. Налоговое администрирование: его цели, задачи, методы и формы

51. Применение обобщенного метода Фурье в задаче полого волновода треугольного сечения

52. Экзаменационные билеты по теории систем за весну 2001

53. Эвристические методы решения творческих задач

54. Методы информатики в обучении математике
55. Использование логических задач на уроках математики в начальной школе
56. Билеты по теории государства и права

57. Методы обучения математике

58. Формы и методы предъявления задач на уроках физике на материале изучения темы "Изменение агрегатных состояний вещества"

59. Решение задач транспортного типа методом потенциалов

60. Билеты по теории государства и права 100

61. Экзаменационные билеты по теории организации за второй семестр 2000 г

62. Задачи по теории управления

63. Методы построения эмпирического знания в теории и методике физического воспитания

64. Основные задачи термохимии. Использование калориметрических методов для определения теплот растворения солей

Чудо трусики для плавания, от 0 до 3-х лет, трехслойные, арт. 1432, для девочек.
Детские специальные трусики для плавания в бассейне и открытом водоеме. Плотно прилегают, отлично защищают! Изготовлены из хлопка, имеют
376 руб
Раздел: Многоразовые
Шкатулка музыкальная "Балерина и звездное небо".
Музыкальная шкатулка для украшений с классической музыкой. Когда шкатулка открыта - звучит музыка и фигурка кружится. Необычное зеркальце,
1116 руб
Раздел: Шкатулки музыкальные
Подставка для сортировки писем и бумаг "Germanium", черная.
Выполнена из металла (сетка). 5 вместительных секций. Размер - 195х365х205 мм. Цвет - черный.
758 руб
Раздел: Подставки, лотки для бумаг, футляры

65. Предмет и метод основ экономической теории

66. Билеты по предмету Математические методы в экономике за осенний семестр 2000 года

67. Билеты математические методы исследования экономики

68. Ответы на билеты по Экономической теории

69. Один из списков билетов по теории перевода, декабрь 2000

70. Один из списков билетов по теории перевода, декабрь 2000
71. Сборник задач по дисциплине Теория бухгалтерского учета
72. ГЕОСИСТЕМНОЕ прогнозирование: задачи, прогнозная информация, методы составления прогнозов

73. Методы решения задач

74. Оптимизация отбора оптимальных признаков на основе приме-нения методов моделирования эволюции для задачи распозна-вания текста

75. Метод АВИ в математической теории переноса вредных веществ в гетерогенных средах

76. Предмет, метод и задачи бухгалтерского учета

77. Страхование: теория и задачи

78. Сущность, методы и задачи регионалистики

79. Налоговый контроль: понятие, задачи, формы, виды и методы

80. Понятия, методы, задачи криминалистики

Ниблер с подкручивающейся ручкой Happy Baby "Nibbler twist" (lime).
Отличный помощник малышу. Необходим для того, чтобы ребенок мог есть любимые фрукты или овощи без риска подавиться. Подкручивающий
499 руб
Раздел: Ниблеры
Рюкзак для старших классов "Сладости", 41x32x14 см.
Рюкзак для старших классов, студентов, молодежи. 1 основное отделение, 1 дополнительный карман. Материал: водоотталкивающая ткань. Широкие
621 руб
Раздел: Без наполнения
Карандаши цветные "Jumbo. MAXI", 12 цветов.
Высококачественные карандаши. Яркая упаковка с изображениями лошадей обязательно понравится детям. Легко затачивается. Очень мягкий
374 руб
Раздел: 7-12 цветов

81. Предмет и методы теории государства и права

82. Аналіз чутливості використання методу Якобі для рішення задач лінійного програмування

83. Обзор методов обработки естественного языка в задачах дистанционного обучения

84. Решение задач линейного программирования симплекс методом

85. Решение задачи линейного программирования графическим методом

86. Решение прикладных задач численными методами
87. Рішення задач з елементарної математики в пакеті MAPLE-8
88. Розв’язання задач з елементарної математики в пакеті Maple-8

89. Симплекс метод решения задачи линейного программирования

90. Теория "Художественной воли", формальный метод А. Ригля

91. Аналитический метод в решении планиметрических задач

92. Логические задачи и методы их решения

93. Метод наименьших квадратов в случае интегральной и дискретной нормы Гаусса

94. Решение задач по курсу теории вероятности и математической статистики

95. Розв’язання лінійних задач методами лінійного програмування

96. Теория и методика обучения математике

Набор из скатерти и салфеток "Botanica", 140x180/42x42 см.
В набор входит скатерть и 6 салфеток "Botanica" 140x180/42x42 см. Салфетки, изготовленные из экологически чистого материала,
961 руб
Раздел: Салфетки сервировочные из ткани
Звуковой планшет "Транспорт".
Звуковой планшет - прекрасный подарок ребёнку! Он удобен и прост в использовании, подходит как для самостоятельного изучения, так и с
313 руб
Раздел: Планшеты и компьютеры
Мыло-пенка "Pigeon" для младенцев (сменная упаковка), 400 мл.
Мыло-пенка "Pigeon" разработано специально для мытья малыша с рождения. Низкий уровень кислотности такой же, как у нежной кожи
494 руб
Раздел: Гели, мыло

97. Методы решения краевых задач, в том числе "жестких" краевых задач

98. Р.Т. Галусарьян. Сборник задач и упражнений по курсу "Высшая математика"

99. Задачи и методы психологического обследования. Миннесотский Многофакторный Личностный Опросник

100. Предмет, задачи и методы патологии


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.