Категория: Математика
Условие задачи (тема реферата, контрольной, курсовой работы или диплома):Дискретная математика. Комбинаторика.
Применение леммы Бернсайда к решению комбинаторных задач.
Оглавление
Введение 2
1. Орбиты группы перестановок 3
2. Длина орбиты группы перестановок 3
3. Формулировка леммы Бернсайда 4
4. Доказательство леммы Бернсайда 5
5. Комбинаторные задачи о раскраске 6
5.1. Задача 1 6
5.2. Задача 2 10
5.3. Задача 3 12
5.4. Задача 4 13
Заключение 14
Список литературы 16
Введение
Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов называется комбинаторикой. Комбинаторика возникла в XVI веке. Вопросы, касающиеся азартных игр, явились движущей силой в развитии комбинаторики, поскольку в жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры: карты и кости. Сейчас комбинаторные методы применяются как в самой математике, так и вне её – теория кодирования, планирование эксперимента, топология, конечная алгебра, математическая логика, теория игр, кристаллография, биология, статистическая физика, экономика и т.д.
Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования.
Уильям Бернсайд - английский математик-алгебраист. Член Лондонского королевского общества, профессор (с 1885) Морского колледжа в Гринвиче. Известен работами по теории групп, теории представлений и характеров групп, указал критерий непростоты конечных групп. Ему принадлежит также ряд работ по теории вероятностей, по автоморфным функциям, по теории волн в жидкостях и др.
Бернсайд сформулировал и доказал эту лемму (без указания авторства) в одной из своих книг (1897 год), но историки математики обнаружили, что он не был первым, кто открыл её. Коши в 1845 году и Фробениусу в 1887 году также была известна эта формула. По-видимому, лемма была столь хорошо известна, что Бернсайд просто опустил указание авторства Коши. Поэтому эта формула иногда называется леммой Бернсайда, а иногда - теоремой Коши-Фробениуса.
Это название не столь туманно, как кажется: работа Бернсайда была столь плодотворной, что большинство лемм в этой области принадлежит ему.
В ходе курсовой работы решены следующие практические задачи
Задача 1
Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зелёный)?
Задача 2
Грани куба можно раскрасить: а) все в белый цвет; б) все в чёрный цвет; в) часть в белый, а остальные в чёрный. Сколько имеется разных способов раскраски?
Задача 3
Сколькими способами можно раскрасить вершины куба в два цвета (красный и синий) так, чтобы вершин каждого цвета было поровну?
Задача 4
Сколькими различными способами можно грани куба раскрасить в четыре цвета так, чтобы все четыре цвета присутствовали в раскраске каждого куба?
Список литературы
- Виленкин Н.Я. Комбинаторика - М.: Наука, 1969, 328 с. – ил.
- Калужнин, Л.А. Преобразования и перестановки – 2-е издание изм. и доп. - М.: Наука, 1985, 160 с. – ил.
- Виленкин Н.Я. Популярная комбинаторика - М.: Наука, 1975, 208 с. – ил.