Глава 2. Комбинаторика

Комбинаторикой называется раздел дискретной математики, который занимается следующими вопросами:

1. Задача перечисления: найти количество элементов заданной математи- ческой модели.

2. Задача перебора: построить алгоритм перебора этих элементов.

Основное внимание мы будем уделять задаче перечисления.

Конечная математическая модель в комбинаторике называется конфигурацией. Мы изучим следующие конфигурации: размещения, сочетания, разбиения и их обобщения. Для дальнейшего изучения рекомендуем [9], [10], [14].

Размещения

Дано n предметов и m ящиков, в которые размещаются предметы. Сколько существует размещений, удовлетворяющих некоторым заданным условиям?

Определение 1. Размещением с повторениями называется функция

f: {x₁, x₂, ×××, x_m} ® { y₁,y₂, ×××,y_n }.

Элементы x_i называются предметами, а y_j - ящиками.

Число всех размещений с повторениями равно количеству последовательностей {a₁,a₂, ×××, a_m} чисел 1£a_i£n и значит оно равно n^m.

Определение 2. Рассмотрим некоторое конечное множество равнове-роятных элементарных событий, которые мы будем иногда назвать исхода-ми. Событием называется подмножество множества всех исходов. Его эле-менты называются благоприятными исходами. Вероятность события определяется как отношение количества благоприятных исходов к количеству всех исходов.

Например, если мы бросаем монету, то возможны два исхода. Число исходов выпадения «орла» равно 1. Значит, вероятность выпадения орла равно ½.