Комбинаторикой называется раздел дискретной математики, который занимается следующими вопросами:
1. Задача перечисления: найти количество элементов заданной математи- ческой модели.
2. Задача перебора: построить алгоритм перебора этих элементов.
Основное внимание мы будем уделять задаче перечисления.
Конечная математическая модель в комбинаторике называется конфигурацией. Мы изучим следующие конфигурации: размещения, сочетания, разбиения и их обобщения. Для дальнейшего изучения рекомендуем [9], [10], [14].
Размещения
Дано n предметов и m ящиков, в которые размещаются предметы. Сколько существует размещений, удовлетворяющих некоторым заданным условиям?
Определение 1. Размещением с повторениями называется функция
f: {x1, x2, ×××, xm} ® { y1,y2, ×××,yn }.
Элементы xi называются предметами, а yj - ящиками.
Число всех размещений с повторениями равно количеству последовательностей {a1,a2, ×××, am} чисел 1£ai£n и значит оно равно nm.
Определение 2. Рассмотрим некоторое конечное множество равнове-роятных элементарных событий, которые мы будем иногда назвать исхода-ми. Событием называется подмножество множества всех исходов. Его эле-менты называются благоприятными исходами. Вероятность события определяется как отношение количества благоприятных исходов к количеству всех исходов.
Например, если мы бросаем монету, то возможны два исхода. Число исходов выпадения «орла» равно 1. Значит, вероятность выпадения орла равно ½.