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

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

Теорема 3. Из 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 способов включения лампы.

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

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

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

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

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

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

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

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

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