Лекции.Орг
 

Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника


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



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

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

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

или

т.е.

.

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

.

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

 

, или , т.е. .

 

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

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

.

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

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

т.е. .


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

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

.

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

, .

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

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

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

Тогда

.

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

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

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

.

 

 





Дата добавления: 2015-05-08; просмотров: 100 | Нарушение авторских прав


© 2015-2017 lektsii.org.

Ген: 0.083 с.