Комбинаторика - важный раздел математики, знание которого необходимо представителям самых равных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по кодам и др. Комбинаторные методы лежат в основе решения многих задач теории вероятностей и ее приложений. В книге в популярной форме рассказывается об интересных комбинаторных задачах и методах их решения.
ПРЕДИСЛОВИЕ
Комбинаторика — ветвь математики, изучающая комбинации и перестановки предметов,— возникла в XVII в. Долгое время казалось, что комбинаторика лежит вне основного русла развития математики и ее приложений. Положение дел резко изменилось после появления быстродействующих вычислительных машин и связанного с этим расцвета конечной математики. Сейчас комбинаторные методы применяются в теории случайных процессов, статистике, математическом программировании, вычислительной математике, планировании экспериментов и т. д. Б математике комбинаторика используется при изучении конечных геометрий, комбинаторной геометрии, теории представлений групп, неассоциативных алгебр и т. д.
На русском языке есть несколько книг, посвященных комбинаторике: «Комбинаторика» М. Холла (М., 1970), «Введение в комбинаторный анализ» Дж. Риордана (М., 1963), «Прикладная комбинаторная математика» (М., 1968). Отдельным вопросам комбинаторики посвящены книги А. А. Зыкова «Теория конечных графов» (Новосибирск, 1969), Ф. Харари «Теория графов» (М., 1973), Т. Саати «Целочисленные методы оптимизации и связанные с ними экстремальные проблемы» (М., 1973) и др. Однако все эти книги предъявляют высокие требования к математической подготовке читателя. Популярные же книги обычно охватывают лишь немногие начальные сведения.
В 1969 г. автор сделал попытку популярно изложить некоторые вопросы комбинаторики («Комбинаторика». М., 1969). В основном книга была посвящена вопросам перечислений. Такие важные разделы, как теоремы о различных и общих представителях, теорема Рамсея, метод Пойя перечисления орбит и т. д., остались вне рамок книги. Поэтому возникла необходимость написать новую книгу, в которой наряду с вопросами перечислительной
ОГЛАВЛЕНИЕ
Предисловие .... ................ 3*
Глава I. Из истории комбинаторики и ее пррл о/кепи и .... 5 •
Дела давно минувших дней ............ 5й
Таинственная черепаха .............. <&
Комбинаторика в Древней Греции ....... 8)
Мистики, астрологи, каббалисты ........ 11
Комбинаторика и схоластики ........... 12;
Комбинаторика в странах Востока ........ 13
Liber Abaci ...» ................. 14
Игра в кости . . . ................ 15
Игрок и ученые .................. 17
Новая ветвь математики ............. 18
Шифры и анаграммы ............... 20 -.{
Иероглифы и клинопись ........... . . 22."
Комбинаторика в биологии ............ 25*
Модель ДНК .................... 26
Генетический код ................. 27 •
Химический пасьянс ................ 32
Комбинаторика эпохи компьютеров .,,,.,, 33 •"
Глава II. Возможное и невозможное в комбинаторике . . . . 35
Проблемы комбинаторики , , .......... 35
Магические квадрата ........... .... 38 ;
Восемь королев ................. . 40
Вся королевская конница .............. 42
Игра в 15 ......... , ............ 43
Офицерское каре , . . , .............. 45 '
Посев пшеницы . . . , . .............. 47 -;
Число знакомых . . ...... ......... 49 -
Научная переписка . . , .' ............ 50
Выбор представителей . . . ............ 52
Графическое решение . . ............. 55
Общие представители . . > ............ 58
Острова и мосты ..... . ............ 59
Кругосветное путешествие ............ 60
Четыре краски ................... 61
Задачи к главе II ............. . . . . 62;
Глава III. Комбинаторика кортежей и множеств ...... 73
....
Суеверный председатель ............. 73
Кортежи ............. , ...... , . 7"
206
Правило произведения............... 76
Размещения о повторениями........... 77
Коды........................ 77
Секретные замки................. 78
Первенство по футболу . . >........... 79
Задача о ладьях.................. 80
Перестановки с повторениями........... 81
Покупка пирожных................ 83
Карточки «Спортлото» ...»............ 85
Выигрыши «Спортлото»............ 86
Генуэзская лотерея.............. 87
Некоторые свойства сочетаний......... 89
Арифметический треугольник......... 90
Человек бродит по городу........... 91
Броуновское движение............. 93
Блуждания по бесконечной плоскости ..... 94
Корова или ворона?................ 96
Анализ отчета ...,..,............ 99
Плохая погода.................. 100
Формула включений и исключений....... 102
Частный случай формулы включевий и исключений ......................... 103
Решето Эратосфена................ 103
Задачи к главе III................ 105
Глава IV. Комбинаторика раскладок и разбиений..... 118
Шары и лузы.................... 118
Партия в преферанс................ 120
Сушка грибов................... 121
Разные статистики................. 122
Флаги на мачтах................. 123
Полное число сигналов.............. 124
Распределение нагрузки............. 124
Числа Стерлинга................. 126
Комбинаторика классификаций.......... 127
Жетоны в мешке.................. 129
Обобщенный арифметический треугольник .... 130
Проблема- абитуриента............. . 131
Отправка бандероли............... . 132
Комбинаторные задачи теории информации . . 134
Кролики Фибоначчи............... 134
- - --- ........ 136
Разбиение чисел Уплата денег
1(7 I_LtfJLMJ.U. fj,——---
Как разменять гривенник?.......
Диаграммная техника..........
Разбиения фигур.............
Алгебра комбинаторики........
Дробные предметы............
Ряд Ньютона...............
Производящие функции.........
Счастливые троллейбусные билеты....... лчи
Наборы гирь . . . .'................ 148
Задачи к главе IV................. 150
207
136 138 139 142 143 145 146 147 148
Глава V, Комбинаторные задачи с ограничениями .... 161
Перестановки с ограничениями.......... 161
Строительство лестницы ............. 162
Книжная полка.................. 163
Рыцари короля Артура.............. 163
Девушка спешит на свидание........... 164
Запретные зоны.................. 165
Общая формула.................. 166
За обеденным столом................ 169
Разбушевавшиеся слоны............. 171
Симметричные расстановки............ 173
Караван в пустыне................. 175
Затруднение мажордома.............. 177
Очередь в кассу.................. 178
У Шамаханской царицы..............182
Поглощающая и отражающая стенки . . . . . . 184
Задача о двух шеренгах............. 184
Задачи к главе V ,..........,..... 186
Глава VI, Комбинаторика орбит............... 191
Преобразования и орбиты............ 191
Хоровод...................... 192
Раскраска куба.................. 193
Черно-белый квадрат.............. . 194
Орбиты и группы преобразований ........ 195
Неподвижные элементы.............. 197
Черно-белый куб............'...... 199
Сопряжение и циклы ....... ........ 200
Задачи к главе VI................. 204
Цена: 150руб.
