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

Комбинаторика (комбинаторный анализ) – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.

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

Прежде чем решать эту задачу, необходимо определить правила выбора.

Так, выбор может быть упорядоченным и неупорядоченным. В случае упорядоченного выбора важен порядок выбора элементов. Так, наборы {} и {}при таком выборе считаются различными.

В случае неупорядоченного выбора важен только состав набора и не важен порядок выбора элементов. В этом случае наборы {} и {} считаются одинаковыми.

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

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

Рассмотрим число наборов, содержащих элементов, сформированных на основе – элементного множества.

Упорядоченный выбор с возвращением (размещения с повторениями).

Число размещений с повторением – элементного множества по местам обозначается и вычисляется по формуле .

Упорядоченный выбор без возвращения (размещения без повторений).

Число размещений без повторений n – элементного множества по m местам обозначается и вычисляется по формуле: ; где .

Пример1.1.1. Пусть есть 5 сигналов .

Сколько 3 – элементных кодовых комбинаций можно составить в случае, если:

а) если сигналы в кодовой комбинации могут повторяться.

б) если сигналы в кодовой комбинации не повторяются

Решение:

а) ;

б)

Неупорядоченный выбор без возвращения (сочетания без повторений).

Число сочетаний без повторений, содержащих элементов и построенных на основе – элементного множества, обозначается и вычисляется по формуле:

.

Неупорядоченный выбор с возвращением (сочетания с повторениями).

Число сочетаний с повторениями, содержащих элементов и построенных на основе – элементного множества, обозначатся и вычисляется по формуле:

.

Дата добавления: 2014-01-04