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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 75: Строка 75:
 
}}
 
}}
  
== Количество беспорядков ==
+
== Беспорядки ==
Попробуем решить следующую задачу: количество перестановок чисел от 1 до n, при которых ни один элемент не стоит на своём месте. Каждая такая перестановка в комбинаторике называется '''беспорядком'''.
+
'''Беспорядком''' в комбинаторике называется перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.
Количество всех беспорядков порядка <tex>n</tex> может быть вычислено с помощью принципа включения-исключения и дается выражением:
+
{{Теорема
 +
|id=идентификатор (необязательно), пример: th1.
  
[[Файл:Formula.png]]
+
|statement=Количество всех беспорядков порядка <tex>n</tex> или [http://ru.wikipedia.org/wiki/Субфакториал субфакториалом] числа <tex>n</tex> (обозначение: !<tex>n</tex>) может быть вычислено по формуле: [[Файл:Formula.png]]
  
которое называется субфакториалом числа n и обозначается, как !n.
+
|proof=}}
  
'''Доказательство'''
+
'''Доказательство:'''
  
Обозначим за [[Файл:Formula4.png]] - количество перестановок из n элементов, в которых на i-ой позиции стоит i.
+
Воспользуемся принципом включения-исключения: обозначим за [[Файл:Formula4.png]] количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
тогда по формуле включения-исключения имеем:
 
  
 
1)    [[Файл:Formula2.png]]
 
1)    [[Файл:Formula2.png]]
Строка 94: Строка 94:
 
2)    [[Файл:Formula3.png]]
 
2)    [[Файл:Formula3.png]]
  
Данные формулы эквивалентны! Действительно, если множества [[Файл:Formula4.png]] являются подмножествами некоторого множества [[Файл:Formula5.png]], то в силу правил де Моргана [[Файл:Formula6.png]].
+
Данные формулы являются эквивалентными. Действительно, если некоторое множество <math>\mathbf{S}</math> являются подмножествами некоторого множества [[Файл:Formula5.png]], то, в силу законов де Моргана  
  
В нашей задаче множество [[Файл:Formula5.png]] - есть количество перестановок из n элементов, т.е. n!. Черта над множеством [[Файл:Formula4.png]] означает дополняющее множество до [[Файл:Formula5.png]] или, в силу определения [[Файл:Formula4.png]], означает количество перестановок, где на i-ой позиции '''НЕ''' i.
+
<tex>|</tex> <math>\mathbf{S}</math> <tex>|</tex> <tex>=</tex> <tex>|</tex> [[Файл:Formula5.png]] <tex>|</tex> — <tex>|</tex> <math>\lnot</math><math>\mathbf{S}</math> <tex>|</tex>.  
  
Таким образом величина в левой части формулы 2) - есть количество перестановок, где на 1-ой позици '''НЕ''' 1, на 2-ой позици '''НЕ''' 2 и т.д. Т.е. количество искомых беспорядков! Осталось определить величины в правой части:
+
В данной задаче множество [[Файл:Formula5.png]] — есть количество перестановок из <tex>n</tex> элементов, т.е. <tex>n!</tex>. Верхнее подчеркивание или символ <math>\lnot</math> перед <math>\mathbf{S}</math> означает дополняющее множество до [[Файл:Formula5.png]] <math>\Rightarrow</math>  <math>\lnot</math> [[Файл:Formula4.png]] — количество перестановок, где <tex>i</tex>-ый элемент стоит '''НЕ''' на своём <tex>i</tex>-ом месте.
  
[[Файл:Formula5.png]] = <tex>n!</tex>
+
Таким образом величина в левой части формулы 2) — есть количество перестановок, где на 1-ой позици '''НЕ''' 1, на 2-ой позици '''НЕ''' 2 и т.д. То есть количество искомых беспорядков. Осталось определить величины в правой части:
  
|[[Файл:Formula4.png]]| можно получить зафиксировав число i на соответствующей ей позиции i, а остальные позиции заполнив как угодно остальными числами => |[[Файл:Formula4.png]]| = <tex>(n - 1)!</tex>. Суммирование ведется по всем i => [[Файл:Formula8.png]]
+
[[Файл:Formula5.png]] <tex>=</tex> <tex>n!</tex>.
Аналогичными рассуждениями получаем, что сумма пересечений некоторых k множеств - есть все перестановки при зафиксированных k позициях, т.е. [[Файл:Formula7.png]] х <tex>(n - k)!</tex>. Таким образом приходим к формуле:
 
  
[[Файл:Formula9.png]] = <tex>n!</tex> + [[Файл:Formula10.png]] х [[Файл:Formula7.png]] х <tex>(n - k)!</tex>
+
|[[Файл:Formula4.png]]| — количество перестановок с уже занятой позицией <tex>i</tex> <math>\Rightarrow</math> |[[Файл:Formula4.png]]| <tex>=</tex> <tex>(n - 1)!</tex>. Суммирование ведется по всем <tex>i</tex> <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |\lnot </tex>[[Файл:Formula4.png]]<tex>|</tex> <tex>=</tex> <math>\binom{n}{1}</math><tex>\cdot</tex><tex>(n-1)!</tex>
  
Раскрывая [[Файл:Formula7.png]] по общеизвестной формуле, получим требуемое выражение, т.е. количество беспорядков порядка <tex>n</tex>.
+
Производя аналогичные рассуждения, получаем, что сумма пересечений некоторых <tex>k</tex> множеств (то есть сумма всеx перестановки при некоторых зафиксированных <tex>k</tex> позициях) — есть <tex>(n-k)!</tex>. Количество способов выбрать <tex>k</tex> позиций — <math>\binom{n}{k}</math> <math>\Rightarrow</math> Количество перестановок с <tex>k</tex> неподвижными точками: <math>\binom{n}{k}</math><tex>\cdot</tex><tex>(n-k)!</tex>
 +
 
 +
[[Файл:Formula9.png]] <tex>=</tex> <tex>n!</tex> <tex>+</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>.
  
 
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Версия 20:36, 15 декабря 2012

Формула включения-исключения — комбинаторная формула, выражающая мощность объединения конечных множеств через мощности и мощности всех их возможных пересечений.

Случай для двух множеств

Для случая из двух множеств [math]A, B[/math] формула включения-исключения имеет следующий вид:

[math] | A \cup B | = | A | + | B | - | A \cap B |[/math]

В силу того, что в сумме [math]| A | + | B |[/math] элементы пересечения [math]A \cap B[/math] учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера—Венна для двух множеств, приведенной на рисунке справа.

Для случая с большим количеством рассматриваемых множеств [math] n [/math] процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.

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

Приведем два разноплановых доказательства теоремы.

I. Комбинаторное доказательство теоремы.

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

[math]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} [/math][math] = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} [/math]

Докажем, что [math] \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0[/math]

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

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

II. Доказательство теоремы по индукции.

Пусть [math]~l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]~l=1[/math] равенство обращается в тривиальное ([math] |A| = |A_1| [/math] — истинно). Для случая [math]~l=2[/math] справедливость теоремы пояснена выше. Таким образом, [math]~l=2[/math] — база индукции.

Предположим, что для [math]~l=n-1[/math] равенство верно. Докажем, что равенство истинно для [math]~l=n[/math]


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


Исходя из предположения индукции, имеем, что [math] | B | = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| [/math]


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


Очевидно, что [math] 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) (**)[/math]


Опираясь на предположение индукции и равенство [math] (**) [/math] имеем, что [math] |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| [/math]


Подставим полученные значения в [math](*)[/math]:


[math] | 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)[/math] [math] =| 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) [/math]


Докажем, что [math] | 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) [/math] [math] = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| [/math]

Равенство справедливо, потому что все наборы [math] I \in 2^N [/math] можно разбить на две группы :

  1. [math] I \in 2^{N'} [/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math], а будут все различные варианты индексов остальных множеств, т.е. [math] I \in 2^{N'}[/math].
  2. [math]\{n\} \cup I[/math], где [math]I \in N'[/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math].

Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и [math]|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| [/math] .

Таким образом, для [math]~l=n[/math] мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.
[math]\triangleleft[/math]

Беспорядки

Беспорядком в комбинаторике называется перестановка чисел от [math]1[/math] до [math]n[/math], в которой ни один элемент не стоит на своём месте.

Теорема:
Количество всех беспорядков порядка [math]n[/math] или субфакториалом числа [math]n[/math] (обозначение: ![math]n[/math]) может быть вычислено по формуле: Formula.png

Доказательство:

Воспользуемся принципом включения-исключения: обозначим за Formula4.png — количество перестановок из [math]n[/math] элементов, в каждой из которых [math]i[/math]-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:

1) Formula2.png

ИЛИ

2) Formula3.png

Данные формулы являются эквивалентными. Действительно, если некоторое множество [math]\mathbf{S}[/math] являются подмножествами некоторого множества Formula5.png, то, в силу законов де Моргана

[math]|[/math] [math]\mathbf{S}[/math] [math]|[/math] [math]=[/math] [math]|[/math] Formula5.png [math]|[/math][math]|[/math] [math]\lnot[/math][math]\mathbf{S}[/math] [math]|[/math].

В данной задаче множество Formula5.png — есть количество перестановок из [math]n[/math] элементов, т.е. [math]n![/math]. Верхнее подчеркивание или символ [math]\lnot[/math] перед [math]\mathbf{S}[/math] означает дополняющее множество до Formula5.png [math]\Rightarrow[/math] [math]\lnot[/math] Formula4.png — количество перестановок, где [math]i[/math]-ый элемент стоит НЕ на своём [math]i[/math]-ом месте.

Таким образом величина в левой части формулы 2) — есть количество перестановок, где на 1-ой позици НЕ 1, на 2-ой позици НЕ 2 и т.д. То есть количество искомых беспорядков. Осталось определить величины в правой части:

Formula5.png [math]=[/math] [math]n![/math].

|Formula4.png| — количество перестановок с уже занятой позицией [math]i[/math] [math]\Rightarrow[/math] |Formula4.png| [math]=[/math] [math](n - 1)![/math]. Суммирование ведется по всем [math]i[/math] [math]\Rightarrow[/math] [math]\sum \limits_{i = 1}^{n} |\lnot [/math]Formula4.png[math]|[/math] [math]=[/math] [math]\binom{n}{1}[/math][math]\cdot[/math][math](n-1)![/math]

Производя аналогичные рассуждения, получаем, что сумма пересечений некоторых [math]k[/math] множеств (то есть сумма всеx перестановки при некоторых зафиксированных [math]k[/math] позициях) — есть [math](n-k)![/math]. Количество способов выбрать [math]k[/math] позиций — [math]\binom{n}{k}[/math] [math]\Rightarrow[/math] Количество перестановок с [math]k[/math] неподвижными точками: [math]\binom{n}{k}[/math][math]\cdot[/math][math](n-k)![/math]

Formula9.png [math]=[/math] [math]n![/math] [math]+[/math] [math]\sum \limits_{i = 1}^{n} (-1)^{n}(n - k)![/math][math]\cdot[/math][math]\binom{n}{k}[/math]

Раскрывая [math]\binom{n}{k}[/math] по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка [math]n[/math].