Комбинаторный поиск

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

Примеры

Пример №1 (простейший комбинаторный поиск): В конкурсе участвуют 6 учеников, обозначим их 1,2,3,4,5,6. Как могут распределиться места между участниками в конкурсе? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Вариантов существует, ровно столько сколько существует вариантов перестановок из шести чисел.

Пример №2: Та же задача, но теперь для 6 участников конкурса есть три призовых места. Может быть призовые места распределятся 4,6,1, или 5,2,3, очевидно, что вариантов распределения в тройке победителей, может быть ровно столько, сколько существует способов выбора трех чисел из шести.

Пример №3: Усложняем задачу, когда для участников конкурса появляется возможность занять 1, 2 или 3 призовое место. Теперь нужно рассмотреть не только варианты, когда участник попадает в призовую тройку, но и то, как распределятся 1, 2 и 3 место между призерами.

Простейшие комбинации, с которыми имеет дело комбинаторный поиск - сочетания, размещения, перестановки.

Сочетанием из n элементов по m при 1 ≤ m ≤ n – называется всякая комбинация, объединяющая m каких-нибудь элементов из числа данных n элементов. Две такие комбинации считаются различными, если какой-нибудь из данных n элементов входит в одну из них, но не входит в другую комбинацию.

Размещением из n элементов по m при 1 ≤ m ≤ n - называется всякая комбинация, объединяющая в определенном порядке m каких-нибудь элементов из числа данных n элементов. Две такие комбинации считаются различными, если они отличаются либо своим составом, либо порядком следования входящих в них элементов. Либо и тем и другим.

Размещение из n элементов по n элементов называется перестановкой из данных n элементов.

Принципы комбинаторики

Существуют два основных принципа:

Принцип сложения

Предположим, что та или иная задача решается любым из k методов, причем первый метод можно применить n₁ способами, второй метод n₂ способами, ……., k-й метод n_k способами. Тогда задача решается n₁ + n₂ + ……. n_k способами.

Принцип умножения

Предположим, что та или иная задача решается за k последовательных этапов, причем число способов решения задачи на каждом следующем этапе не зависит от того, какими именно возможными способами она решалась на всех предыдущих этапах, и составляет n₁ способов на первом этапе, n₂ на втором этапе …n_k способов на k-м этапе. Два решения считаются разными, если они получены по-разному хотя бы на одном из этапов. В этих условиях задачу можно решить n₁ * n₂ * ····· n_k способами.

См. также

Литература

Е.С. Кочетков, С.О. Смерчинская, В.В. Соколов. Теория вероятностей и математическая статистика: учебник. — 2-е изд., перераб. и доп. — М.: ФОРУМ: ИНФРА-М, 2017. — 240 с.
А.С. Шведов. Теория вероятностей и математическая статистика. - Изд. дом Высшей школы экономики, 2016. - 280 с.