nm n

где

k m k j j m

дельта O =сигма (-1) C (k-j)

j=0 k

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. Метод траекторий.

Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством.

Основные формулы комбинаторики

Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них.

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

P_n = n!,

где n! = 1 * 2 * 3 ... n.

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений

A^m _n = n (n - 1)(n - 2) ... (n - m + 1).

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний

С ^m _n = n! / (m! (n - m)!).

примеры перестановок, размещений, сочетаний