Элементы комбинаторики

Определение 35. Комбинаторика – математический аппарат для вычисления числа различных комбинаций элементов множества.

Теорема 4. Из m элементов а ₁, а ₂,…, а_m и n элементов b ₁, b ₂,…, b_n можно образовать ровно различных пар (a_i, b_j), содержащих по одному элементу из каждой группы.

Доказательство. Составим из этих пар прямоугольную таблицу, содержащую m строк и n столбцов, так, чтобы пара (a_i, b_j) стояла на пересечении i -той строки и j- ого столбца. Каждая из пар встретиться в таблице один и только один раз, что и требовалось доказать.

Пример. Электрическая лампа с несколькими способами включения содержит три обычные лампочки и светящую арматуру, которая может работать в трех положениях или может быть выключена. Каждая из этих возможностей комбинируется с 0, 1, 2, 3 включенными лампочками. Следовательно, всего имеется возможных комбинаций, из которых одна (0, 0) означает, что лампа не светит. Остается 15 способов включения лампы.

Теорема 5. Пусть даны k групп элементов: m элементов первой группы а ₁, а ₂,…, а_m; n элементов второй группы b ₁, b ₂,…, b_n;…..; s элементов k - ой группы с ₁, с ₂,…, с_s. Тогда можно образовать ровно различных комбинаций , содержащих по одному элементу из каждой группы.

Пусть дано конечное множество , состоящее из n элементов. Его называют генеральной совокупностью.

Определение 36. Произвольное упорядоченное множество , состоящие из m (m < n) элементов, входящих в генеральную совокупность, называется набором или выборкой объема m из А.

Определение 37. Объем выборки – это количество элементов в выборке.

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

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

К основным комбинаторным конфигурациям относятся сочетания, размещения и перестановки.

Определение 39. Неупорядоченные наборы элементов называются сочетаниями, упорядоченные – размещениями, упорядоченные без повторений – перестановкой.

Определение 40. Комбинаторные формулы – формулы пересчета числа комбинаторных конфигураций.

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