Учебное пособие: Дискретная математика
86
Глава 5. Комбинаторика
5.2 Комбинаторика и теоретико-вероятностные
задачи
Наблюдаемые нами события (явления) можно подразделить на следующие три
вида: достоверные, невозможные и случайные.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Достоверным называют событие, которое обязательно произой-
дет, если будет осуществлена определенная совокупность усло-
вий T. Например, если в сосуде содержится вода при нормальном
атмосферном давлении и температуре ниже 0
°, то событие «вода
в сосуде находится в твёрдом состоянии» есть достоверное. В этом
примере заданные атмосферное давление и температура воды со-
ставляют совокупность условий T.
Невозможным называют событие, которое заведомо не произой-
дет, если будет осуществлена совокупность условий T. Например,
событие «вода в сосуде находится в жидком состоянии» заведомо
не произойдет, если будет осуществлена совокупность условий T
предыдущего примера.
Случайным называют событие, которое при осуществлении сово-
купности условий T может либо произойти, либо не произойти.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Например, если брошена монета, то она может упасть так, что сверху будет
либо герб, либо надпись. Поэтому событие «при бросании монеты выпал «герб» —
случайное. Каждое случайное событие, в частности выпадение «герба», есть след-
ствие действия очень многих случайных причин (это — сила, с которой брошена
монета, форма монеты и другие). Невозможно учесть влияние на результат всех
этих причин, поскольку число их очень велико и законы их действия неизвест-
ны. Теория вероятностей не ставит перед собой задачу предсказать, произойдет
единичное событие или нет, — она просто не в силах это сделать. Иначе обстоит
дело, если рассматриваются случайные события, которые могут многократно на-
блюдаться при осуществлении одних и тех же условий T. Установлено, что доста-
точно большое число однородных случайных событий независимо от их конкрет-
ной природы подчиняется определенным закономерностям, а именно вероятност-
ным закономерностям. Установлением этих закономерностей и занимается теория
вероятностей.
При решении задач комбинаторики используют следующие правила.
Правило суммы.
Суммой A + B двух событий A и B называют событие, состоящее в появлении
события A, или события B, или обоих этих событий.
Если некоторый объект A может быть выбран из совокупности объектов m спо-
собами, а другой объект B может быть выбран n способами, то выбрать либо A,
либо B можно m + n способами.
5.2 Комбинаторика и теоретико-вероятностные задачи
87
Например, если из орудия произведены два выстрела и A — попадание при пер-
вом выстреле, B — попадание при втором выстреле, то A + B — попадание при пер-
вом выстреле, или при втором, или в обоих выстрелах.
Если два события A и B — несовместные, то A + B — событие, состоящее в по-
явлении одного из этих событий, безразлично какого.
Суммой нескольких событий называют событие, которое состоит в появлении
хотя бы одного из этих событий. Например, событие A + B + C состоит в появлении
одного из следующих событий: A, B, C, A и B, A и C, B и C, A и B и C.
Пусть события A и B — несовместные, причем вероятности этих событий из-
вестны. Как найти вероятность того, что наступит либо событие A, либо собы-
тие B? Ответ на этот вопрос дает теорема сложения.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вероятность появления одного из двух несовместных событий,
безразлично какого, равна сумме вероятностей этих событий:
P
(A + B) = P(A) + P(B).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Доказательство. Пусть n — общее число возможных элементарных исходов ис-
пытания; m
1
— число исходов, благоприятствующих событию A; m
2
— число исхо-
дов, благоприятствующих событию B.
Число элементарных исходов, благоприятствующих наступлению либо собы-
тия A, либо события B, равно m
1
+ m
2
. Следовательно,
P
(A + B) = (
m
1
+
m
2
)
n
=
m
1
n
+
m
2
n
.
Так как m
1
/n = P(A) и m
2
/n = P(B), то получим P(A + B) = P(A) + P(B).
Следствие. Вероятность появления одного из нескольких попарно несовмест-
ных событий, безразлично какого, равна сумме вероятностей этих событий:
P
(A
1
+
A
2
+
. . . + A
n
) = P(A
1
) + P(A
2
) + ... + P(A
n
).
Доказательство. Рассмотрим три события: A, B и C. Так как рассматриваемые
события попарно несовместны, то появление одного из трех событий, A, B и C,
равносильно наступлению одного из двух событий, A + B и C, поэтому в силу
указанной теоремы
P
(A + B + C) = P[(A + B) + C] = P(A + B) + P(C) = P(A) + P(B) + P(C).
Для произвольного числа попарно несовместных событий доказательство про-
водится методом математической индукции.
Полная группа событий.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Сумма вероятностей событий A
1
, A
2
, . . ., A
n
, образующих полную
группу, равна единице: P
(A
1
) + P(A
2
) + ... + P(A
n
) = 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
Глава 5. Комбинаторика
Доказательство. Так как появление одного из событий полной группы досто-
верно, а вероятность достоверного события равна единице, то
P
(A
1
+
A
2
+
. . . + A
n
) = 1.
(5.1)
Любые два события полной группы несовместны, поэтому можно применить
теорему сложения:
P
(A
1
+
A
2
+
. . . + A
n
) = P(A
1
) + P(A
2
) + ... + P(A
n
).
(5.2)
Сравнивая (5.1) и (5.2), получим
P
(A
1
) + P(A
2
) + ... + P(A
n
) = 1.
Правило произведения.
Если объект A можно выбрать из совокупности объектов m способами и по-
сле каждого такого выбора объект B можно выбрать n способами, то пара объек-
тов
(A,B) в указанном порядке может быть выбрана mn способами.
Произведение событий. Произведением двух событий A и B называют собы-
тие AB, состоящее в совместном появлении (совмещении) этих событий. Напри-
мер, если A — деталь годная, B — деталь окрашенная, то AB — деталь годна и окра-
шена.
Произведением нескольких событий называют событие, состоящее в совмест-
ном появлении всех этих событий. Например, если A, B, C — появление «герба»
соответственно в первом, втором и третьем бросаниях монеты, то ABC — выпаде-
ние «герба» во всех трех испытаниях.
Условная вероятность. Во введении случайное событие определено как со-
бытие, которое при осуществлении совокупности условий S может произойти или
не произойти. Если при вычислении вероятности события никаких других огра-
ничений, кроме условий S, не налагается, то такую вероятность называют без-
условной; если же налагаются и другие дополнительные условия, то вероятность
события называют условной. Например, часто вычисляют вероятность события B
при дополнительном условии, что произошло событие A. Заметим, что и безуслов-
ная вероятность, строго говоря, является условной, поскольку предполагается осу-
ществление условий S.
Условной вероятностью P
A
(B) называют вероятность события B, вычислен-
ную в предположении, что событие A уже наступило.
Исходя из классического определения вероятности, формулу P
A
(B) = P(AB)/P(A)
(P(A) > 0) можно доказать. Это обстоятельство и служит основанием для следую-
щего общего (применимого не только для классической вероятности) определения.
Условная вероятность события B при условии, что событие A уже наступило,
по определению, равна
P
A
(B) = P(AB)/P(A) (P(A) > 0).
Рассмотрим два события: A и B. Пусть вероятности P
(A) и P
A
(B) известны. Как
найти вероятность совмещения этих событий, т. е. вероятность того, что появится
и событие A и событие B? Ответ на этот вопрос дает теорема умножения.
5.2 Комбинаторика и теоретико-вероятностные задачи
89
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вероятность совместного появления двух событий равна произве-
дению вероятности одного из них на условную вероятность дру-
гого, вычисленную в предположении, что первое событие уже на-
ступило:
P
(AB) = P(A)P
A
(B).
(5.3)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Доказательство. По определению условной вероятности,
P
A
(B) = P(AB)/P(A).
Отсюда
P
(AB) = P(A)P
A
(B).
Замечание. Применив формулу (5.3) к событию BA, получим
P
(BA) = P(B)P
B
(A),
или, поскольку событие BA не отличается от события AB,
P
(AB) = P(B)P
B
(A).
(5.4)
Сравнивая формулы (5.3) и (5.4), заключаем о справедливости равенства
P
(A)P
A
(B) = P(B)P
B
(A).
(5.5)
Следствие. Вероятность совместного появления нескольких событий равна
произведению вероятности одного из них на условные вероятности всех осталь-
ных, причем вероятность каждого последующего события вычисляется в предпо-
ложении, что все предыдущие события уже появились:
P
(A
1
A
2
A
3
. . .A
n
) = P(A
1
)P
A
1
(A
2
)P
A
1
A
2
(A
3
)...P
A
1
A
2
. . .A
n−1
(A
n
),
где P
A
1
A
2
. . .A
n−1
(A
n
) является вероятностью события A
n
, вычисленной в предположе-
нии, что события A
1
, A
2
, . . ., A
n
−1
наступили. В частности, для трех событий
P
(ABC) = P(A)P
A
(B)P
AB
(C).
Заметим, что порядок, в котором расположены события, может быть выбран
любым, т. е. безразлично какое событие считать первым, вторым и т. д.
Пусть вероятность события B не зависит от появления события A.
Событие B называют независимым от события A, если появление события A
не изменяет вероятности события B, т. е. если условная вероятность события B
равна его безусловной вероятности:
P
A
(B) = P(B).
(5.6)
Подставив (5.6) в соотношение (5.5) предыдущего параграфа, получим
P
(A)P(B) = P(B)P
B
(A).
90
Глава 5. Комбинаторика
Отсюда
P
B
(A) = P(A),
т. е. условная вероятность события A в предположении что наступило событие B,
равна его безусловной вероятности. Другими словами, событие A не зависит от
события B.
Итак, если событие B не зависит от события A, то событие A не зависит от
события B; это означает, что свойство независимости событий взаимно.
Для независимых событий теорема умножения P
(AB) = P(A)P
A
(B) имеет вид
P
(AB) = P(A)P(B),
(5.7)
т. е. вероятность совместного появления двух независимых событий равна произ-
ведению вероятностей этих событий.
Равенство (5.7) принимают в качестве определения независимых событий.
Два события называют независимыми, если вероятность их совмещения равна
произведению вероятностей этих событий; в противном случае события называют
зависимыми.
На практике о независимости событий заключают по смыслу задачи. Напри-
мер, вероятности поражения цели каждым из двух орудий не зависят от того, по-
разило ли цель другое орудие, поэтому события «первое орудие поразило цель»
и «второе орудие поразило цель» независимы.
Замечание 1. Если события A и B независимы, то независимы также события
A и B, A и B, A и B.
Действительно, A
= AB + AB.
Следовательно,
P
(A) = P(AB) + P(AB) или P(A) = P(AB) + P(A)P(B).
Отсюда
P
(AB) = P(A)[1 − P(B)] или P(AB) = P(A)P(B),
т. е. события A и B независимы.
Независимость событий A и B, A и B является следствием доказанного утвер-
ждения.
Несколько событий называют попарно независимыми, если каждые два из них
независимы. Например, события A, B, C попарно независимы, если независимы
события A и B, A и C, B и C.
Для того чтобы обобщить теорему умножения на несколько событий, введем
понятие независимости событий в совокупности.
Несколько событий называют независимыми в совокупности (или просто неза-
висимыми), если независимы каждые два из них и независимы каждое событие
и все возможные произведения остальных. Например, если события A
1
, A
2
, A
3
,
независимы в совокупности, то независимы события A
1
и A
2
, A
1
и A
3
, A
2
и A
3
; A
1
и A
2
A
3
, A
2
и A
1
A
3
, A
3
и A
1
A
2
. Из сказанного следует, что если события независимы
в совокупности, то условная вероятность появления любого события из них, вы-
численная в предположении, что наступили какие-либо другие события из числа
остальных, равна его безусловной вероятности.