Презентация, доклад по теме Метод включения и исключения

Лавлинский М.В., LavlinskiMV@mail.ru

I. Объединение 2 непересекающихся множеств

Правило 1.
n(А)= а, n(В) = b, А∩В = ∅ ⇒
n(A∪B) = n(А) + n(В) = a + b

Задача №1.
Известно, что в некотором информационном сообщении содержится 578 согласных букв и 234 гласных (в сообщении отсутствуют ь и ъ). Сколько всего букв в сообщении.

Решение:
А∩В = ∅
n(A∪B) = n(А) + n(В) = 578+234 = 812


Ответ: 812

Дано:
n(A) = 578
n(B) = 234

Найти:
n(A∪B) - ?

II. Объединение n непересекающихся множеств

Правило 2.
Множества А1, А2, ..., Аn попарно не пересекаются ⇒
n( А1 ∪ А2 ∪ ... ∪ Аn) = n( А1) + n(A2) + ... + n(Аn)

Задача №2.
Множество А - студенты ЧГПУ; n(A) = 6000; В - преподаватели ЧГПУ; n(B)=340; C - непреподавательский состав ЧГПУ; n(C) = 110. Из скольких человек состоит коллектив ЧГПУ?

Решение:
А∩В = ∅, А∩C = ∅, B∩C = ∅
n(A∪B∪C) = n(А) + n(В) + n(C) = 6000 + 340 + 110 = 6450

Ответ: 6450

Дано:
n(A) = 6000
n(B) = 340
n(C) = 110
Найти:
n(A∪B∪C) - ?

III. Разность 2-ух множеств

Правило 3.
n(А) = а, n(В) = b, В ⊂ A ⇒
n(A\B) = n(А) - n(В) = a - b

Задача №3.
А - абитуриенты, поступавшие в ЧГПУ в 2012 году. n(A)=2000. В - студенты первокурсники ЧГПУ в 2012/2013 году, n(B) = 900. Сколько абитуриентов, не поступивших в 2012 году в ЧГПУ.

Решение:
В ⊂ А
n(A\B) = n(А) - n(В) = 2000-900 = 1100


Ответ: 1100

Дано:
n(A) = 2000
n(B) = 900

Найти:
n(A\B) - ?

IV. Объединение 2 пересекающихся множеств

Правило 4.
n(А) = а, n(В) = b, n(А∩В) = c ⇒
n(A∪B) = n(А) + n(В) - n(А∩В) = a + b - c

Обоснование: складывая элементы пересекающихся множеств А и В, мы дважды считаем элементы, принадлежащие их пересечению.

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

Задача №4.
В школьной библиотеке содержатся книги с русскими текстами, книги с английскими текстами, некоторые книги содержат как английские, так и русские тексты. Известно, что из 590 книг в 500 есть тексты на русском языке, и в 100 книгах - английские тексты. Сколько книг содержат тексты как на русском, так и на английском языке? Сколько книг содержат тексты только на русском языке? Сколько книг содержат тексты только на английском языке?

Решение:
1) А∩В ≠ ∅
n(A∪B) = n(А) + n(В) - n(А∩В)
2) 590 = 500 + 100 - n(Р∩А)
⇒ n(Р∩А) = 10 (рус. и англ. книги)
3) n(P\(P∩A)) = 500 – 10 = 490 (рус. книги)
4) n(A\(P∩A)) = 100 – 10 = 90 (англ. книги)

Ответ: 10, 490, 90

Дано:
n(Р) = 500
n(А) = 100
n(P∪A) = 590

Найти:
n(P∩A) - ?
n(P\(P∩A)) - ?
n(A\(P∩A)) - ?

Задача №5.
В бухгалтерии мебельной фабрики было обнаружено расхождение в сведениях: за месяц общий объем изготовленных кроватей и кресел 780 единиц, но, по данным из кроватного цеха, кроватей выпущено 360, из кресельного цеха вышло 540 кресел. В чем причина расхождения данных, сколько на самом деле кресел и кроватей выпускают соответствующие цеха?

Решение:
1) Выпускаются кресла-кровати
А∩В ≠ ∅
n(A∪B) = n(А) + n(В) - n(А∩В)
2) 780 = 360 + 540 - n(А∩В)
⇒ n(А∩В) = 120 (кресла-кровати)
3) n(А\(А∩В)) = 360 – 120 = 240 (кровати)
4) n(В\(А∩В)) = 540 – 120 = 420 (кресла)

Ответ: 240, 420

Дано:
n(А) = 360
n(В) = 540
n(А∪В) = 780

Найти:
n(А\(А∩В)) - ?
n(В\(А∩В)) - ?

V. Объединение 3 пересекающихся множеств

Правило 5.
n(A∪В∪С)=n(А)+n(В)+n(С)-n(А∩В)-n(В∩С)-n(А∩С)+n(А∩В∩С)

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

Студенты первого курса, изучающие информатику в университете, могут посещать и дополнительные дисциплины. В этом году 25 из них предпочли изучать бухгалтерию, 27 выбрали бизнес, а 12 решили заниматься туризмом. Кроме того, было 20 студентов, слушающих курс бухгалтерии и бизнеса, 5 изучали бухгалтерию и туризм, а 3 — туризм и бизнес. Известно, что никто из студентов не отважился посещать сразу три дополнительных курса. Сколько студентов посещали по крайней мере один дополнительный курс? Сколько из них были увлечены только туризмом?

Решение:
1) n(A∪B∪C) = 25 + 27 + 12 – 20 – 5 – 3 +0
⇒ n(A∪B∪C) = 36
2) x = 12 – 5 – 3 = 4 (только туристы)

Ответ: 36, 4

Дано:
n(А)=25, n(В)=27, n(С) =12
n(A∩B)=20, n(A∩C)=5
n(B∩C)=3
n(A∩B∩C)=0
Найти:
n(A∪B∪C) - ?

VI. Формула включений и исключений

n(A∪B) = n(А) + n(В) - n(А∩В)
n(A∪В∪С)=
n(А)+n(В)+n(С)-n(А∩В)-n(В∩С)-n(А∩С)+n(А∩В∩С)
n(A∪В∪С ∪D)=
n(А)+n(В)+n(С)+n(D)-n(А∩В)-n(А∩С)-n(А∩D)-n(В∩С)-n(В∩D)-n(C∩D)+n(А∩В∩С)+n(А∩В∩D)+n(А∩С∩D)+n(В∩С∩D)-n(А∩В∩С ∩D)
4) …

Домашнее задание

*

О.В.Кузьмин. Перечислительная комбинаторика
§ 1.2. Правило суммы, § 1.3
“3_1_Метод включения и исключения [ДЗ].doc”
Подготовиться к СР