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

Пусть A и B  произвольные множества. Тогда мощность их объединения может быть определена по формуле:

|A  B| = |A| + |B| |A  B|. (1)

Если рассмотреть объединение трех множеств A, B и С, то справедлива следующая формула:

|ABС|=|A|+|B|+|С||AB||AC||BC|+|ABC|. (2)

Справедливость каждой их приведенных формул легко может быть проверена с помощью диаграмм Венна для произвольных двух и трех множеств. Для этого достаточно посчитать, сколько раз учитывается в правой и левой части каждого равенства всякий элемент объединения.

Применение приведенных формул при решении конкретных задач может быть оправдано, если нахождение каждого значения в правой части соответствующей формулы проще нахождения всего значения ее левой части.

Считается, что в общем случае объединения множеств устроены сложнее, чем пересечения множеств. Например, множество ABС в общем случае может рассматриваться как более разнородное, чем каждое из входящих в него множеств A, B и С, поскольку содержать элементы обладающие и не обладающие свойствами элементов множеств A, B и С, в разных комбинациях, в которых достаточно выполнимости лишь одного из свойств элементов этих множеств.

Действительно, в A  B  С могут содержаться элементы, обладающие только свойством элементов множества A. Там же могут содержаться элементы не из A, но обладающие свойствами элементов множеств B или C.

Множества, мощности которых используются в правых частях формул (1) и (2), образованы пересечениями отдельных множеств и поэтому более однородны, поскольку все их элементы обладают одним и тем же свойством, представляемым конъюнкцией свойств элементов множеств входящих в пересечение.

Приведенные формулы (1) и (2) могут быть обобщены на случай объединения произвольного конечного числа множеств так, чтобы свести задачу нахождения мощности объединения множеств к серии задач, связанных с нахождением мощностей нескольких пересечений множеств.

Пусть заданы конечные множества A₁ , ... , A_k и такое число i, что 0  i  k. Обозначим как n_i сумму мощностей всех возможных пересечений по i таких множеств.

Заметим, что n_i является суммой слагаемых, так как существует ровно столько различных пересечений по i множеств из k.

ТЕОРЕМА 2.1

| A_i | = n₁ + ... + (1)^i-1n_i + ... + (1)^k-1n_k. (1)

Доказательство

Пусть a  это произвольный элемент, входящий в A_i .

Покажем, что в левой и правой частях равенства (1) этот элемент множества A учитывается ровно один раз.

Для левой части (1) очевидно, что это так.

Рассмотрим правую часть доказываемого равенства. Предположим, что a содержится в r разных множествах из множеств A₁, ... , A_k. Тогда:

- в n₁ элемент a учтен раз;

- в n₂ элемент a учтен раз;

. . .

- в n_r элемент a учтен раз.

В последующих слагаемых правой части (1) элемент a не учитывается ни разу.

Поэтому в выражении:

n₁ +... + (1)^i1 n_i + ...+(1)^k1n_k

элемент a учтен ровно

+ ... + (1)^i1 + ... + (1)^r1 раз.

Докажем равенство:

+ ... + (1)^i1 + ... + (1)^r1 = 1. (2)

Перенесем все члены этого равенства в правую часть и с учетом того, что = 1, получим:

0 =  + ... + (1)ⁱ + ... + (1)^r . (3)

Воспользуемся формулой бинома Ньютона:

(1  x)^r =  x+... + (1)ⁱ xⁱ +...+(1)^r x^r.

Очевидно, что формула (3) - частный случай бинома Ньютона для x = 1.

Значит, равенство (2) является справедливым. Поэтому элемент a учитывается в правой части формулы (1) ровно один раз.

Доказательство окончено.

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