П.2. Правило суммы

Обозначение. Пусть A - конечное множество. Обозначим | A | - число элементов в множестве A (мощность множества A). Полагаем |Æ| = 0.

Пусть A, B - конечные множества. | A | = | B | тогда и только тогда, когда существует биекция f: A ® B.

Пусть A, B - конечные множества. Тогда число элементов в множестве равно

| A È B | = | A | + | B | - | A Ç B |. (1)

Действительно, | A |+| B | - число элементов в множествах A и B, при этом общие элементы множеств A и B, т.е. элементы множества A Ç B, подсчитывались дважды. Поэтому справедлива формула (1).

Пусть A, B - подмножества конечного множества . Из (1) следует, что число элементов не принадлежащих множеству равно

. (2)

Из (1) следует, что для любых конечных множеств A, B, C число элементов в множестве равно

| A È B È C | = | A | + | B | + | C | - | A Ç B | - | A Ç C | -| B Ç C | + | A Ç B Ç C |. (3)

Действительно, применяя несколько раз (1) получаем, что

| A È B È C | = |(A È B)È C | = | A È B | + | C | - |(A È B)Ç C | = | A È B | + | C | -

- |(A Ç C) È(B Ç C)| =

= | A | + | B | - | A Ç B | + | C | - |(A Ç C)| - | B Ç C)| + | (A Ç B)Ç (B Ç C)|.

Пусть A, B, C - подмножества конечного множества . Из (1) следует, что число элементов не принадлежащих множеству равно

. (4)

Аналогичным образом проверяется справедливость следующей теоремы.

Теорема 1. Пусть A ,..., A - подмножества конечного множества . Справедливы утверждения:

i) Число элементов в множестве равно

, (5)

где суммирование ведётся по всем кортежам N таким, что

.

ii) Число элементов не принадлежащих множеству равно

, (6)

где суммирование ведётся по всем кортежам N таким, что

. n

Равенства(1) - (6) называются формулами включения-исключения.

Следствие 1. Пусть A ,..., A - конечные множества такие, что

A Ç A =Æ для всех i ¹ j. Тогда

| A È...È A | = | A | +...+ | A |. n (7)

Обычно равенство (7) называют правилом суммы.