Дискретная математика. Азарнова Т.В - 34 стр.

                                                               34
Комбинаторика


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

      В основе решения многих комбинаторных задач лежит так называемая
формула включений и исключений.
      Пусть Χ 1 , Χ 2 ,..., Χ n - подмножества некоторого множества Χ , тогда
число элементов в объединении множеств
 Χ 1 ∪ Χ 2 ∪ ... ∪ Χ n = Χ 1 + Χ 2 +... + Χ n −
− Χ 1 ∩ Χ 2 − Χ 1 ∩ Χ 3 −... − Χ n −1 ∩ Χ n +
+ Χ 1 ∩ Χ 2 ∩ Χ 3 +... + Χ n −2 ∩ Χ n −1 ∩ Χ n +
+... +(−1) Χ 1 ∩ Χ 2 ∩ ... ∩ Χ n ,
                n +1

число элементов в множестве Χ , не принадлежащих объединению множеств
Χ 1 , Χ 2 ,..., Χ n
 Χ \ (Χ 1 ∪ Χ 2 ∪ ... ∪ Χ n ) = Χ − Χ 1 − Χ 2 −... − Χ n +
+ Χ 1 ∩ Χ 2 + Χ 1 ∩ Χ 3 +... + Χ n −1 ∩ Χ n −
− Χ 1 ∩ Χ 2 ∩ Χ 3 −... − Χ n−2 ∩ Χ n −1 ∩ Χ n −
+... +(−1)n Χ 1 ∩ Χ 2 ∩ ... ∩ Χ n .
         Эти формулы носят название формул включений и исключений.
         Приведем наиболее часто используемую интерпретацию данных
формул. Пусть Χ - конечное множество, состоящее из Ν элементов,
α1 , α 2 ,..., α n - некоторые свойства, которыми могут обладать или не обладать
элементы                из       Χ.         Введем ∀i ∈{1,2,..., n}   множество
Χ i ={x ∈Χ : x −обладает свойством α i }. Обозначим для любого набора
(i1 , i2 ,..., ik )                                    (                     )
                       k =1,2,..., n через Ν α i1 , α i2 ,..., α ik = Χ i1 ∩ Χ i2 ∩ ... ∩ Χ ik - число
элементов в множестве Χ , обладающих одновременно свойствами
α i1 , α i2 ,..., α ik . Тогда, в соответствии с приведенными выше формулами
включений и исключений, число элементов Ν 0 в множестве Χ , не
обладающих ни одним из свойств α1 , α 2 ,..., α n , равно
                                  Ν 0 =Ν −Ζ 1 +Ζ 2 −... +(−1)n Ζ n ,
где
                              Ζk =        ∑ Ν (α i ,..., α i
                                                           1        k
                                                                        ),       k =1,2,..., n.
                                     1≤i1 ≤...≤ik ≤n


     Задача 1. В студенческой группе 30 человек. Из них 15 человек знают
английский язык, 10 - французский, 6 - немецкий, 5 - английский и
французский, 3 - английский и немецкий, 3 - французский и немецкий, 2 -
английский, французский и немецкий. Сколько человек в данной группе не
знают ни одного языка?