Комбинаторика является разделом дискретной математики, ориентированным на решение задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами и ограничениями. Каждое такое правило определяет способ построения некоторой комбинаторной конфигурации, поэтому комбинаторный анализ (комбинаторика) занимается изучением свойств комбинаторных конфигураций,
условиями их существования, алгоритмами построения и оптимизацией
этих алгоритмов.
условиями их существования, алгоритмами построения и оптимизацией
этих алгоритмов.
Этот раздел математики тесно связан с рядом других разделов дискретной математики: теорией вероятностей, теорией графов, теорией
чисел, теорией групп и т. д.
чисел, теорией групп и т. д.
Первые параграфы настоящего пособия посвящены элементам классической комбинаторики: размещениям, перестановкам и сочетаниям.
В последующих параграфах рассматриваются некоторые классы наиболее часто встречающихся задач: комбинаторные задачи с ограничениями, комбинаторные задачи раскладок и разбиений, комбинаторные
задачи, решаемые с помощью рекуррентных соотношений.
задачи, решаемые с помощью рекуррентных соотношений.
Настоящее учебное пособие содержит большое число примеров,
заимствованных из книг известного российского математика и прекрасного популяризатора математических идей Н.Я. Виленкина. К сожалению, его книги “Комбинаторика” и “Популярная комбинаторика” практически невозможно найти в библиотеках технических вузов, в особенности в библиотеках периферийных вузов. Только это, а также потребность в более сжатом изложении материала и привязки его к задачам
вычислительной техники побудило автора написать это учебное пособие.
заимствованных из книг известного российского математика и прекрасного популяризатора математических идей Н.Я. Виленкина. К сожалению, его книги “Комбинаторика” и “Популярная комбинаторика” практически невозможно найти в библиотеках технических вузов, в особенности в библиотеках периферийных вузов. Только это, а также потребность в более сжатом изложении материала и привязки его к задачам
вычислительной техники побудило автора написать это учебное пособие.
1. ОСНОВНЫЕ ПОНЯТИЯ И ТЕОРЕМЫ
КОМБИНАТОРИКИ
1.1. Размещения с повторениями
Рассмотрим задачу: сколько разных 5-разрядных чисел можно составить из 10 цифр?
Перенумеруем разряды:
1
2
3
4
5
В первый разряд можно поставить одну из 10 цифр. Независимо от
того, какая цифра поставлена, во второй разряд можно также поставить
одну из 10 цифр и т. д. Всего получается 105 различных чисел.
Для двоичной системы счисления (используются только две цифры:
0 или 1) получаем 25 различных чисел. Для системы с основанием k и
числом разрядов n соответственно получаем:
того, какая цифра поставлена, во второй разряд можно также поставить
одну из 10 цифр и т. д. Всего получается 105 различных чисел.
Для двоичной системы счисления (используются только две цифры:
0 или 1) получаем 25 различных чисел. Для системы с основанием k и
числом разрядов n соответственно получаем:
A = kn
(1)
(1)
n – число позиций (разрядов); k – число элементов в каждой позиции (цифр).
В общем виде задача ставится следующим образом: имеется k типов предметов (количество предметов каждого типа неограничено) и n
позиций (ящиков, кучек, разрядов). Требуется определить, сколько разных комбинаций можно составить, если в позициях предметы могут
повторяться? Ответ дается формулой (1).
П р и м е р. Cколько разных чисел может содержать 10-разрядное
слово в троичной системе счисления? В первый разряд можно поставить один из трех символов (0, 1 или 2), во второй
В общем виде задача ставится следующим образом: имеется k типов предметов (количество предметов каждого типа неограничено) и n
позиций (ящиков, кучек, разрядов). Требуется определить, сколько разных комбинаций можно составить, если в позициях предметы могут
повторяться? Ответ дается формулой (1).
П р и м е р. Cколько разных чисел может содержать 10-разрядное
слово в троичной системе счисления? В первый разряд можно поставить один из трех символов (0, 1 или 2), во второй