Составители:
Рубрика:
3
ВВЕДЕНИЕ
Комбинаторика является разделом дискретной математики, ориен-
тированным на решение задач выбора и расположения элементов неко-
торого множества в соответствии с заданными правилами и ограниче-
ниями. Каждое такое правило определяет способ построения некоторой
комбинаторной конфигурации, поэтому комбинаторный анализ (комби-
наторика) занимается изучением свойств комбинаторных конфигураций,
условиями их существования, алгоритмами построения и оптимизацией
этих алгоритмов.
Этот раздел математики тесно связан с рядом других разделов дис-
кретной математики: теорией вероятностей, теорией графов, теорией
чисел, теорией групп и т. д.
Первые параграфы настоящего пособия посвящены элементам клас-
сической комбинаторики: размещениям, перестановкам и сочетаниям.
В последующих параграфах рассматриваются некоторые классы наи-
более часто встречающихся задач: комбинаторные задачи с ограниче-
ниями, комбинаторные задачи раскладок и разбиений, комбинаторные
задачи, решаемые с помощью рекуррентных соотношений.
Настоящее учебное пособие содержит большое число примеров,
заимствованных из книг известного российского математика и прекрас-
ного популяризатора математических идей Н.Я. Виленкина. К сожале-
нию, его книги “Комбинаторика” и “Популярная комбинаторика” прак-
тически невозможно найти в библиотеках технических вузов, в особен-
ности в библиотеках периферийных вузов. Только это, а также потреб-
ность в более сжатом изложении материала и привязки его к задачам
вычислительной техники побудило автора написать это учебное посо-
бие.
