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

1.

Формула
включенийисключений
ФЕДОТОВА Н.П.

2.

Задача 1
В научно-исследовательском университете работают 67 ученых, из
них 47 знают английский язык. Сколько человек не знают
английский язык?

3.

Задача 1
В научно-исследовательском университете работают 67 ученых, из
них 47 знают английский язык. Сколько человек не знают
английский язык?
N(a’) = 67 – 47 = 20
N (a’) = N – N(a)

4.

Задача 2
В научно-исследовательском университете работают 67 ученых, из
них 47 знают английский язык, 35 знают немецкий, 23 оба языка.
Сколько человек не знают иностранных языков?

5.

Задача 2
В научно-исследовательском университете работают 67 ученых, из
них 47 знают английский язык, 35 знают немецкий, 23 оба языка.
Сколько человек не знают иностранных языков?
N(a1’ a2’) = 67 – 47 – 35 + 23 = 8
N (a1’ a2’) = N – N(a1) – N(a2) + N(a1 a2)

6.

Задача 3
В научно-исследовательском университете работают
67 ученых, из них:
47 знают английский язык,
35 знают немецкий, 20 французский,
23 англ и нем, 11 нем и франц,
12 англ и франц, 5 – три языка.
Сколько человек не знают иностранных языков?

7.

Задача 3
В НИИ работают 67 ученых, из них:
47 знают английский язык,
35 знают немецкий, 20 французский,
23 англ и нем, 11 нем и франц,
12 англ и франц, 5 – три языка.
Сколько человек не знают иностранных языков?
N(a1’ a2’ a3’) = 67 – 47 – 35 – 20
+ 23 + 12 + 11 – 5 = 6
N (a1’ a2’ a3’) = N – N(a1) – N(a2) – N(a3)
+ N(a1 a2) + N(a1 a3) + N(a2 a3) – N(a1 a2 a3)

8.

Обобщение
N (a’) = N – N(a)
N (a1’ a2’) = N – N(a1) – N(a2) + N(a1 a2)
N (a1’ a2’ a3’) = N – N(a1) – N(a2) – N(a3)
+ N(a1 a2) + N(a1 a3) + N(a2 a3) – N(a1 a2 a3)
теорема

9.

10.

Задача. В чём ошибка?
Староста дал следующие сведения о студентах:
в группе учатся 45 человек, в том числе 25 юношей;
30 студентов учатся на 4 и 5 (со стипендией),
в том числе 16 юношей;
спортом занимаются 28 студентов, из них 18 юношей и 17 со
стипендией;
15 мальчиков учатся со стипендией и в то же время занимаются
спортом.

11.

Задача о простых числах
Сколько простых чисел в первой сотне?

12.

Решето Эратосфена

13.

Задача о беспорядках
Сколькими способами можно переставить n предметов, чтобы
каждый не оказался на своем месте?

14.

Ровно m свойств
Для док-ва потребуется следствие 5 с прошлой лекции

15.

Задача о ящиках
Сколькими способами можно разложить 10 шаров по 5 ящикам так,
чтобы 2 ящика остались пустыми?

16.

Не менее m свойств