Правила и формулы комбинаторики при вычислении вероятностей

  • 1. Правило суммы: если элемент х можно выбрать пх способами и если, после его выбора элемент у можно выбрать пу способами, то выбор «либо х, либо у» можно осуществить пх + пу способами.
  • 2. Правило произведения: если элемент х можно выбрать пх способами и если после его выбора, элемент у можно выбрать пу способами, то выбор упорядоченной пары (х, у) можно осуществить пхпу способами.

Различающиеся только цветом пх + пу шаров распределены по двум урнам: в первой урне пх шаров, во второй пу. Выберем случайным образом урну (это можно сделать так: подбросим монету и при выпадении орла выберем первую урну; цифры - вторую), а затем из нее случайным образом шар (так как шары различаются только цветом, то это можно сделать так: перемешать шары и, закрыв глаза, вытащить один). Так как заранее не известно, из какой урны будет вынут шар, то число вариантов цвета для шара, вынутого либо из первой, либо из второй урны, равно пх + пу.

Теперь случайным образом выберем шар из первой урны, а затем — случайным образом шар из второй урны. Так как шар, вынутый из первой урны, имеет пх вариантов цвета и при каждом из этих вариантов шар, вынутый из второй урны, имеет пу вариантов цвета, то различных упорядоченных пар цветов для двух вынутых шаров (упорядоченность пар цветов означает, что, например, пары «синий, белый» и «белый, синий» различны) будет пх пу.

3. Перестановки:

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

Число перестановок без повторений из п элементов обозначают символом Рп и подсчитывают так:

(символ п читается «эн факториал»; п равен произведению натуральных чисел от 1 до п; по определению 0! = 1).

Перестановками с повторением из п элементов к типов (к < п):

число элементов первого типа п, число элементов второго типа П2, ..., число элементов к-го типа пк

называются все возможные последовательности исходных п элементов.

Число перестановок с повторениями обозначают символом Рп =/1|+И2+ ...+«* И

подсчитывают так:

I

Пример 8.

Перестановки без повторений из п = 3 различных элементов: а, Ь, с таковы: а,Ь,с; Ь,а,с; Ь,с,а; а,с,Ь; с,Ь,а; с,а,Ь. Число перестановок равно 6. И согласно формуле (4.4)

Пример 9.

Перестановки элементов с повторениями из п = 3: а,а,Ь двух типов (тип «а» повторяется п — 2 раза, тип «Ь» повторяется П2 = 1 раз), таковы: а,а,Ь; а,Ь,а; Ь,а,а.

получим такой же результат: />3 = 3! = 1 . 2 • з = 6.

Число перестановок равно 3.

И согласно формуле (4.5) получим такой же результат:

Замечания.

• Если все п элементов разных типов т.е. число типов к = 1 + 1 + ...+ + 1 = п, то число перестановок с повторениями равно числу перестановок без повторений. Действительно,

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

Задача 3.

По следствию должны пройти пять человек: А, В, С, D, Е. Какова вероятность того, что в списке этих пяти человек, составленном случайным образом:

  • а) В будет следовать сразу после А;
  • б) В не будет перед А?

Решение.

Список из пяти человек можно составить N = 5! способами — это общее число равновероятных возможностей.

  • а) «В следует сразу после К» в списках следующих видов:
    • • А, В, ?, ?, ? — таких списков Р3, = 3!, так как последовательность трех букв — трех человек С, D, Е на последних трех местах — это некоторая перестановка букв С, D, Е, а число таких перестановок равно Р3 = 3!,
    • • ?, А, В, ?, ? — таких списков тоже 3!,
    • • ?, ?, А, В, ? — таких списков тоже 3!,
    • • ?, ?, ?, А, В — таких списков тоже 3!.

Поэтому в соответствии с правилом суммы число списков, в которых В следует сразу после А равно: М = 3! +3!+3!+3!=4 • 3! и искомая вероятность Р = M/N = (4 • 3!)/5! = 1/5.

  • б) «В не будет перед А» в списках следующих видов:
    • • д 9 9 9 9 — таких списков Р4, = 4! (последователь-
    • —I—^' ность четырех различных букв В, С, D, Е

места для в на последних четырех местах — это некоторая перестановка этих букв, а число таких перестановок равно Р4 = 4!),

• 9 д 9 9 9 — таких списков 4! — 3! (если бы не было

' ограничений на расположение В, то число

места для в списков вида «?, А, ?, ?, ?» было бы равно

4!; из этого числа надо вычесть количество списков вида «В, А, ?,?,?», а их 3!),

. 9 ? a 9 ? таких списков 4! — 2 • 3! (из 4! списков вида

^ «?, ?, А, ?, ?» вычитаем 3! списков вида «В, ?,

места для В д ^ 9» и 31 списков вида «?; В, Д? ?»)?

• ?, ?, ?, А, В — таких списков 3!

Поэтому число списков, в которых «В не будет перед А» , М = = 4! + (4! — 3!) + (4! — 2 • 3!) + 3! = 60 и вероятность того, что в списке, составленном случайным образом, «В не будет перед А» Р = M/N = = 60/5! = 0,5.

Задача 4,

Какова вероятность получить слово «юрист», переставляя в случайном порядке буквы этого слова? Какова вероятность получить слово «математика», переставляя в случайном порядке буквы этого слова?

Решение.

В слове «юрист» все 5 букв разные: число перестановок этих букв равно N = Р$ = 5! и лишь М = 1 вариант из 5! вариантов дает слово «юрист». Поэтому вероятность получить это слово Р = =M/N= 1/5! = 1/120.

В слове «математика» п = 10 букв, однако различных букв

к = 6:

«м», которая повторяется п =2 раза,

«а», которая повторяется П2 =3 раза,

«т», которая повторяется щ = 2 раза,

«е», которая повторяется п4 = 1 раз,

«и», которая повторяется «5 = 1 раз,

«к», которая повторяется п^ = 1 раз.

Поэтому перестановки букв слова «математика» — это перестановки с повторениями из п = 10 элементов к = 6 типов, и в соответствии с формулой (4.5) общее число таких перестановок - 10'

^10=2+3+2+1+1 =-= 151 200. Из них только одна пере-

2J 2| 2! 1! И и к

становка дает слово «математика»; вероятность получить это слово, случайно переставляя буквы, равна 1/151 200.

4. Размещения:

Размещениями без повторений из п различных элементов по т элементов (т < п) называются все такие последовательности т различных элементов, выбранных из исходных п, которые отличаются друг от друга или порядком следования эле-

Размещениями с повторениями из элементов к типов по т элементов (кит могут быть в любых соотношениях: т<к, т>к) называются все такие последовательности т элементов, принадлежащих исходным типам, которые отличаются

Пример 10.

Размещения без повторений из п = 3-х различных элементов: а,Ь,с по т = 2 элементов таковы: а, Ь; Ь, а; а, с; с,а; Ь,с; с,Ь. Число размещений равно 6; и согласно формуле (4.6) получим такой же результат:

ментов или составом элементов.

Число размещений без повторений из п элементов по т обозначают символом А”',

где п = 1 • 2 • 3 • ... • п;

(п — т) = 1 • 2 • ... • (п — т).

Выборка без возвращения и

друг от друга или порядком следования элементов или составом элементов.

Число размещений с повторениями из к типов элементов по т элементов

обозначают А'",

Пример 11.

Размещения с повторениями из элементов к = 2-х типов: тип «а» и тип «Ь», по т = 3 элементов таковы: a,a,a; b,a,a; a,b,a; a,a,b; b,b,a; b,a,b; a,b,b; b,b,b. Число размещений с повторениями равно 8; и согласно формуле (4.7) получим такой же результат:

Замечание.

Формулой (4.7) мы пользовались и ранее, не приводя ее. Так подсчет числа строк в таблице истинности высказывания, состоящего из т =

= 3-х простых высказываний, каждое из которых может быть к = 2-х типов (или «И» — ИСТИННЫМ, ИЛИ «Л» — ложным), или подсчет числа подмножеств множества Q, состоящего из т = 3-х элементов, для каждого из которых может быть к = 2 варианта (или элемент войдет в подмножество или не войдет), — это подсчет числа размещений с повторениями:

выборка с возвращением

• Выборка без возвращения. Пусть имеется совокупность п элементов, пронумерованных числами 1, 2, ..., п; назовем эту совокупность генеральной. Случайным образом выберем элемент (этот выбор можно осуществить так: номера напишем на одинаковых карточках и, перемешав карточки, вслепую наугад вытащим одну; ее номер и будет номером отобранного элемента). Отобранный элемент отложим в сторону. Повторим выбор т раз (т<п), не возвращая отбираемые элементы в исходную генеральную совокупность (не возвращая отбираемые карточки обратно). В результате окажется выбранной некоторая группа из т элементов. Ее называют т — выборкой без возвращения из генеральной совокупности объема п. Вернем т отобранных элементов в генеральную совокупность и вновь «без возврата» отберем из п элементов т элементов и т.д. Сколько существует различных т выборок, если различными считать выборки, отличающиеся или составом номеров вошедших в них элементов или порядком следования номеров? Число таких выборок равно числу размещений без повторений (ведь в выборке не может оказаться одинаковых номеров) из п по т:

Выборка с возвращением. Из той же совокупности п элементов отберем т элементов, но перед выбором каждого следующего элемент, отобранный на предыдущем шаге, будем возвращать в исходную генеральную совокупность, предварительно, запомнив его номер. Выбранную (запомненную) группу из т элементов называют т - выборкой с возвращением из генеральной совокупности объема п (при выборке с возвращением тип могут находиться в любом соотношении: т<п и т>п). Поскольку каждый из отобранных т элементов может быть п типов: иметь номер 1, иметь номер 2, иметь номер п, то число различных т выборок с возвращением равно числу размещений с повторениями (ведь в выборке могут оказаться два и более одинаковых номеров) из элементов п

типов по т элементов: А" = пт .

Задача 5.

В фирме работают 8 человек одинаковой квалификации, среди них Иванов, Петров, Сидоров. Случайно выбранным трем из них (из восьми) поручают три различных вида работ (первому выбранному — работу первого вида, второму выбранному — второго вида, третьему — третьего вида). Какова вероятность того, что работа первого вида будет поручена Иванову, второго — Петрову, третьего - Сидорову?

Решение.

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

8!

отбора m = 3 из л = 8 N = = -——- = 336 , и только в одном

(8-3)!

варианте = 1) из этих 336 работа первого вида будет поручена Иванову, второго — Петрову, третьего — Сидорову. Поэтому искомая вероятность Р— M/N= 1/336.

Задача 6.

Замок камеры хранения имеет четыре диска, каждый из которых разделен на 10 секторов; на секторах каждого из дисков написаны цифры 0, 1,2, ..., 9. Какова вероятность открыть закрытую камеру для человека:

  • а) забывшего все, что он набрал на дисках, закрывая камеру;
  • б) помнящего только цифру, набранную на первом диске;
  • в) помнящего только, что ни на втором, ни на третьем, ни на четвертом диске он не набирал цифры 6?

Решение.

  • а) Пытаясь открыть камеру с четырьмя дисками, человек, по сути, выбирает количество цифр т = 4 из п — 10, при этом осуществляется выбор с возвратом. Общее число вариантов такого выбора N = А*0 = 104, из которых только в варианте М = 1 камера откроется. Поэтому искомая вероятность равна 1/104.
  • б) При известной цифре на первом диске, общее число вариантов «набора» цифр на трех оставшихся дисках N = Д30 = 103

Искомая вероятность равна 1/103.

  • в) На первом диске может быть набрана любая из десяти цифр. Число вариантов набора цифр (уже не из десяти, а из девяти) на трех оставшихся дисках равно = 93. Общее число вариантов набора цифр на четырех дисках, с учетом правила произведения, будет N= 10 • 93. Искомая вероятность равна 1/(10 ? 93).
  • 5. Сочетания:

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

Сочетаниями с повторениями из элементов к типов по т элементов (кит могут быть в любых соотношениях: т<к, т>к) называются все такие последовательности т элементов, принадлежащим исходным типам, которые отличаются друг от друга составом элементов.

Число сочетаний без повторений из п элементов по т обозначают символом С"

Пример 12.

Сочетания без повторений из трех различных элементов, /7 = 3: а,Ь,с по т = 2 таковы: а,Ь; а,с; с,Ь (сочетания отличаются друг от друга только составом элементов, поэтому, например, последовательности «а,Ь» и «Ь,а» — это одно и то же сочетание). Число сочетаний без повторений - 3. И согласно формулы (4.8) получим такой же результат:

Число сочетаний с повторениями из к типов элементов по т элементов обозначают символом С"

Пример 13.

Сочетания с повторениями из элементов двух типов, к = 2: тип «а» и тип «Ь» по т = 3 таковы: а,а,а; Ь,а,а; b,b,a; b,b,b (сочетания отличаются друг от друга только составом элементов, поэтому, например, последовательности: «Ь,а,а», «а,Ь,а» и «а,а,Ь» — это одно и то же сочетание).Число сочетаний с повторениями — 4. И согласно формулы (4.9) получим такой же результат

Задача 7.

В примере 5 в качестве «голосующей коалиции» был рассмотрен Совет безопасности ООН. Каково число выигрывающих и минимальных выигрывающих коалиций в Совете безопасности?

Решение.

Напомним выигрывающая коалиция включает «большую пятерку» и нс менее двух из шести представителей малых наций. Поскольку «большая пятерка» в любой выигрывающей коалиции обязательно должна присутствовать, то вариативность выигрывающих коалиций определяется количеством (или 2, или 3, или 4, или 5, или 6) и составом вошедших в них представителей малых наций. Число вариантов выбора из 6 представителей малых наций двух представителей равно числу сочетаний (ведь порядок выбора не важен!) без повторений из п = 6, по т — 2, т.е.

  • (-2 __2:_= 15 именно столько будет минимальных
  • 6 2! (6-2)!

выигрывающих коалиций. Аналогично, число вариантов выбора из 6 представителей малых наций трех равно с = 20 , четырех —

САЬ - 15 , пяти — с| = 6 , шести — С% = 1 • Окончательно, число выигрывающих коалиций, в соответствии с правилом суммы, равно С62 + Cl + С64 5Ь+ С66 = 57 .

Задача 8.

Известно, что 5 из 40 пассажиров автобуса замешаны в похищении крупной суммы денег. На остановке к автобусу подошел инспектор уголовного розыска и заявил, что ему для обнаружения по крайней мере одного преступника достаточно произвести обыск у шести наугад выбранных пассажиров. Что руководило инспектором: риск или трезвый расчет?

Решение.

Дадим «урновую» интерпретацию условий задачи. Пусть К — 40 пассажиров — это 40 пронумерованных шаров в урне, из которых 1 = 5 черные (это виновные пассажиры) и K—L = 35 — белые (это невиновные). Из урны наудачу берут к = 6 шаров (пассажиров). Число вариантов выбора к = 6 из К = 40 шаров

N = СкК — С40 (используем сочетания без повторений, так как

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

  • • либо / = 1 черный шар и k — I = 5 белых,
  • • либо 1—2 черных шара и к — I — 4 белых,
  • • либо 1—3 черных шара и к — I — 3 белых,
  • • либо 1=4 черных шара и к — 1= 2 белых,
  • • либо 1=5 черных шаров и к — I = 1 белый.

Число вариантов выбора / = 1 черного шара (виновного) из L = 5 черных равно C'L - С, а поскольку в каждом таком варианте должно быть выбрано к — 1=6— 1=5 белых шаров (невиновных) из К — L = 40 — 5 = 35 белых, что можно сделать СкК~ = С|5 способами, то число вариантов выбора / = 1 черного шара и к — I = 5 белых, согласно правилу произведения, равно С[СкК~ = С5С35 (4.30,а). Аналогично число вариантов отбора:

  • 1=2 черных и к — 1 = 6 — 2 = 4 белых шара равно С\_СкК = С52С345 (рис. 4.30,6),
  • 1=3 черных и к — I = 3 белых = С53Сз5,
  • 1 = 4 черных и к — I = 2 белых = С54С25,
  • 1=5 черных и к — I = 1 белых = С55Сз5.

Рис. 4.30

Тогда число вариантов выбора 6 шаров (пассажиров) из 40, в которых окажется по крайней мере один черный шар (виновный), согласно правилу суммы, будет М = ClCj) + С52С345 + +

+C*C*}+ClCl5 =2 215 220- И вероятность обнаружения в выборке из шести пассажиров по крайней мерс одного преступника равна „ М 2 215220 Лс_

Р=— =-^— = 0,57, т.е. вероятность превысила значение

N Q,

0,5, что, по-видимому, и дало основание инспектору назвать число 6.

Вероятность того, что при отборе «без возвращения» из К пронумерованных шаров, среди которых L черных и К — L белых, к шаров в выборке окажется / черных и к — I белых, рассчитывается по формуле гипергеометрической вероятности:

Задача 9.

Инвестор формирует портфель ценных бумаг. Он может вложить свои деньги в акции 5 различных фирм. Сколькими способами инвестор может образовать набор из 7 акций и какова вероятность того, что в набор попадут 4 акции, принадлежащие различным фирмам?

Решение.

По условию из акций, количество типов которых к = 5, инвестор составляет набор из семи акций (т = 7), в число таких наборов может, в том числе, входить и набор, все 7 акций которого принадлежат какой-то одной фирме. Очевидно, что для инвестора важен только состав набора: акции каких фирм и в каких количествах они входят в набор, и совсем не важен порядок следования отобранных акций. Поэтому количество таких наборов равно числу сочетаний с повторениями из элементов к = 5 типов по

т =7 элементов: N = С] или, учитывая формулу (4.9),

Среди этих наборов количество наборов, в каждом из которых 4 акции принадлежат различным фирмам, равно числу сочетаний без повторений из 5 элементов (5 различных фирм) по 4:

Г4

га d М с5 5 1

Искомая вероятность Р = — = = — = —.

N Г1 330 66

с5

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >