Глава 1. Метод рекуррентных соотношений

Оглавление:

Ошибка! Неверная ссылка закладки.

Глава 2. CleanCenter

Глава 3. Reboot Now

Глава 1. Метод рекуррентных соотношений

Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения,

которое называется рекуррентным (см. Рекуррентное на стр. 2)(). Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов решение задачи легко находится.

Глава 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).

Метод подсчета числа элементов объединения множеств (см. Множества на стр. 1) () по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения.

Глава 3. Метод траекторий

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

Примечания:

– совокупность тех или иных переменных

–сам не знаю…

– Определённая цель