No Image

Принцип включения и исключения

СОДЕРЖАНИЕ
856 просмотров
10 марта 2020

Содержание

Формула включения-исключения [ править ]

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

Для случая из двух множеств [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] riangleright[/math]

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

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

Рассмотрим некоторый элемент [math] x in igcup limits_^A_i [/math] . Пусть [math] x in igcap limits_^A_ [/math] . Тогда найдем число вхождений элемента [math] x [/math] в правую часть формулы.

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

В силу того, что [math] (1 + (-1)) ^ t = 1^t (-1)^0 + 1 ^ (-1) ^ 1 + ldots + 1^0 (-1)^t = sum limits_^ (-1)^j [/math] , имеем [math] 0 = (1 + (-1)) ^ t = sum limits_^ (-1)^j [/math] , то равенство доказано.

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

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

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]

Пусть [math] A [/math] — объединение [math]

n[/math] множеств. Очевидно, что [math] A = igcup limits_^A_i = left( <igcup limits_^A_i>
ight) cup A_n [/math] . Пусть [math] B = igcup limits_^A_i [/math] ; [math]N’ = < 1,2, ldots ,n-1 >[/math] .

Исходя из предположения индукции, имеем, что [math] | B | = sum limits_> (-1)^ <|I|+1>left| igcap limits_ < j in I>A_j
ight| [/math]

Кроме того, так как формула верна для [math]

l=2[/math] (из базы индукции), то верно равенство [math] | A | = | B | + | A_n | – | B cap A_n | (*)[/math] .

Очевидно, что [math] B cap A_n = left( igcup limits_^A_i
ight) cap A_n = igcup limits_^ left( A_i cap A_n
ight) (**)[/math]

Опираясь на предположение индукции и равенство [math] (**) [/math] имеем, что [math] |B cap A_n| = sum limits_> (-1)^ <|I|+1>left| igcap limits_ < j in I>left( A_j cap A_n
ight)
ight| = sum limits_
> (-1)^ <|I|+1>left| igcap limits_ < jin I cup < n >> A_j
ight| [/math]

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

[math] | A | = | A_n |+left( sum limits_> (-1)^ <|I|+1>left| igcap limits_ < j in I>A_j
ight|
ight) – left( sum limits_
> (-1)^ <|I|+1>left| igcap limits_ < jin I cup < n >> A_j
ight|
ight)[/math] [math] =| A_n |+left( sum limits_
> (-1)^ <|I|+1>left| igcap limits_ < j in I >A_j
ight|
ight) + left( sum limits_
> (-1)^ <|I|+2>left| igcap limits_ < jin I cup < n >> A_j
ight|
ight) [/math]

Докажем, что [math] | A_n |+left( sum limits_> (-1)^ <|I|+1>left| igcap limits_ < j in I >A_j
ight|
ight) + left( sum limits_
> (-1)^ <|I|+2>left| igcap limits_ < jin I cup < n >> A_j
ight|
ight) [/math] [math] = sum limits_
(-1)^ <|I|+1>left| igcap limits_ < j in I >A_j
ight| [/math]

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

  1. [math] I in 2^ [/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math] , а будут все различные варианты индексов остальных множеств, т.е. [math] I in 2^

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

Таким образом, для [math]

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

[math] riangleleft[/math]

Беспорядки [ править ]

Определение:
Беспорядок (англ. Derangement) — это перестановка чисел от [math]1[/math] до [math]n[/math] , в которой ни один элемент не стоит на своём месте.

Явная формула с использованием принципа включения-исключения [ править ]

Теорема:
Доказательство:
[math] riangleright[/math]

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

[math]|A_i| = (n – 1)![/math] , так как [math]i[/math] -ая позиция занята числом [math]i[/math] . [math]inom<1>[/math] — количество способов выбрать одну [math]i[/math] -ую позицию [math] Rightarrow sum limits_^ |A_i| = inom <1>(n-1)![/math]

Рассмотрим [math] |A_ igcap A_ igcap . igcap A_| [/math] , где [math] 1leqslant i_1 lt i_2 lt . lt i_k leqslant n [/math] . Так как некоторые [math]k[/math] позиций [math]i_1, i_2, . , i_k [/math] заняты соответствующими числами, то количество способов расставить остальные [math]n-k[/math] чисел равно [math](n-k)![/math] . То есть [math] |A_ igcap A_ igcap . igcap A_| = (n – k)! [/math] Количество всех способов выбрать [math]k[/math] позиций [math]i_1, i_2, . , i_k [/math] равно [math]inom [/math] . Таким образом получаем, что:

Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем:

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

[math] riangleleft[/math]

Рекурретное соотношение для нахождения количества беспорядков [ править ]

[math] d(n)=n imes d(n-1)+(-1)^ [/math] ,

где [math] d(1)=0 [/math] , а [math] d(2)=1 [/math]

Утверждение:
[math] riangleright[/math]

1) Докажем второе соотношение:

Так как [math] d(n)=!n [/math] , то можно переписать эту формулу, как [math] !n=n!(n-1)+(-1)^ [/math]

2) Докажем первое соотношение:

У нас есть [math] n [/math] чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером.

Предположим, что первое число оказалось на месте с номером [math] i [/math] . Это можно сделать [math] n-1 [/math] способами, так как первое число может оказаться на любом месте, кроме первого. Теперь есть 2 варианта, зависящие от того, окажется ли число с номером [math] i [/math] на первом месте или нет.

  • Число [math] i [/math] на первом месте. Остается [math] n-2 [/math] мест и [math] n-2 [/math] чисел. То есть количество беспорядков от [math] n-2 [/math]
  • Число [math] i [/math] не может оказаться на первом месте. Это эквивалентно решению задачи с [math] n-1 [/math] местами и [math] n-1 [/math] числами (первое число уже заняло место, а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером [math] i [/math] запрещенным будет первое место). Получается количество беспорядков от [math] n-1 [/math] .

Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число [math] i [/math] занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и [math] i [/math] -го чисел. Во втором же случае число с номером [math] i [/math] попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое.

В итоге получается необходимая формула.

[math] riangleleft[/math]

Задача о перестановках [ править ]

Сколько есть перестановок чисел от [math] 0 [/math] до [math] 9 [/math] таких, что первый элемент больше [math] 1 [/math] , а последний меньше [math] 8 [/math] ?

Посчитаем количество "плохих" перестановок, то есть таких, у которых первый элемент [math] leqslant 1 [/math] (множество таких перестановок обозначим [math] X [/math] ) и/или последний [math] leqslant 8 [/math] (множество таких перестановок обозначим [math] Y [/math] ).

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

[math] |X|+|Y|-|X cap Y| [/math]

Проведя несложные комбинаторные вычисления, получим:

[math] 2 imes 9!+2 imes 9! – 2 imes 2 imes 8! [/math]

Отнимая это число от общего числа перестановок [math] 10! [/math] , получим ответ.

Задача о нахождении числа взаимно простых четвёрок [ править ]

Дано [math] n [/math] чисел: [math] a_1, a_2. a_n [/math] . Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.

Посчитаем число "плохих" четвёрок, то есть таких, в которых все числа делятся на число [math] d gt 1 [/math] .

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

[math] answer=sum limits_ (-1)^ imes f(d) [/math] ,

где [math] deg(d) [/math] — это количество простых в факторизации числа [math] d [/math] , [math] f(d) [/math] — количество четвёрок, делящихся на [math] d [/math] .

Чтобы посчитать функцию [math] f(d) [/math] , надо просто посчитать количество чисел, кратных [math] d [/math] , и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку.

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

На этой странице мы собрали примеры решения учебных задач на применение принципа включений-исключений в комбинаторных задачах по теории вероятностей или дискретной математике.

Краткая теория

Формула включений и исключений для двух множеств

Для любых конечных множеств $A$ и $B$ справедливо равенство:

В сумме $|A|+|B|$ пересечение $Acap B$ учтено дважды, поэтому для компенсации мы вычитаем $|Acap B|$.

Формула включений и исключений для трех множеств

Для любых конечных множеств $A$, $B$ и $C$ справедливо равенство:

$$ | A cup B cup C | =|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap B cap C|. $$

Поясним кратко, откуда берутся слагаемые справа. Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности $A$, $B$ и $C$, мы дважды учли каждый двукратный элемент и трижды — каждый трёхкратный. Вычтя три попарных пересечения, мы «восстановили справедливость» в отношении двукратных элементов, но при этом трижды вычли трехкратные элементы, которые теперь оказались полностью неучтёнными. Поэтому надо добавить мощность тройного пересечения.

Разберем примеры решений типовых задач с этой формулой включений и исключений для случая 2 и 3 множеств (другие примеры подобных заданий вы найдете в разделе Примеры по дискретной математике: Множества и отношения).

Примеры решенных задач

Задача 1. Формула включений и исключений (для трех множеств). Известно, что свойством А обладает n объектов, В — m объектов, С — с объектов, АВ — р объектов, АС — g объектов, ВС — r объектов, АВС — q объектов. Сколько всего объектов?

Задача 2. Из 100 человек студентов, сдавших сессию, 48 человек сдали экономику, 42 студента – математику и 37 человек – логику. По экономике или математике сдали экзамен 76 человек, по экономике или логике также 76 человек, а по математике или логике – 66 человек. Сколько человек сдали хотя бы один экзамен, если все три предмета сдали 5 человек? Сколько человек не сдали ни одного экзамена? Сколько человек сдали только один экзамен по логике?

Задача 3. При обследовании читательских вкусов студентов оказалось, что 60 % студентов читают журнал А, 50 % – журнал В, 50 % – журнал С, 30 % – журналы А и В, 20 % – журналы В и С, 40 % – журналы А и С, 10 % – журналы А, В и С. Выяснить, сколько процентов студентов:
1) не читает ни одного из журналов;
2) читает в точности два журнала;
3) читает не менее двух журналов.

Задача 4. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро – немецкий, шестеро – французский, пятеро знают английский и немецкий, четверо – английский и французский, трое – немецкий и французский. Выяснить:
1) сколько человек знают все три языка;
2) сколько человек знают ровно два языка;
3) сколько человек знают только английский язык.

Задача 5. Из 100 туристов, выехавших в заграничное путешествие, 10 человек не знают ни немецкого, ни французского языков, 76 человек знают немецкий и 83 – французский. Сколько туристов знают оба эти языка?

Задача 6. В отряде из 40 ребят 30 умеют плавать; 27 умеют играть в шахматы; 5 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.

Видеоурок: Формула включений и исключений

Решебник по терверу и комбинаторике

Если решения нужны срочно и почти даром? Ищите в решебнике по теории вероятностей:

КОМБИНАТОРИКИ

Формулы и алгоритмы, рассмотренные в теме 1, дают способы вычисления комбинаторных чисел для некоторых распространенных конфигураций. Однако, практические задачи далеко не всегда непосредственно сводятся к ним. В этом случае чрезвычайно важно знание методов сведения одних конфигураций к другим, либо общих методов, не столь зависящих от конкретных комбинаторных структур. Рассмотрим наиболее популярные из таких методов.

1.1. Вывод формулы. Пусть имеем N объектов и некоторый набор свойств а1, …, аn, которыми могут обладать эти объекты. Обозначим N(i) – число объектов, обладающих свойством аi, и вообще N(i1, …, ik) – число объектов, обладающих одновременно всеми свойствами . Пусть N(0) – число объектов, не обладающих ни одним из свойств аi. Справедлива формула включения и исключения:

N(0) = N – + + …

+ (– 1) k + … + (–1) n N(1, 2, … , n). (3.1)

Символ 1 £ i1 0 . n = 1. N(0) = N – N(1). Всего существует одно свойство. От общего числа объектов отнимем количество объектов, обладающих этим свойством – узнаем, сколько объектов этим свойством не обладают.

2 0 . Пусть для n – 1 свойств справедлива формула

N(0) = N – + + …

+ (– 1) k + … + (–1) n N(1, 2, … , n – 1). (3.2)

Пусть теперь имеем множество, все элементы которого обладают свойством аn, и, возможно, обладают свойствами а1, …, аn–1. Очевидно, для этого множества формула (3.2) также верна и имеет вид:

N(0, n) = N(n) –+ … +

+(–1) n –2 + (–1) n –1 N(1, 2, … , n – 1, n). (3.3)

В (3.3) везде в скобках дописано n, т.к. все элементы множества свойством аn обладают. Вычтем (3.3) из (3.2):

N(0) – N(0, n) = N – + + … – (–1) n –1 N(1, 2, … , n – 1, n).

N(0) – N(0, n) = N –++… + (–1) n N(1, 2,…,n).

Справа мы получили требуемую формулу. А что слева? N(0) – число элементов, не обладающих свойствами а1, …, аn–1, но, возможно, обладающих свойством аn. N(0, n) – число элементов, не обладающих свойствами а1, …, аn–1, но обязательно обладающих свойством аn. Следовательно, N(0) – N(0, n) – число элементов, не обладающих ни одним из свойств а1, …, аn, т.е. требуемая величина. Формула доказана.

Пример 3.1. Староста класса подал следующие сведения о классе. Всего в классе 45 учеников, из них 25 мальчиков. 30 человек учится без троек, из них – 16 мальчиков; 28 человек занимаются спортом, из них – 18 мальчиков и 17 хорошистов и отличников; 15 мальчиков учатся без троек и одновременно занимаются спортом. Классный руководитель внимательно посмотрел список и сказал, что в сведениях есть ошибка. Как он это узнал?

Решение. Обозначим a1 – свойство принадлежности к мужскому полу; a2 – хорошая успеваемость; a3 – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка.

1.2. Модификации формулы включения и исключения

2.а. Формулу (2.1) можно обобщить для определения числа элементов, обладающих в точности k свойствами (0 £ k £ n):

N(k) = + …+ (– 1) s–k + …

+ (–1) n–k ×N(1, 2, … , n). (3.4)

Пример 3.2. В отделе НИИ каждый сотрудник владеет хотя бы одним иностранным языком. Известно, что английским языком владеют 6 человек, немецким – 6, французским – 7, английским и немецким – 4, немецким и французским – 3, английским и французским – 2, все три языка знает 1 человек. Определить, сколько всего человек в отделе, сколько человек владеют только английским, только немецким, только французским, и сколько человек знает только 1 иностранный язык.

Решение. Согласно условиям задачи N(0) = 0, т.к. в отделе нет сотрудников, не владеющих иностранными языками. Следовательно, по формуле (3.1) получаем:

N = + N(1, 2, 3) (3.5)

N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек всего в отделе.

Для вычисления остальных показателей также воспользуемся формулой (3.5). Найдем, например N(только А) – число человек, не владеющих никаким другим языком, кроме английского. Для этого формулу (3.5) надо применить только к множеству людей, владеющих английским языком. В этом случае n = 2. Тогда N = N(A), N(1) и N(2) – число людей, владеющих помимо английского еще немецким и французским, соответственно, N(1, 2) – число людей, владеющих помимо английского еще одновременно немецким и французским. Отсюда

N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) =

N(только Н) = N(Н) – N(А и Н) – N(Н и Ф) + N(А и Н и Ф) =

N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) =

Вычислим теперь N(1) – число людей, владеющих только 1 языком. Воспользуемся формулой (3.4) при k = 1.

N(1) = N(А) + N(Н) + N(Ф) + (–1) 2–1 ×× [N(А и Н) + N(Н и Ф) + N(А и Ф)] + (–1) 3–1 ×× N(А и Н и Ф) = 6 + 6 + 7 – 2×(4 + 3 + 2) + 3×1 = 4.

Такой же результат получим, если сложим N(только A) + N(только Н) + N(только Ф).

2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений различных множеств, т.е. дать теоретико-множественное представление принципа включения и исключения. Пусть имеем некоторое конечное множество А и его подмножества Аj, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид:

= |A| – + + …

+ (– 1) k + …+ (–1) n .

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9617 – | 7511 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Читайте также:  Программа для ретуширования лица на фото
Комментировать
856 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock
detector