§ 6. Метод включения и исключения
Этот метод применяется к важной задаче разбиения множеств на подмножества в зависимости от того, обладают ли их элементы определенной совокупностью свойств или нет.
Пусть дано n-множество S некоторых элементов и m - множество свойств p1, p2,...,pm, которыми элементы множества S могут как обладать, так и не обладать. Выделим какую – либо r выборку свойств (pi1, pi2 ,..., pir). Число элементов s∈S, каждый из которых обладает всеми r свойствами, обозначим через n(pi1, pi2,..., pir). Отсутствие у элементов какого – либо свойства, например pi, будем обозначать через $\overline{p_i}$. Таким образом, число элементов, обладающих, скажем, свойствами p1, p3, p5 и не обладающих свойствами p2, p4, p6, запишется как n(p1,$\overline{p_2}$, p3,$\overline{p_4}$, p5,$\overline{p_6}$ ).
Сначала рассмотрим два простых случая.
Сначала рассмотрим два простых случая. 1. Имеется только одно свойство, например, p. Тогда очевидно, что $n(\overline{p})=n-n(p)$
2. Имеется конечное число несовместимых друг с другом свойств p1, p2,...,pm (например, быть сферическими, кубическими, коническими и т.п.). Снова очевидно, что $n(\overline{p_1},\overline{p_2}, ... ,\overline{p_m})=n-\sum{n(p_i)}$
Перейдем теперь к общему случаю, когда элементы множества S обладают комбинациями совместимых свойств.
Теорема 4.2. Пусть даны n - множество элементов и множество свойств pi (1≤ i ≤ m), совместимых между собой. Тогда число элементов, не обладающих ни одним из этих свойств p1, p2, ... , pm, равно:
$n(\overline{p_1},\overline{p_2},...,\overline{p_m}) = n-\sum{n(p_i)} + \sum_{i<j}n(p_i,p_j)-$ $\sum_{i<j<k} n(p_i,p_j,p_k) + ... + (-1)^m n(p_1,p_2,...,p_m$
Доказательство. Чтобы получить число элементов, не обладающих ни одним из указанных свойств, необходимо из n - множества исключить подмножество элементов, обладающих свойством p1, затем обладающих свойством p2 и т.д., т.е. ∑ n(pi) элементов. Однако при этом элементы, имеющие два свойства, скажем p1 и p2, оказались исключёнными дважды как обладающие свойством p1, затем как обладающие свойством p2. Значит, надо возвратить все множества, элементы которых обладают двумя свойствами, т.е. прибавить $\sum_{n(p_i,p_j)}$ элементов. Но при этом элементы, обладающие тремя свойствами, скажем, pi, pj и pk , оказались включенными дважды, следовательно, надо вычесть $\sum_{n(p_i,p_j,p_k)}$. Рассуждая далее аналогичным образом, получим алгоритм для вычисления $n(\overline{p_1},\overline{p_2}, ... ,\overline{p_m})$, состоящий в попеременном отбрасывании и возвращении подмножеств. Этому и обязано название метода: метод включения и исключения.
Эту теорему можно доказать следующим образом. Пусть B - подмножество (В⊆S) элементов, не обладающих ни одним из свойств $p_1,p_2,...,p_m$ А= S\B. Следовательно, B∩A = ∅ и S=A∪В. Тогда
$n(S) = n = n(B) + n(A)$
$n(B) = n(\overline{p_1},\overline{p_2},...,\overline{p_m}) = n – n(A)$
Подмножество A состоит из элементов множества S, обладающих некоторыми (возможно, всеми) свойствами p1, p2,..., pm. Пусть A1 подмножество из A всех тех элементов, которые обладают свойством p1 (и может быть какими – то другими свойствами), A2 - подмножества из A всех тех элементов, которые обладают свойством p2 (и может быть какими – то другими свойствами) и т.д. Тогда имеем:
$A = A_1 ∪ A_2 ∪ ...∪ A_m$
следовательно, получим:
$n(\overline{p_1},\overline{p_2}, ... ,\overline{p_m}) = n - n(A_1 ∪ A_2 ∪ ...∪ A_m) $
и по формуле (4.3) - требуемое равенство (4.7).
Рассмотрим пример. Даны числа 1,2,...,100. Требуется выяснить, сколько среди них чисел, которые не делятся ни на одно из чисел 2,3,5.
Положим:
- p1 - свойство чисел делиться на 2;
- p2 - свойство чисел делиться на 3;
- p3 - свойство чисел делиться на 5;
- p1 p2 - будет означать, что число делится на 6;
- p1 p2 - будет означать, что число делится на 10;
- p2 p3 - будет означать, что число делится на 15;
- p1 p2 p3 - будет означать, что число делится на 30.
Тогда легко получить, что:
$n(\overline{p_1},\overline{p_2},\overline{p_3}) = 100-n(p_1)-n(p_2)-n(p_3)+n(p_1,p_2)+n(p_1,p_3)+n(p_2,p_3)-+n(p_1,p_2,p_3)=100-50-33-20+16+10+6-3=26$
Рассмотрим второй пример. При обследовании установили:
60% студентов читают журналы типа А;
50% студентов читают журналы типа В;
50% студентов читают журналы типа С;
А и В читают 30% студентов;
А и С читают 40% студентов;
В и С читают 20% студентов;
все три типа журналов читают 10% студентов.
Сколько процентов студентов не читают вообще эти журналы? Легко получить, что:
$n(\overline{A},\overline{B},\overline{C})=100 – (60 + 50 + 50) + (30 + 40 + 20) – 10 = 20$%
Усложнение метода связано с введением весов элементов.
Пусть для каждого элемента s∈S приписано неотрицательное число (вес) υ(s). Рассмотрим вновь n-множество S некоторых элементов и m - множество свойств p1, p2,...,pm, которыми элементы множества S могут, как обладать, так и не обладать. Возьмем r – выборку свойств (pi1 ,..., pir) и обозначим сумму весов элементов, обладающих всеми r выбранными свойствами через υ(pi1 ,..., pir), а сумму, распространенную на все возможные r - выборки свойств, обозначим через υ(r):
υ(r) = ∑ υ(pi1, ..., pir).
Введем дополнительно, что υ(0 ) = ∑ υ(si).
Теорема 4.3. Если даны n - множество S, каждый элемент si которого имеет вес υ(si), и m - множество свойств, то сумма υm(0) весов элементов, не удовлетворяющих ни одному из заданных свойств, определится по формуле:
$υm(0) = υ(0) - υ(1) + υ(2) - ... + (-1)m υ(m). $
Доказательство. Всякий элемент $s_i∈S$, если он имеет $r > 0 (r ≤ m)$свойств, вносит свой вес $υ(s_i)$ в первое слагаемое один раз, во второе r раз, в третье $C_r^2$ раз и т.д., в r-е $C_r^r$ раз, а, начиная с r +1-го, нуль раз. Всего элемент $s_i$ вносит свой вес
$C_r^0 - C_r^1- C_r^2 - ... + (-1)^r C_r^r = \sum_{k=0}^{r}(-1)^k C_r^k$
раз, а это выражение равно нулю.
Таким образом, чтобы получить искомую сумму весов, надо:
- взять сумму весов всех элементов множества;
- из полученной суммы вычесть сумму весов элементов, обладающих хотя бы одним свойством;
- возвратить (прибавить) сумму весов элементов, имеющих не менее двух свойств и т.д.
Обобщением предыдущей теоремы является следующая.
Теорема 4.4. Сумма весов элементов n – множества S, удовлетворяющих r - выборке из m - множества свойств p1, p2,..., pm находится по формуле
$v_m(r)=v(r)-C_{r+1}^1 v(r+1) + C_{r+2}^2 v(r+2) - ... (-1)^{m-r}v(m)$
Без доказательства.