Основные комбинаторные конфигурации

Набор элементов x_{i 1},…, x_ik из множества X={ x ₁, …, x_n } называется выборкой объема k из n элементов или, иначе, (n, k)- выборкой.

Выборка называется упорядоченной, если задан порядок следования элементов в ней. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов в выборке не является существенным, то такая выборка называется неупорядоченной.

Перестановкой без повторений из n элементов называется всякий упорядоченный набор из этих элементов.

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

Число различных размещений (без повторений) из n элементов по k обозначается и вычисляется по формуле

Сочетанием без повторений из n по k называется неупорядоченный набор k элементов, выбранных из данных n элементов (неупорядоченная (n, k)-выборка без возвращения). Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Количество всех различных сочетаний (без повторений) из n элементов по k обозначают или :

Пример

Пусть C = {a, b, c, d}

Количество сочетаний из C, состоящих из 2 элементов равно

.

Получаем 6 подмножеств: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.

Пример

Коллектив должен состоять из 3 преподавателей и 4 программистов. Имеется 9 преподавателей и 11 программистов. Сколько существует способов сделать это?

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