Изменения

 == Формула включения-исключения =={{Определение|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>

Равенство справедливо, потому что все наборы <texdpi = "130"> I \in 2^N </tex> можно разбить на две группы :

# <texdpi = "130"> I \in 2^{N'} </tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс <texdpi = "130"> n </tex>, а будут все различные варианты индексов остальных множеств, т.е. <texdpi = "130"> I \in 2^{N'}</tex>.# <texdpi = "130">\{n\} \cup I</tex>, где <texdpi = "130">I \in N'</tex> Аналогично предыдущему, только в наборе будет индекс <texdpi = "130"> n </tex>.

Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и <texdpi = "130">|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> .Таким образом, для <texdpi = "130">~l=n</tex> мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.

== Беспорядок Беспорядки ==

|definition='''БеспорядкомБеспорядок''' (Disturbance)англ. ''Derangement'' называется ) — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.

<tex dpi = "130">|A_i|statement=Количество беспорядков порядка (n - 1)!</tex>n, так как <tex dpi = "130">i</tex> или [http:-ая позиция занята числом <tex dpi = "130">i<//rutex>.wikipedia.org<tex dpi = "130">\binom{n}{1}</wiki/Субфакториал субфакториалом] числа tex> — количество способов выбрать одну <texdpi = "130">ni</tex> (обозначение: !-ую позицию <texdpi = "130">\Rightarrow \sum \limits_{i = 1}^{n} |A_i| = \binom{n}{1} (n-1)!</tex>) вычисляется по формуле: [[Файл:Formula.png]]

Рассмотрим <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}|proof</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"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! </tex> Количество всех способов выбрать <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> равно <tex dpi = "130">\binom{n}{k} </tex>. Таким образом получаем, что:  <tex dpi = "130">\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>.}}

1) [[Файл{{Утверждение|statement = Количество беспорядков удовлетворяет рекурсивным соотношениям:Formula2.png]]

2и <tex dpi = "140"> d(n) [[Файл:Formula3.png]]=n \times d(n-1)+(-1)^{n} </tex>,

Данные формулы эквивалентны. Действительно, если некоторое множество где <mathtex dpi = "140">Sd(1)=0 </mathtex> является подмножеством некоторого множества , а <texdpi = "140">Ud(2)=1 </tex>, то, в силу законов де Моргана|proof =1) Докажем второе соотношение:

Так как <texdpi = "140">|</tex> <math>S</math> <tex>|d(n)=!n </tex> , то можно переписать эту формулу, как <texdpi = "140">!n=n!(n-1)+(-1)^{n} </tex> <tex>|</tex> <tex>U</tex> <tex>|</tex> — <tex>|</tex> <math>\lnot</math><math>S</math> <tex>|</tex>.

Где По формуле субфакториала <texdpi = "140">U</tex> — универсальное множество. <tex>|U| !n=n!(\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!} + \frac {(-1)^{n}}{n!})= n!</tex>, т.е. количество перестановок из <tex>\sum \limits_{k = 0}^{n</tex> элементов. <math>-1} \lnot</math><math>S</math> означает дополняющее множество до <tex>U</tex>. Откуда следует, что <math>frac {(-1)^{k}}{k!}+(-1)^{n}=n \lnot</math><tex>A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>times !(n-1)+(-ый элемент стоит не на своём <tex>i1)^{n}</tex>-ом месте.

У нас есть <tex>|A_i| = (n - 1)!</tex> (тчисел и столько же мест.кМы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером. <tex>i</tex>-ая позиция занята числом <tex>i</tex>). Суммирование ведется по всем <tex>i</tex> <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |A_i| = </tex> <math>\binom{n}{1}</math><tex> (n-1)!</tex>

Предположим, что первое число оказалось на месте с номером <tex> |A_{i1} \bigcap A_{i2} \bigcap ... \bigcap A_{ik}| = (n - k)! i </tex>, где . Это можно сделать <tex> n-1\le i1 < i2 < ... < ik \le n </tex>способами, так как первое число может оказаться на любом месте, кроме первого. Так как позиции Теперь есть 2 варианта, зависящие от того, окажется ли число с номером <tex>i1, i2, ... , ik i </tex> заняты соответствующими числамина первом месте или нет.

* Число <tex>\sum \limits_{1\le i1 < i2 i < /tex> на первом месте... Остается < ik \le tex> n}^{} |A_{i1} \bigcap A_{i2} \bigcap ... \bigcap A_{ik}| = -2 </tex> мест и <mathtex>\binom{n}{k}-2 </mathtex>чисел. То есть количество беспорядков от <tex>\cdot(n-k)!2 </tex>* Число <tex> i </tex>, т.кне может оказаться на первом месте. количество способов выбрать Это эквивалентно решению задачи с <tex>kn-1 </tex> позиций местами и <tex> n-1 </tex>i1числами (первое число уже заняло место, i2, ... , ik а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером <tex> i </tex> равно запрещенным будет первое место). Получается количество беспорядков от <mathtex>\binom{n}{k}-1 </mathtex>. Подставляя соответствующие значения мощностей множеств в формулу фключения-исключения, получаем:

Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число <tex>| \bigcap_{i=_1}^n \lnot A_i |</tex> занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и <tex>=i </tex> -го чисел. Во втором же случае число с номером <tex>n!</tex> <tex>+i </tex> <tex>\sum \limits_{i = 1}^{n} (-1)^{n}(n попасть на первое место не может, а значит займет какое- k)!</tex><tex>\cdot</tex><math>\binom{n}{k}</math> то другое место, и распределение остальных чисел уже будет другое.

Раскрывая <math>\binom{n}{k}</math> по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка <tex>n</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> Проведя несложные комбинаторные вычисления, получим: <tex> 2 \times 9!+2 \times 9! - 2 \times 2 \times 8! </tex> Отнимая это число от общего числа перестановок <tex> 10! </tex>, получим ответ. == Задача о нахождении числа взаимно простых четвёрок ==  Дано <tex> n </tex> чисел: <tex> a_1, a_2,..., a_n </tex>. Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.  Посчитаем число "плохих" четвёрок, то есть таких, в которых все числа делятся на число <tex> d > 1 </tex>. Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на <tex> d </tex> (но, возможно, делящихся и на больший делитель). <tex> answer=\sum \limits_{d>1} (-1)^{deg(d)-1} \times f(d) </tex>, где <tex> deg(d) </tex> — это количество простых в факторизации числа <tex> d </tex>, <tex> f(d) </tex> — количество четвёрок, делящихся на <tex> d </tex>. Чтобы посчитать функцию <tex> f(d) </tex>, надо просто посчитать количество чисел, кратных <tex> d </tex>, и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку. Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д. == См. также ==* [[Производящая функция]]* [[Лемма Бёрнсайда и Теорема Пойа]] ==Примечания== <references />== Источники информации ==