Изменения

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

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

<texdpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</tex>

В силу того, что в сумме <texdpi = "140">| A | + | B |</tex> элементы пересечения <texdpi = "140">A \cap B</tex> учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.

Для случая с большим количеством рассматриваемых множеств <texdpi = "140"> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

|statement=Пусть <texdpi = "140"> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения{{---}}исключения: <center> <texdpi = "140"> | A | = \sum \limits_{I \in 2^N-1} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex> </center>Причем <texdpi = "140"> N = \{ 1,2, \ldots ,n \} </tex>. Здесь за <texdpi = "140"> 2^N - 1 </tex> обозначим множество всех непустых подмножеств <texdpi = "140"> N </tex>.

Рассмотрим некоторый элемент <texdpi = "140"> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <texdpi = "140"> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <texdpi = "140"> x </tex> в правую часть формулы.

<texdpi = "140">k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} + (-1) {t \choose 0} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} </tex><texdpi = "140"> = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} </tex>

Докажем, что <texdpi = "140"> \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0</tex>

В силу того, что <texdpi = "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>, имеем <texdpi = "140"> 0 = (1 + (-1)) ^ t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, то равенство доказано.

Таким образом, <texdpi = "140"> k = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j = 1 - 0 = 1</tex>, то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана.

Пусть <texdpi = "130">~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <texdpi = "130">~l=1</tex> равенство обращается в тривиальное (<texdpi = "130"> |A| = |A_1| </tex> {{---}} истинно). Для случая <texdpi = "130"x>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <texdpi = "130">~l=2</tex> {{---}} база индукции.

Предположим, что для <texdpi = "130">~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <texdpi = "130">~l=n</tex>

Пусть <texdpi = "130"> A </tex> {{---}} объединение <texdpi = "130">~n</tex> множеств. Очевидно, что <texdpi = "130"> A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n </tex>. Пусть <texdpi = "130"> B = \bigcup \limits_{i=1}^{n-1}A_i </tex>; <texdpi = "130">N' = \{ 1,2, \ldots ,n-1 \} </tex>.

<texdpi = "130"> | B | = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex>

Кроме того, так как формула верна для <texdpi = "130">~l=2</tex> (из базы индукции), то верно равенство <texdpi = "130"> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>. Найдем <tex>~| B \cap A_n |</tex>:

Очевидно, что Найдем <texdpi = "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> (**) </tex> имеемОчевидно, что <texdpi = "130"> | B \cap A_n| = \sum left( \bigcup \limits_{I \in 2i=1}^{N'}} (n-1)^{|I|+1} A_i \left| \bigcap \limits_{ j \in I} \left( A_j right) \cap A_n \right) \right| = \sum bigcup \limits_{I \in 2i=1}^{N'}} (n-1)^{|I|+1} \left| ( A_i \bigcap \limits_{ j\in I \cup \{ n \} } A_j cap A_n \right| ) (**)</tex>

Подставим полученные значения в Опираясь на предположение индукции и равенство <texdpi = "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>:

Подставим полученные значения в <texdpi = "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> <texdpi = "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)

Докажем, что <texdpi = "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> <texdpi = "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>. Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и <tex dpi = "130">|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> .Таким образом, для <tex dpi = "130">~l=n</tex> мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.}} == Беспорядки =={{Определение|id=идентификатор (необязательно), пример: def1. |definition='''Беспорядок''' (англ. ''Derangement'') — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте. }} === Явная формула с использованием принципа включения-исключения ==={{Теорема|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> числа <tex>n</tex> (обозначение: <tex>!n</tex>) и вычисляется по формуле:

Равенство справедливо, потому что все наборы <texdpi = "150"> I !n = n! - \in frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + \frac{n!}{n!}(-1)^N {n}= \sum_{k=0}^n\frac{n!}{k!}(-1)^{k} </tex> можно разбить |proof=Воспользуемся принципом включения-исключения: обозначим за <tex dpi = "130">A_i</tex> — количество перестановок из <tex dpi = "130">n</tex> элементов, в каждой из которых <tex dpi = "130">i</tex>-ый элемент стоит на две группы своём месте. Тогда по формуле включения-исключения имеем: <tex dpi = "140"> \Big |\bigcap_{i=_1}^n \overline{A}_i \Big| = |U|-\sum \limits_{i} |A_i|+\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}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>, где универсум <tex dpi = "130">U</tex> — множество из всех перестановок порядка <tex dpi = "130">n</tex>.

# <tex> I \in 2^overline{N'A} _i</tex> Это означает— количество перестановок, что в наборе точно '''не''' будет присутствовать индекс каждой из которых <tex> n i</tex>, а будут все различные варианты индексов остальных множеств, т.е. <tex> I \in 2^{N'}</tex>.# <tex>\{n\} \cup I</tex>, где <tex>I \in N'</tex> Аналогично предыдущему, только в наборе будет индекс -ый элемент стоит не на своём <tex> n i</tex>-ом месте.

Как видно Таким образом <tex dpi = "130">| \bigcap_{i=_1}^n \overline {A}_i |</tex> — количество всех перестановок, в каждой из равенства, первое и третье слагаемое которых <tex>i</tex>-ый элемент <tex dpi = "130">\neq</tex> <tex dpi = "отвечают130" за вторую группу>i</tex>, а второе слагаемое за первую группуто есть количество искомых беспорядков. Значит, равенство истинно и  <texdpi = "130">|AA_i| = (n - 1)!</tex>, так как <tex dpi = "130">i</tex>-ая позиция занята числом <tex dpi = "130">i</tex>. <tex dpi = "130">\binom{n}{1}</tex> — количество способов выбрать одну <tex dpi = "130">i</tex>-ую позицию <tex dpi = "130"> \Rightarrow \sum \limits_{I i = 1}^{n} |A_i| = \in 2^Nbinom{n}{1} (n-1)^!</tex> Рассмотрим <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}|I</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"> |+1A_{i_1} \left| bigcap A_{i_2} \bigcap ... \limits_bigcap A_{ j i_k}| = (n - k)! </tex> Количество всех способов выбрать <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> равно <tex dpi = "130">\in I binom{n}{k} A_j \right| </tex> .Таким образомполучаем, для что:  <texdpi = "130">~l\sum \limits_{1\leqslant i_1 < i_2 < ... < i_k \leqslant n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| =\binom{n}{k} \cdot(n-k)! </tex> мы доказали Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, что равенство вернополучаем: <tex dpi = "130">| \bigcap_{i=_1}^n \overline{A}_i | = n! + \sum \limits_{k = 1}^{n} (-1)^{k}\binom{n}{k} \cdot (n - k)!. Значит</tex>  Раскрывая <tex dpi = "140">\binom{n}{k}</tex> по общеизвестной формуле, индукционный переход веренполучим требуемое выражение, то есть теорема доказанаколичество беспорядков порядка <tex dpi = "130">n</tex>.

== = Рекурретное соотношение для нахождения количества беспорядков === {{Утверждение|statement = Количество беспорядков удовлетворяет рекурсивным соотношениям: <tex dpi = "140"> d(n)=(n-1)[d(n-1)+d(n-2)] </tex> и <tex dpi = "140"> d(n)=n \times d(n-1)+(-1)^{n} </tex>, где <tex dpi ="140"> d(1)=0 </tex>, а <tex dpi = "140"> d(2)=1 </tex>|proof =Попробуем решить следующую задачу1) Докажем второе соотношение: количество перестановок чисел от  Так как <tex dpi = "140"> d(n)=!n </tex>, то можно переписать эту формулу, как <tex dpi = "140"> !n=n!(n-1)+(-1)^{n} </tex> По формуле субфакториала <tex dpi = "140"> !n=n!(\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!} + \frac {(-1)^{n}}{n!})=n!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}+(-1)^{n}=n \times !(n-1)+(-1 до )^{n}</tex> 2) Докажем первое соотношение: У нас есть <tex> n</tex> чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, при которых что ни один элемент одно из чисел не стоит оказалось на своём местес таким же номером. Каждая такая перестановка в комбинаторике называется '''беспорядком''' Предположим, что первое число оказалось на месте с номером <tex> i </tex>. Это можно сделать <tex> n-1 </tex> способами, так как первое число может оказаться на любом месте, кроме первого. Теперь есть 2 варианта, зависящие от того, окажется ли число с номером <tex> i </tex> на первом месте или нет. Количество всех * Число <tex> 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-1 </tex>. Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число <tex> i </tex> занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и <tex> i </tex>-го чисел. Во втором же случае число с номером <tex> i </tex> попасть на первое место не может, а значит займет какое-исключения то другое место, и дается выражениемраспределение остальных чисел уже будет другое. В итоге получается необходимая формула. }} == Задача о перестановках == Сколько есть перестановок чисел от <tex> 0 </tex> до <tex> 9 </tex> таких, что первый элемент больше <tex> 1 </tex>, а последний меньше <tex> 8 </tex>? Посчитаем количество "плохих" перестановок, то есть таких, у которых первый элемент <tex> \leqslant 1 </tex> (множество таких перестановок обозначим <tex> X </tex>) и/или последний <tex> \leqslant 8 </tex> (множество таких перестановок обозначим <tex> Y </tex>). Тогда количество "плохих" перестановок по формуле включений-исключений равно: <tex> |X|+|Y|-|X \cap Y| </tex>

[[ФайлПроведя несложные комбинаторные вычисления, получим:Formula.png]]

которое называется субфакториалом числа n и обозначается, как <tex> 2 \times 9!n.+2 \times 9! - 2 \times 2 \times 8! </tex>

1) [[ФайлДано <tex> n </tex> чисел:Formula2<tex> a_1, a_2,..., a_n </tex>. Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.png]]

2Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на <tex> d </tex> (но, возможно, делящихся и на больший делитель) [[Файл:Formula3.png]]

Данные формулы эквивалентны! Действительно<tex> answer=\sum \limits_{d>1} (-1)^{deg(d)-1} \times f(d) </tex>, если множества [[Файл:Formula4.png]] являются подмножествами некоторого множества [[Файл:Formula5.png]], то в силу правил де Моргана [[Файл:Formula6.png]].

В нашей задаче множество [[Файл:Formula5.png]] - есть где <tex> deg(d) </tex> — это количество перестановок из n элементов, т.е. n!. Черта над множеством [[Файл:Formula4.png]] означает дополняющее множество до [[Файл:Formula5.png]] или, простых в силу определения [[Файл:Formula4.png]]факторизации числа <tex> d </tex>, означает <tex> f(d) </tex> — количество перестановокчетвёрок, где делящихся на i-ой позиции '''НЕ''' i<tex> d </tex>.

Таким образом величина в левой части формулы 2Чтобы посчитать функцию <tex> f(d) - есть </tex>, надо просто посчитать количество перестановокчисел, где на 1-ой позици '''НЕ''' 1кратных <tex> d </tex>, на 2-ой позици '''НЕ''' 2 и тс помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку.д. Т.е. количество искомых беспорядков! Осталось определить величины в правой части:

[[Файл:Formula5Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д.png]] = <tex>n!</tex>

|[[Файл:Formula4.png]]| можно получить зафиксировав число i на соответствующей ей позиции i, а остальные позиции заполнив как угодно остальными числами => |[[Файл:Formula4= См.png]]| также = <tex>(n - 1)!</tex>. Суммирование ведется по всем i => * [[Файл:Formula8.pngПроизводящая функция]]Аналогичными рассуждениями получаем, что сумма пересечений некоторых k множеств - есть все перестановки при зафиксированных k позициях, т.е. * [[Файл:Formula7.pngЛемма Бёрнсайда и Теорема Пойа]] х <tex>(n - k)!</tex>. Таким образом приходим к формуле:

[[Файл:Formula9.png]] = <tex>n!</tex> + [[Файл:Formula10.png]] х [[Файл:Formula7.png]] х <tex>(n - k)!</tex>=Примечания==

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