Изменения

{{Определение|definition='''Формула включения-исключения''' (англ. ''Inclusion-exclusion principle'') {{-- это -}} комбинаторная формула, которая позволяет определить выражающая мощность объединения конечных множеств, если известны их через мощности всех множеств и мощности всех их возможных пересечений.}}

[[Файл:пересечение двух множеств.svg.png|thumb|right|случай Случай для двух множеств]]

Например, в случае Для случая из двух множеств <mathtex dpi = "140">~A, B</mathtex> формула включения-исключения имеет следующий вид:

<mathtex dpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</mathtex>

В силу того, что в сумме <mathtex dpi = "140">~| A | + | B |</mathtex> элементы пересечения <mathtex dpi = "140">A \cap B</mathtex> учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.  Для случая с большим количеством рассматриваемых множеств <tex dpi = "140"> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и чтобы компенсировать это мы вычитаем исключений ошибочно включенного. Отсюда и происходит название формулы.  Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.  {{Теорема |statement=Пусть <tex dpi = "140"> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <mathtex dpi = "140"> | A | = \sum \limits_{I \in 2^N -1} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex> </center>Причем <tex dpi = "140"> N = \{ 1,2, \ldots ,n \cap B } </tex>. Здесь за <tex dpi = "140"> 2^N - 1 </tex> обозначим множество всех непустых подмножеств <tex dpi = "140"> N </tex>.  ||proof=Приведем два разноплановых доказательства теоремы. '''I. Комбинаторное доказательство теоремы.''' Рассмотрим некоторый элемент <tex dpi = "140"> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <tex dpi = "140"> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <tex dpi = "140"> x </tex> в правую часть формулы. <tex dpi = "140">k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} </tex><tex dpi = "140"> = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} </tex> Докажем, что <tex dpi = "140"> \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0</mathtex> В силу того, что <tex dpi = "140"> из (1 + (-1)) ^ t = {t \choose 0} 1^t (-1)^0 + {t \choose 1} 1 ^ {t - 1} (-1) ^ 1 + \ldots + {t \choose t} 1^0 (-1)^t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, имеем <tex dpi = "140"> 0 = (1 + (-1)) ^ t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, то равенство доказано. Таким образом, <tex dpi = "140"> k = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j = 1 - 0 = 1</tex>, то есть каждый элемент подсчитан в правой части формулыровно один раз, то теорема доказана. '''II. Доказательство теоремы по индукции.''' Пусть <tex dpi = "130">~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex dpi = "130">~l=1</tex> равенство обращается в тривиальное (<tex dpi = "130"> |A| = |A_1| </tex> {{---}} истинно). Для случая <tex dpi = "130"x>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <tex dpi = "130">~l=2</tex> {{---}} база индукции.  Предположим, что для <tex dpi = "130">~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex dpi = "130">~l=n</tex>   Пусть <tex dpi = "130"> A </tex> {{---}} объединение <tex dpi = "130">~n</tex> множеств. Очевидно, что <tex dpi = "130"> A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n </tex>. Пусть <tex dpi = "130"> B = \bigcup \limits_{i=1}^{n-1}A_i </tex>; <tex dpi = "130">N' = \{ 1,2, \ldots ,n-1 \} </tex>. Справедливость этого рассуждения видна   Исходя из диаграммы Эйлерапредположения индукции, имеем, что <tex dpi = "130"> | B | = \sum \limits_{I \in 2^{N'}} (-Венна 1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex>  Кроме того, так как формула верна для двух <tex dpi = "130">~l=2</tex> (из базы индукции), то верно равенство <tex dpi = "130"> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>.   Найдем <tex dpi = "130">~| B \cap A_n |</tex>:  Очевидно, что <tex dpi = "130"> B \cap A_n = \left( \bigcup \limits_{i=1}^{n-1}A_i \right) \cap A_n = \bigcup \limits_{i=1}^{n-1} \left( A_i \cap A_n \right) (**)</tex>  Опираясь на предположение индукции и равенство <tex dpi = "130"> (**) </tex> имеем, что <tex dpi = "130"> |B \cap A_n| = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} \left( A_j \cap A_n \right) \right| = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| </tex>  Подставим полученные значения в <tex dpi = "130">(*)</tex>:  <tex dpi = "130"> | A | = | A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| \right) - \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right)</tex> <tex dpi = "130"> =| A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| \right) + \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+2} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right) </tex>  Докажем, что <tex dpi = "130"> | A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| \right) + \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+2} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right) </tex> <tex dpi = "130"> = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> Равенство справедливо, потому что все наборы <tex dpi = "130"> I \in 2^N </tex> можно разбить на две группы : # <tex dpi = "130"> I \in 2^{N'} </tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс <tex dpi = "130"> n </tex>, а будут все различные варианты индексов остальных множеств, приведенной на рисунке справат.е. <tex dpi = "130"> I \in 2^{N'}</tex>.# <tex dpi = "130">\{n\} \cup I</tex>, где <tex dpi = "130">I \in N'</tex> Аналогично предыдущему, только в наборе будет индекс <tex dpi = "130"> n </tex>.

Таким же образом Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и в случае <math>~ntex dpi = "130">|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </mathtex> множеств процесс нахождения количества элементов объединения .Таким образом, для <mathtex dpi = "130">A_1 \cup A_2 \cup \ldots \cup A_n~l=n</mathtex> состоит во включении всегомы доказали, затем исключении лишнегочто равенство верно. Значит, затем включении ошибочно исключенного и так далееиндукционный переход верен, то есть в попеременном включении и исключении. Отсюда и происходит название формулытеорема доказана.}}

== Теорема Беспорядки ==Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:Определение<center><math> | A | id= \sum_{I=идентификатор (i_1,i_2, \ldots ,i_kнеобязательно) \subset \{ 1,2, \ldots ,n \} } пример: def1. |definition='''Беспорядок''' (-1англ. ''Derangement'')^{k+— это перестановка чисел от <tex>1} \Big| \bigcap_{ j \in I } A_j \Big| </mathtex>до <tex>n</centertex>, в которой ни один элемент не стоит на своём месте. }}

== Доказательство =Явная формула с использованием принципа включения-исключения ==={{Теорема|id=идентификатор (необязательно), пример: th1. Для случая |statement= Количество беспорядков порядка <tex>n</tex> равно субфакториалу <ref>[http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B1%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB Википедия {{---}} Субфакториал]</ref> числа <mathtex>~n=1</mathtex> и (обозначение: <mathtex>~!n=2</mathtex> теорема, очевидно, верна. ) и вычисляется по формуле:

Теперь рассмотрим <mathtex dpi = "150">~!n = n! - \frac{n>!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + \frac{n!}{n!}(-1)^{n}= \sum_{k=0}^n\frac{n!}{k!}(-1)^{k} </mathtex>|proof=Воспользуемся принципом включения-исключения:обозначим за <tex dpi = "130">A_i</tex> — количество перестановок из <tex dpi = "130">n</tex> элементов, в каждой из которых <tex dpi = "130">i<center/tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем: <mathtex dpi = "140"> A = \bigcup_Big |\bigcap_{i=1_1}^n \overline{nA}A_i _i \Big| = |U|-\Bigg( sum \underbrace limits_{i} |A_i|+\bigcup_sum \limits_{i< j} |A_i\bigcap A_j|-\sum \limits_{i < j < k} |A_i\bigcap A_j\bigcap A_k|</tex> <tex dpi ="130">+ ... +(-1})^{n-1}A_i}_{B} | A_1 \bigcap A_2 \Bigg) bigcap ... \cup bigcap A_n | </tex>, где универсум <tex dpi = "130">U</tex> — множество из всех перестановок порядка <tex dpi = "130">n</mathtex>.

Таким образом <mathtex dpi = "130"> | B | = \sum_bigcap_{I \subset \{ 1,2, \ldots ,i=_1}^n-1 \} } (-1)^overline {|I|+1A} \Big_i | </tex> — количество всех перестановок, в каждой из которых <tex>i</tex>-ый элемент <tex dpi = "130">\bigcap_{ j \in I } A_j \Big| neq</tex> <tex dpi = "130">i</mathtex>,то есть количество искомых беспорядков.

Рассмотрим <mathtex dpi = "130"> | A A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| </tex>, где <tex dpi = "130"> 1\leqslant i_1 < i_2 < ... < i_k \leqslant n </tex>. Так как некоторые <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> заняты соответствующими числами, то количество способов расставить остальные <tex dpi = "130">n-k</tex> чисел равно <tex dpi = "130">(n-k)!</tex>. То есть <tex dpi = "130"> | B | + | A_n A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - | B k)! </tex> Количество всех способов выбрать <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> равно <tex dpi = "130">\cap A_n |binom{n}{k} </mathtex>. Таким образом получаем, что:

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1}^{nПодставляя соответствующие значения мощностей множеств в формулу включения-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>исключения, получаем:

Раскрывая <mathtex dpi = "140"> = \sum_binom{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1k} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1</tex> по общеизвестной формуле,2получим требуемое выражение, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ то есть количество беспорядков порядка <tex dpi = "130">n \} } A_j \Big| </mathtex>.</center>}}

<center>{{УтверждениеТаким образом|statement = Количество беспорядков удовлетворяет рекурсивным соотношениям:</center>

<center>и <mathtex dpi = "140"> | A | = | A_n| + \Biggd( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j =n \in I } A_j \Big| \Bigg) - \Biggtimes d( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1n} \Big| \bigcap_{ j \in I } A_j \Big| </math></centertex>,

где <tex dpi == Теорема ==Пусть <math"140"> A d(1)= \bigcup_{i=1}^{n}A_i 0 </mathtex> , тогда по формуле включения-исключения:а <centertex dpi = "140"><math> | A | = \sum_{I=d(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+=1} \Big| \bigcap_{ j \in I } A_j \Big| </mathtex></center>|proof =1) Докажем второе соотношение:

Так как <tex dpi == Доказательство ==Для случая <math"140">~d(n)=1!n </mathtex> и , то можно переписать эту формулу, как <mathtex dpi = "140">~!n=2n!(n-1)+(-1)^{n} </mathtex> теорема, очевидно, верна.

Теперь рассмотрим По формуле субфакториала <mathtex dpi = "140">~!n>2</math>:<center><math> A = n!(\bigcup_sum \limits_{ik =10}^{n-1}A_i = \Biggfrac {( -1)^{k}}{k!} + \underbrace frac {(-1)^{n}}{n!})=n!\bigcup_sum \limits_{ik =10}^{n-1}A_i\frac {(-1)^{k}}_{Bk!} +(-1)^{n}=n \Biggtimes !(n-1) \cup A_n +(-1)^{n}</mathtex>

У нас есть <mathtex> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </mathtex>чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером.

* Число <mathtex> | A | = | B | + | A_n | i </tex> на первом месте. Остается <tex> n-2 </tex> мест и <tex> n-2 </tex> чисел. То есть количество беспорядков от <tex> n-2 </tex>* Число <tex> i </tex> не может оказаться на первом месте. Это эквивалентно решению задачи с <tex> n-1 </tex> местами и <tex> n-1 </tex> числами (первое число уже заняло место, а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером <tex> i </tex> запрещенным будет первое место). Получается количество беспорядков от <tex> n- | B \cap A_n |1 </mathtex>.

<math> \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup_{i=1В итоге получается необходимая формула. }^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>

Сколько есть перестановок чисел от <mathtex> = \sum_{I \subset \{ 10 </tex> до <tex> 9 </tex> таких,2, \ldots ,n-что первый элемент больше <tex> 1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2</tex>, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| а последний меньше </mathtex>8 </centertex>?

<center>Таким образомТогда количество "плохих" перестановок по формуле включений-исключений равно:</center>

<center><math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1Проведя несложные комбинаторные вычисления,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) - \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math></center>получим:

== Теорема ==Пусть <mathtex> A = 2 \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:<center><math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,times 9!+2, \ldots ,n \} } (times 9! -1)^{k+1} 2 \Big| times 2 \bigcap_{ j \in I } A_j \Big| </math>times 8! </centertex>

== Доказательство ==Для случая Отнимая это число от общего числа перестановок <mathtex>~n=110! </mathtex> и <math>~n=2</math> теорема, очевидно, вернаполучим ответ.

Теперь рассмотрим <math>~n>2</math>:<center><math> A = \bigcup_{i=1}^{n}A_i Задача о нахождении числа взаимно простых четвёрок = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>

Посчитаем число "плохих" четвёрок, то есть таких, в которых все числа делятся на число <mathtex> d > | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| </mathtex>.

<mathtex> | A | answer= | B | + | A_n | \sum \limits_{d>1} (-1)^{deg(d)- | B 1} \cap A_n |times f(d) </mathtex>,

Чтобы посчитать функцию <mathtex> \Big| B \bigcap A_n \Big| = \Bigg| \Biggf( \bigcup_{i=1}^{n-1}A_i \Biggd) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </mathtex>, надо просто посчитать количество чисел, кратных <tex> d </tex>, и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку.

<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>См. также ==* [[Производящая функция]]</center>* [[Лемма Бёрнсайда и Теорема Пойа]]

<centerreferences />Таким образом== Источники информации ==* [[wikipedia:ru:Беспорядок_(перестановка)|Википедия — Беспорядок]] <* [http:/center> /en.wikipedia.org/wiki/Derangement Wikipedia — Derangement]* Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика, Изд. 4-е, исправленное - МЦНМО, 2013 ISBN 978-5-4439-0052-0* Р. Стенли, Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.