Составители:
Рубрика:
141
3.2.10. Представление диэдральной группы ............................ 53
3.2.11. Скалярное произведение функций, заданных
на группе .................................................................. 54
3.2.12. Задачи для контрольной ............................................. 56
Литература ................................................................................ 62
4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ ................................................ 63
4.1. Основные понятия и теоремы комбинаторики .......................... 63
4.1.1. Размещения с повторениями ........................................ 63
4.1.2. Размещения без повторений ......................................... 65
4.1.3. Перестановки без повторений ........................................ 66
4.1.4. Перестановки с повторениями ...................................... 67
4.1.5. Основные правила комбинаторики ................................. 68
4.1.6. Главная теорема комбинаторики (теорема о включениях
и исключениях) .......................................................... 68
4.1.7. Сочетания без повторений ............................................ 70
4.1.8. Сочетания с повторениями ........................................... 72
4.1.9. Свойства чисел сочетаний ............................................. 73
4.1.10. Основные формулы классической комбинаторики ........... 74
4.2. Комбинаторные задачи с ограничениями ................................ 75
4.2.1. Простые задачи с ограничениями ................................. 75
4.2.2. «Задачи о смещениях (о беспорядках)» .......................... 76
4.2.3. «Задача о караване» ..................................................... 77
4.3. Комбинаторные задачи на раскладки и разбиения ................... 78
4.3.1. Раскладки с указанием числа предметов ........................ 78
4.3.2. Раскладка предметов на 2 кучки (в 2 ящика, кармана) ..... 79
4.3.3. Раскладка предметов по k ящикам ................................. 81
4.3.4. «Флаги на мачтах» ...................................................... 82
4.3.5. «Покупка билетов» ...................................................... 83
4.4. Рекуррентные соотношения в комбинаторике .......................... 83
4.4.1. «Задача о наклейке марок» ........................................... 84
4.4.2. «Задача об уплате долга» .............................................. 84
4.4.3. «Задача о размене гривенника» ..................................... 85
4.5. Задачи для контрольной работы ............................................. 85
Литература ................................................................................ 89
5. ТЕОРИЯ ГРАФОВ ....................................................................... 90
5.1. «Задача о кёнигсбергских мостах» ......................................... 90
5.2. Виды графов ........................................................................ 91
5.3. Способы задания графов ........................................................ 92
5.4. Понятие о плоских графах – «Задача о трех домах и трех
колодцах» ........................................................................... 95
5.5. Теорема Жордана о плоских графах ........................................ 96
5.6. Определение числа ребер в графе ........................................... 96
5.7. Теорема о количестве вершин нечетной степени ...................... 97
5.8. Графы типа «дерево» – основные соотношения ......................... 97
5.9. Цикломатическое число графа .............................................. 97
5.10. «Задача о наименованиях и переименованиях» ........................ 98
