01 случайные события / 13_Элементы комбинаторики
.doc
§7. Элементы комбинаторики.
При подсчете вероятности по классическому определению приходится пересчитывать число исходов опыта, т. е. число различных вариантов.
Это гораздо легче сделать, если использовать готовые формулы, полученные в специальном разделе математики, который называется
комбинаторика.
В нашем курсе нам понадобятся 4 формулы (вообще говоря, их там гораздо больше).
-
Основное правило комбинаторики (правило умножения).
Пусть некоторое
действие можно выполнить в два этапа.
На
первом из них есть k
вариантов выбора, на втором - l
вариантов.
При этом любой
выбор на первом этапе сочетается
с любым выбором
на втором этапе.
Тогда общее
число способов выполнить действие
равно:
(
К1) )
Для запоминания: схема дорог.
Из пункта A в пункт B ведет k дорог. Из B в C ведет l дорог.
Сколько всего разных путей из A в C ?
.
Пусть выбран путь №1 из A в B . У него есть l продолжений - путей из B в C . Это все разные пути. Уже l вариантов. Если из A в B выбираем путь №2, у него тоже l продолжений. Еще l вариантов. И так далее. Таким образом, получаем:
Этот прием позволяет решать очень многие задачи, связанные с пересчетом вариантов.
П
Д
Пример 2: Записывают пятизначное число, в котором все цифры разные. Сколько способов это сделать (сколько таких чисел) ?
Записываем первую цифру. У нас 9 вариантов выбора (любая цифра, кроме 0 ). Когда записываем вторую, одна цифра уже израсходована, но зато добавляется 0 - имеем 9 варантов выбора. Когда записываем третью, осталоь 8 вариантов (две цифры уже израсходованы). И так далее. Всего получаем:
Пример 3: Кодовый замок сейфа состоит из 5 дисков по 12 символов
на каждом. Сколько всего вариантов набора кода?
Когда выбираем какой то символ на первом диске, у нас 12 вариантов. На втором тоже 12 и любой символ на первом диске может сочетаться с любым символом на втором. И т.д.
Пример 4: Есть семь карточек с номерами 1, 2 , 3, .......7. Из них достают 4 выкладывают из них число. Сколько существует способов получить четное число?
Чтобы число было четным, на последнюю позицию нужно положить одну из цифр 2, 4, 6 – имеем 3 варианта.
После того, как последняя позиция заполнена, выбираем карточку на предпоследнюю позицию – 6 вариантов. На третью справа – 5 вариантов, на первую позицию – 4 варианта.
Если после заполнения последней позиции начать выкладывать карточки слева направо, число вариантов не изменится:
Вообще, процесс заполнения можно проводить в любой последовательности и от этого общее число вариантов не изменится.
-
Перестановки.
Имеется
множество из k
различных
элементов.
Его
упорядочивают,
располагают элементы в определенном
порядке. Каждое такое упорядоченное
множество называется
перестановкой
из k
элементов.
Удобна для запоминания следующая схема:
Число
называется
факториал.
Это
произведение всех чисел от 1
до k
(или наоборот, от k
до 1).
3!
= 3
2
1 = 6
; 5!
= 5
4
3
2
1 = 120
;
Замечание:
Формула получается очень просто, по тому же принципу, который применялся выше. Сначала отбираем один элемент, чтобы положить его на первую позицию. Для этого у нас k вариантов. Когда отбираем претендента на вторую позицию, один элемент уже израсходован, и число вариантов равно (k–1). Так как число позиций равно числу элементов, когда доберемся до последней позиции, на нее останется ровно 1 претендент:
-
Размещения и сочетания .
Имеется
множество из k
различных
элементов.
Из
него отбирают
часть, подмножество из l
элементов.
Если порядок
отбора элементов безразличен, то
получают
сочетание
из k
элементов по l
.
Если порядок
отбора элементов важен
(отобранные
элементы упорядочивают)
то получают
размещение
из k
элементов по l
.
Схемы для запоминания:
Формула для числа размещений:
Когда отбираем первый элемент, у нас k вариантов. Для второго (k–1) вариант. На последнюю позицию № l остается (k – (l+1)) претендент.
Если продолжать умножение дальше, до 1, получим факториал. Не хватает сомножителей (k-l) . . . 321 . Домножим и разделим на эти недостающие сомножители, получим факториалы, входящие в формулу (К3) .
Формула для числа сочетаний:
Пример 5: Сколько чисел можно соcтавить из цифр 1, 3, 5, 9 ?
Е
Пример 6: В фирме 5 сотрудников. Необходимо одновременно выехать в командировку в 5 разных городов. Сколько разных способов распределить места командировок ?
Пять элементов (сотрудников) нужно распределить по пяти местам (городам). Это – перестановка из 5 элементов:
Пример 7: Цифры 3, 4, 5, 6, 7, 8 раскладываются в произвольном порядке друг за другом. Сколько существует вариантов, при которых четные цифры стоят на четных местах?
Выполним действие в два этапа.
Первый. Сначала возьмем четные цифры 4, 6, 8 и положим их на четные места. Таких мест 3.
Если 3 элемента менять местами, это перестановка. Число вариантов
Второй. теперь разложим по оставшимся 3 местам нечетные цифры 3, 5, 7. Это опять перестановка из трех элементов:
Любой выбор на первом этапе сочетается с любым выбором на втором (схема дорог). Т.е., по основному правилу комбинаторики
Пример 8: Имеется 7 цифр: 2, 3, 4, 5, 6, 7, 8. Сколько четырехзначных чтсле можнл из них сосотавить?
Чтобы записать такое число нужно из этих 7 цифр отобрать часть ( 4 цифры ) и расположить по порядку. Т.е., любое такое число – это размещение из 7 элементов по 4.
Пример 9: В фирме работают 5 сотрудников. Для выполнения трех различных работ нужно отобрать трех исполнителей. Сколько разных способов это сделать?
Из 5 элементов (сотрудников) нужно отобрать часть – троих. Порядок отбора важен (разным людям поручаются разные работы). Это размещения из 5 по 3.
Пример 10: За 8 дней студент должен сдать 5 зачетов (можно сдавать только по одному зачету в день). Сколько разных способов составить расписание?
Из 8 элементов (дней) нужно отобрать часть – те 5 дней, в которые будут проводиться зачеты. Порядок сдачи зачетов важен (предметы разные). Это размещения из 8 по 5.
Пример 11: Предприятие собирается вложить деньги на вклады в разные банки суммами 250 и 500 тыс. грн. Для этого нужно выбрать два банка из 8. Сколько разных способов это сделать?
Из 8 элементов (банков) нужно отобрать часть – 2. Кроме того, среди этих двух выбрать, в какой сколько вкладывать (порядок отбора различается). Это размещения из 8 по 2.
Пример 12: Для выполнения срочной работы нужно отобрать 3 сотрудников из 9 работающих. Сколько разных способов это сделать?
Из 9 элементов (сотрудников) нужно отобрать часть – 3. Порядок отбора безразличен (они все трое будут выполнять одну работу) Это сочетание из 9 по 3.
П
Выполним действие в два этапа.
Первый. Отбираем 2 красных. Из 7 элементов (шаров) нужно отобрать часть – 2. Порядок отбора безразличен (важен только цвет). Это сочетание из 7 по 2.
Второй этан. Отбираем 3 черных. Из 12 шаров нужно отобрать 3. (порядок отбора безразличен). Это сочетание из 12 по 3.
Любой выбор 2 красных шаров сочетается с любым выбором 3 черных. Т.е., по основному правилу комбинаторики
Пример 14: Из 10 человек, пришедших сдавать экзамен, отбирают пятерых и рассаживают в первом ряду. Сколько существует вариантов, при которых двое друзей (А и Б) будут сидеть рядом?
Перебор вариантов выполним поэтапно.
Первый этап. Отбираем те 2 места, на которых будут сидеть рядом А и Б. Например:
.
Для этого у нас есть 4 варианта.
Второй этап. У нас есть 2 варианта выбора того, как именно посадить этих двоих:
Третий этап. После того, как посадили этих двоих, нужно рассадить на 3 оставшихся места еще 3 человека из 8 оставшихся. Из 8 элементов отбираем 3 и порядок отбора важен (разные способы рассадки). Это размещение из 8 по 3.
По основному правилу комбинаторики