Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 41 стр.

UptoLike

точности k человек получат свои шляпы. Рассмотреть все значения k ( k
= 0, 1, 2, 3, 4 ).
Ответ : Имеем 9, 8, 6, 0, 1 случаев с вероятностями
24
1
,0,
4
1
,
3
1
,
8
3
соответственно..
Замечание. Вероятность равна числу Р(А ) =
n
m
, где n общее число
комбинаций, т - число "благоприятных " комбинаций.
2.3 Формула включений и исключений
Пусть имеется N предметов и п свойств a
1
, a
2
, , a
n
. Каждый из рас-
сматриваемых предметов может обладать одним или несколькими из этих
n свойств. Обозначим через N(a
i1
, a
i2
, , a
is
) число предметов, обладаю-
щих свойствами a
i1
, a
i2
, , a
is
(и, быть может , некоторыми другими), а че-
рез N(
a
1
,
a
2
, ,
a
n
) - число предметов, не обладающих свойствами a
i1
, a
i2
, ,
a
is
.
Например, N(a
1
, a
3
,
a
4
) число предметов, обладающих свойствами
a
1
, a
3
, но не обладающих свойством a
4.
Справедлива формула
N( a
1
,a
2
, , a
n
) = N N(a
1
) N(a
2
) …– N(a
n
) + N(a
1
, a
2
)+
+N(a
1
, a
3
) + + N(a
1
, a
n
) + + N(a
n-1
, a
n
) N(a
1
, a
2
, a
3
) …– (9)
N(a
n-2
,a
n-1
, a
n
) + + (-1)
n
N(a
1
, a
2
, , a
n
).
Формула (9) н aзыв aeт cя формулой включений и исключений. Здесь
слагаемые включают все комбинации свойств a
1
,a
2
, ,a
n
без учёта их по -
рядка ; знак + ставится, если число учитываемых свойств чётно, и знак
- , если это число нечётно.
Пример 14. В результате опроса 70 студентов выяснилось, что 45 из
них занимаются спортом , 29 музыкой, 9 и спортом и музыкой.
Сколько студентов из числа опрошенных не занимаются ни спортом, ни
музыкой.
Решение. Чтобы применить формулу (9), обозначим через a
1
(a
2
)-
свойство студента, состоящее в том, что он занимается спортом (музыкой).
Тогда имеем N=70, N(a
1
)=45, N(a
2
)=29, N(a
1
,a
2
)=9. Нужно найти число
N( a
1
,a
2
). По формуле (9) получаем
N( a
1
, a
2
)=N N(a
1
) N(a
2
)+N(a
1
,a
2
)=70 45 29 + 9 = 5.
Предположим теперь , что число N(a
1
,a
2
,...,a
n
) зависит не от самых
этих свойств, а лишь от их числа .
Введём следующие обозначения : N
(0)
= N, N
(1)
= N(a
1
) == N(a
n
),