пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

15.Метод включень і виключень

 

http://img.pslan.com/uploads/be59e442475f8c2a6bdfa305a1f2498a.jpg

 

 

be59e442475f8c2a6bdfa305a1f2498a.jpg

 

Формулу включений-исключений можно доказать по индукции [1][5].

При ~n=1 формула включений-исключений тривиальна:

N(overline{a}) = N - N(a)

Пусть формула верна для ~n=m, докажем ее для ~n=m+1.

Пусть каждый элемент множества ~U может обладать или не обладать любым из свойств ~a_1, ldots, a_m, a_{m+1}. Применим формулу включений-исключений для свойств ~a_1, ldots , a_m:

N(overline{a}_1 ldots overline{a}_m) = N - sum_{i leq m} N(a_i) + sum_{i < j leq m} N(a_i a_j) + ldots + (-1)^m N(a_1 ldots a_m)

Теперь применим формулу для свойств ~a_1, ldots , a_m к множеству ~N(a_{m+1}) объектов, для которых выполнено свойство ~a_{m+1}:

N(overline{a}_1 ldots overline{a}_m a_{m+1}) = N(a_{m+1}) - sum_{i leq m} N(a_i a_{m+1}) + sum_{i < j leq m} N(a_i a_j a_{m+1}) + ldots + (-1)^m N(a_1 ldots a_m a_{m+1})

Наконец, применим формулу для одного свойства ~a_{m+1} к совокупности N(overline{a}_1 ldots overline{a}_m), объектов, которые не обладают свойствами a_1, ldots , a_m:

N(overline{a}_1 ldots overline{a}_m overline{a}_{m+1}) = N(overline{a}_1 ldots overline{a}_m) - N(overline{a}_1 ldots overline{a}_m a_{m+1})

Комбинируя выписанные три формулы, получим формулу включений-исключений для ~m+1 свойств a_1, ldots , a_{m+1}. Что и требовалось доказать.

Комбинаторное доказательство

Рассмотрим произвольный элемент ~e in U и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений

Если элемент ~e не обладает ни одним из свойств ~a_i, то в правой части формулы он учитывается ровно 1 раз (в члене ~N).

Пусть элемент ~e обладает в точности ~r свойствами, скажем ~a_{j_1}, ldots , a_{j_r}. Он дает по 1 в тех слагаемых суммы sumnolimits_{i_1 < ldots < i_s} N(a_{i_1}, ldots , a_{i_s}), для которых { i_1, ldots , i_s} есть подмножество { j_1, ldots , j_r}, и 0 для остальных. Число таких подмножеств по определению есть число сочетаний r choose s. Следовательно, вклад элемента ~e в правую часть равен

1 - {r choose 1} + {r choose 2} - ldots + (-1)^n {r choose n}

При ~s > r числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

sum_{s=0}^{r} (-1)^s {r choose s} = bigg (1 + (- 1) bigg )^r = 0

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств ~a_i, то есть N(overline{a}_1 ldots overline{a}_n). Что и требовалось доказать.

 


хиты: 197
рейтинг:0
Точные науки
математика
дискретная геометрия
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь