Изменения

Перейти к: навигация, поиск

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

497 байт добавлено, 02:37, 17 декабря 2011
Нет описания правки
||proof=
Доказываем теорему Приведем два разноплановых доказательства Теоремы. '''I. Комбинаторное доказательство Теоремы.''' Рассмотрим некоторый элемент <tex> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <tex> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <tex> x </tex> в правую часть формулы.   '''II. Доказательство Теоремы по индукции.'''
Пусть <tex>~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex>~l=1</tex> равенство обращается в тривиальное (<tex> |A| = |A_1| </tex> {{---}} истинно). Для случая <tex>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <tex>~l=2</tex> {{---}} база индукции.
Анонимный участник

Навигация