Элементы комбинаторики. Размещения. Перестановки. Сочетания

Пример: Пусть в распоряжении конструктора имеется четыре взаимозаменяемых блока (элемента): . Конструктивный узел состоит из трех блоков. Требуется найти множество конструктивных схем узла, отличающихся между собой как составом блоков, так и порядком их следования.

Упорядоченные наборы, состоящие из элементов (подмножества), взятых из множества элементов , отличающиеся хотя бы одним элементом (составом) и порядком их следования (расположением) называются размещениями (Arrangement) , а их количество обозначается в виде − число размещений из элементов по . Искомые упорядоченные наборы − конструктивные схемы, удобно находить с помощью следующих цепных диаграмм

Откуда непосредственно находится искомое множество конструктивных схем узла и их количество как число размещений из по :

или

т.е.

.

Методом математической индукции легко получить общую формулу

.

В частном случае, когда , упорядоченные наборы (подмножества) отличаются между собой лишь порядком следования элементов − их расположением в наборе. Состав элементов в наборе − неизменен. Такие упорядоченные соединения элементов в группы называются перестановками (Permutation) и их количество обозначается в виде − число перестановок из элементов. Очевидно, что

, или , т.е. .

Упорядоченные наборы, состоящие из элементов, взятых из элементов , отличающиеся между собой лишь составом (хотя бы одним элементом), а порядок следования элементов − произволен (несущественен), называются сочетаниями (Combination), а их количество обозначается в виде − число сочетаний из элементов по .

Так как размещения включают перестановки и сочетания, то очевидно

.

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

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

т.е. .

Откуда следует формула для числа сочетаний:

или в развернутом виде:

.

Учитывая, что , искомым формулам можно придать лаконичный вид:

, .

Пример: В ящике деталей, из них дефектных. Наудачу извлечены

деталей. Найти вероятность того, что все извлеченные детали качественны.

Решение: Общее число возможных элементарных исходов: . Число элементарных исходов, благоприятствующих появлению искомого случайного события − извлеченных деталей качественны: .

Тогда

.

Пример: В ящике находится семь блоков, обозначенные , , , , , , , из которых в определенной очередности собирается узел. Известно, что блоки и , а также и − взаимозаменяемые. С учетом взаимозаменяемости, номерам блоков присвоены буквы следующим образом: , , , , , , . Узел будет правильно функционировать (правильно собран), если блоки последовательно разместить в очередности, имеющей закодированное слово «бабушка». Найти вероятность того, что наудачу извлеченные блоки расположатся в порядке, при котором узел будет собран правильно, т.е. в результате испытания составится последовательность букв, имеющих смысл − «бабушка».

Решение: Общее число возможных элементарных исходов: , т.е. 5040. исходы благоприятствующих появлению искомого слова следующие:

Таким образом

.