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

UptoLike

Составители: 

42
41. Сколько существует вариантов того, что три человека, сдавшие
свои шляпы в гардероб, не получат в точности свою шляпу?
Ответ:
2
=
N
.
42. Четыре человека сдают свои шляпы в гардероб. Предполагая, что
шляпы возвращаются наугад, найти число случаев и вероятность того, что
в точности k человек получат свои шляпы. Рассмотреть все значения
k (k = 0, 1, 2, 3, 4 ).
Ответ: Имеем 9, 8, 6, 0, 1 случаев с вероятностями
3111
,,,0,
83424
соответственно.
Замечание. Вероятность равна числу Р(А) =
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
–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
)
свойство студента, состоящее в том, что он занимается спортом (музыкой).