Комбинаторика
3. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Это число равно
4. Задача коммивояжера, задача о бродячем торговце — комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещять города (по одному разу каждый) чтобы общее пройденное расстояние было минимальным?
Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора вариантов.
МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ
1. Метод рекуррентных соотношений.
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов решение задачи легко находится.
2. Метод включения и исключения.
Пусть N (A) — число элементов множества A. Тогда методом математической индукции можно доказать, что
N (A1 U A2 U … An) = N (A1) + … + N (An) - {N (A1 П A2) + … + N (An-1 П An)} + + {N (A1 П A2 П A3) + … + N (An-2 П An-1 П An)} - … … +(-1)^n-1*N (A1 П A2 П … П An-1 П An).
Метод подсчета числа элементов объединения множеств по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения.
3. Метод траекторий.
Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством.