Файл: Дискретная математика.pdf

5.2 Комбинаторика и теоретико-вероятностные задачи

91

Подчеркнем, что если несколько событий независимы попарно, то отсюда еще

не следует их независимость в совокупности. В этом смысле требование независи-
мости событий в совокупности сильнее требования их попарной независимости.

Поясним сказанное на примере.

. . . . . . . . . . . . . . . . . . . . . .

Пример 5.1

. . . . . . . . . . . . . . . . . . . . .

Пусть в урне имеется 4 шара, окрашенные: один — в красный цвет (A), один —

в синий цвет (B), один — в черный цвет (C) и один — во все эти три цвета (ABC).
Чему равна вероятность того, что извлеченный из урны шар имеет красный
цвет?

Так как из четырех шаров два имеют красный цвет, то P

(A) = 2/4 = 1/2. Рас-

суждая аналогично, найдем P

(B) = 1/2, P(C) = 1/2. Допустим теперь, что взятый

шар имеет синий цвет, т. е. событие B уже произошло. Изменится ли вероятность
того, что извлеченный шар имеет красный цвет, т. е. изменится ли вероятность
события A? Из двух шаров, имеющих синий цвет, один шар имеет и красный
цвет, поэтому вероятность события A по-прежнему равна 1

/2. Другими словами,

условная вероятность события A, вычисленная в предположении, что наступило
событие B, равна его безусловной вероятности. Следовательно, события A и B
независимы. Аналогично придем к выводу, что события A и C, B и C независимы.
Итак, события A, B и C попарно независимы.

Независимы ли эти события в совокупности? Оказывается, нет. Действитель-

но, пусть извлеченный шар имеет два цвета, например синий и черный. Чему
равна вероятность того, что этот шар имеет и красный цвет? Лишь один шар окра-
шен во все три цвета, поэтому взятый шар имеет и красный цвет. Таким образом,
допустив, что события B и C произошли, приходим к выводу, что событие A обяза-
тельно наступит. Следовательно, это событие достоверное и вероятность его равна
единице. Другими словами, условная вероятность P

BC

(A) = 1 события A не равна

его безусловной вероятности P

(A) = 1/2. Итак, попарно независимые события A,

B, C не являются независимыми в совокупности.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Приведем теперь следствие из теоремы умножения.
Следствие. Вероятность совместного появления нескольких событий, незави-

симых в совокупности, равна произведению вероятностей этих событий:

P

(A

1

A

2

. . .A

n

) = P(A

1

)P(A

2

)...P(A

n

).

Доказательство. Рассмотрим три события: A, B и C. Совмещение событий A,

B и C равносильно совмещению событий AB и C, поэтому

P

(ABC) = P(AB ⋅ C).

Так как события A, B и C независимы в совокупности, то независимы, в частно-

сти, события AB и C, а также A и B. По теореме умножения для двух независимых
событий имеем:

P

(AB ⋅ C) = P(AB)P(C) и P(AB) = P(A)P(B).

92

Глава 5. Комбинаторика

Итак, окончательно получим

P

(ABC) = P(A)P(B)P(C).

Для произвольного n доказательство проводится методом математической ин-

дукции.

Замечание. Если события A

1

, A

2

, . . ., A

n

независимы в совокупности, то и про-

тивоположные им события A

1

, A

2

, . . ., A

n

также независимы в совокупности.

Пусть в результате испытания могут появиться n событий, независимых в со-

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bepoятнocть пoявлeния xoтя бы oднoгo из coбытий A

1

, A

2

, . . ., A

n

,

нeзaвиcимыx в coвoкyпнocти, paвнa paзнocти мeждy eдини-
цeй и пpoизвeдeниeм вepoятнocтeй пpoтивoпoлoжныx coбытий
A

1

, A

2

, . . ., A

n

:

P

(A) = 1 − q

1

q

2

. . .q

n

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Доказательство. Обозначим через A событие, состоящее в появлении хотя бы

одного из событий A

1

, A

2

, . . ., A

n

. События A и A

1

A

2

. . .A

n

(ни одно из событий не на-

ступило) противоположны, следовательно, сумма их вероятностей равна единице:

P

(A) + P(A

1

A

2

. . .A

n

) = 1.

Отсюда, пользуясь теоремой умножения, получим

P

(A) = 1 − P(A

1

A

2

. . .A

n

) = 1 − P(A

1

)P(A

2

)...P(A

n

)

или

P

(A) = 1 − q

1

q

2

. . .q

n

.

Частный случай. Ecли coбытия A

1

, A

2

, . . ., A

n

имeют oдинaкoвyю вepoятнocть,

paвнyю p, тo вepoятнocть пoявлeния xoтя бы oднoгo из этиx coбытий

P

(A) = l − q

n

.

Противоположные события.
Противоположными называют два единственно возможных события, образу-

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Сумма вероятностей противоположных событий равна единице:

P

(A) + P(A) = 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Контрольные вопросы по главе 5

93

Доказательство базируется на том, что противоположные события образуют

полную группу, а сумма вероятностей событий, образующих полную группу, равна
единице (см. Теорему о полной группе событий).

Замечание 1. Если вероятность одного из двух противоположных событий обо-

значена через p, то вероятность другого события обозначают через q. Таким обра-
зом, в силу предыдущей теоремы p + q

= 1.

Замечание 2. При решении задач на отыскание вероятности события A часто

выгодно сначала вычислить вероятность противоположного события, а затем найти
искомую вероятность по формуле P

(A) = 1 − P(A).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Контрольные вопросы по главе 5

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Определение и формула перестановок.

2. Определение и формула размещений.

3. Определение и формула размещений с повторениями.

4. Определение и формула сочетаний.

5. Студенту необходимо сдать 3 экзамена (хвоста) за 7 дней. Сколькими спо-

собами это можно сделать, при условии, что в один день сдается 1 экзамен?

6. В группе студентов 9 студенток и 8 студентов. Для проведения вечера необ-

ходимо выбрать пару ведущих. Сколько вариантов выбора существует?

7. Телефонный номер состоит из пяти цифр. Найти вероятность того, что:

а) все цифры различны;

б) все цифры нечетные.

ЗАКЛЮЧЕНИЕ

В данном учебном пособии изложены основные понятия теории множеств,

теории графов, комбинаторики и переключательных функций. Основные вопросы
теории изложены в доступной и наглядной форме, что способствует более лёг-
кому их восприятию. Материал пособия также содержит примеры типовых задач
и алгоритмы их решения. В данном учебном пособии материал изложен по блоч-
ному принципу. Это позволяет объект изучения рассматривать как единое целое
относительно ряда характеристик.

Таким образом, учебное пособие позволит студентам приобрести определён-

ные навыки и умения практического профессионального применения методов тео-
рии графов и комбинаторики, ориентированные на компьютерные технологии.

ЛИТЕРАТУРА

Основная литература

[1] Хаггарти Род. Дискретная математика для программистов : учеб. пособие

для вузов : пер. с англ. / Род. Хаггарти. — 2-е изд., доп. — М. : Техносфера,
2005. — 393 с.

[2] Макоха А. Н. Дискретная математика : учеб. пособие для вузов / А. Н. Мако-

ха. — М. : Физматлит, 2005. — 368 с.

[3] Шапорев С. Д. Математическая логика. Курс лекций и практических заня-

тий : учеб. пособие для вузов / С. Д. Шапорев. — БХВ-Петербург, 2005. —
410 с.

[4] Новиков Ф. А. Дискретная математика для программистов : учеб. пособие

для вузов / Ф. А. Новиков. — 2-е изд. — СПб. ; М. ; Нижний Новгород : Питер,
2007. — 363 [5] с. : ил.

Дополнительная литература

[5] Яблонский С. В. Введение в дискретную математику : учеб. пособие для

вузов / С. В. Яблонский. — 4-е изд. — М. : Высшая школа, 2002. — 384 с.

[6] Оре Ойстин. Теория графов / О. Оре ; пер. с англ. И. Н. Врублевской ; ред.

пер. Н. Н. Воробьев. — 2-е изд., стереотип. — М. : Наука, 1980. — 336 с.

[7] Костюкова Н. И. Графы и их применение. Комбинаторные алгоритмы

для программистов : учеб. пособие / Н. И. Костюкова. — М. : Интернет-
Университет Информационных Технологий, 2007 ; М. : БИНОМ. Лабора-
тория знаний, 2007. — 310 с.

[8] Гаврилов Г. П. Сборник задач по дискретной математике : учеб. пособие для

вузов / Г. П. Гаврилов, А. А. Сапоженко. — М. : Наука, 1977. — 368 с.