Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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
), 
   точности k человек получат свои шляпы. Рассмотреть все значения k ( k
   = 0, 1, 2, 3, 4 ).
                                                                  3 1 1      1
      Ответ: Имеем 9, 8, 6, 0, 1 случаев с вероятностями           , , , 0,
                                                                  8 3 4     24
соответственно..
                                                       m
      Замечание. Вероятность равна числу Р(А) =          , где n – общее число
                                                       n
комбинаций, т - число "благоприятных" комбинаций.


                   2.3 Формула включений и исключений

        Пусть имеется N предметов и п свойств a 1, a 2, … , an . Каждый из рас-
сматриваемых предметов может обладать одним или несколькими из этих
n свойств. Обозначим через N(ai1, ai2, … , ais) число предметов, обладаю-
щих свойствами ai1, ai2, … , ais (и, быть может, некоторыми другими), а че-
рез N( a 1, a 2,…, a n) - число предметов, не обладающих свойствами a i1, ai2,…,
ais.
        Например, N(a1, a3 , a 4) – число предметов, обладающих свойствами
a1, a3 , но не обладающих свойством a4.
        Справедлива формула
        N( a 1 , a 2,…, a n ) = N – N(a1) – N(a2) – …– N(an ) + N(a1 , a2)+
        +N(a 1 , a3) +…+ N(a1 , an) +…+ N(an-1 , a n) – N(a1 , a2 , a3 ) –…– (9)
          – N(an-2 ,an-1 , an) +…+ (-1)n N(a1, a2 , … , an ).
        Формула (9) нaзывaeтcя формулой включений и исключений. Здесь
слагаемые включают все комбинации свойств a 1,a2,…,an без учёта их по-
рядка; знак “+” ставится, если число учитываемых свойств чётно, и знак
         “ - “ , если это число нечётно.

        Пример 14. В результате опроса 70 студентов выяснилось, что 45 из
них занимаются спортом, 29 — музыкой, 9 — и спортом и музыкой.
Сколько студентов из числа опрошенных не занимаются ни спортом, ни
музыкой.
        Решение. Чтобы применить формулу (9), обозначим через a 1(a2)-
свойство студента, состоящее в том, что он занимается спортом (музыкой).
Тогда имеем N=70, N(a1)=45, N(a2)=29, N(a1,a2)=9. Нужно найти число
N( a 1, a 2 ). По формуле (9) получаем
            N( a 1 , a 2)=N – N(a1) – N(a2)+N(a 1,a2)=70 – 45 – 29 + 9 = 5.
      Предположим теперь, что число N(a1,a2,...,an ) зависит не от самых
этих свойств, а лишь от их числа.
      Введём следующие обозначения : N(0) = N, N(1) = N(a1 ) =…= N(an),

Страницы