Срочно! 100 баллов!Формула Включений-Исключений для любого n с подробным доказательством! Очень надо!
Ответы
Ответ: Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре[1]. Например, в случае двух множеств {\displaystyle A,B}A,B формула включений-исключений имеет вид: |A\cup B|=|A|+|B|-|A\cap B|.}|A\cup B|=|A|+|B|-|A\cap B|
Відповідь:Например, в случае двух множеств формула включений-исключений имеет вид:В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.|A u B|=|A|+|B|-|A u B|
Покрокове пояснення:Существует несколько доказательств формулы включений-исключений.Доказательство по индукцииФормулу включений-исключений можно доказать по индукции .При формула включений-исключений тривиальна:Пусть формула верна для .Пусть каждый элемент множества :Теперь применим формулу для свойств :Наконец, применим формулу для одного свойства :Комбинируя выписанные три формулы, получим формулу включений-исключений для . Что и требовалось доказать. ■Комбинаторное доказательствоРассмотрим произвольный элемент .Если элемент ).Пусть элемент в правую часть равенПри числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равнаТаким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств . Что и требовалось доказать. ■Доказательство через индикаторные функцииПусть ).Индикаторная функция их дополнений равнаа индикаторная функция пересечения дополнений:Раскрывая скобки в правой части и еще раз используя тот факт, что индикаторная функция пересечения множеств равна произведению их индикаторных функций, получаем:Это соотношение — одна из форм принципа включений-исключений. Оно выражает собой логическое тождество и верно для произвольных множеств его мощность равнаполучим формулировку принципа включений-исключений в терминах мощностей множеств (или в терминах свойств).