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

1.12.1. В группе 25 студентов, 15 занимаются лыжами, 12 – коньками, 8 и тем, и другим. Сколько студентов не занимается этими видами спорта?

1.12.2. (Обобщение) Проверьте, что если A и B – конечные множества, то Здесь - число элементов множества A.

1.12.3. В группе 15 студентов занимаются футболом, 13 – волейболом, 12 – баскетболом, 10 – футболом и волейболом, 11 – волейболом и баскетболом, 12 – футболом и баскетболом, 8 – всеми тремя видами спорта. Сколько студентов занимается хотя бы одним из этих видов спорта?

1.12.4. (Обобщение). Докажите, что для конечных множеств A,B,C справедлива формула

.

1.12.5. Как выглядит аналог формул из упражнений 1.12.2 и 1.12.4 для n множеств?

Ответ.

.

Указание. Один из способов доказательства: проверьте, что каждый элемент учтен в правой части в общей сложности один раз. Для этого предположите, что и воспользуйтесь формулой из задачи 1.12.2.

1.12.6. Сколько существует перестановок чисел 1,2,…, n, в которых

А) число 1 расположено на своем месте?

B) числа 1 и 2 расположены на своих местах?

C) числа 1,2,…, k расположены на своих местах?

D) хотя бы одно из чисел расположено на своем месте?

E) ни одно из чисел не расположено на своем месте (беспорядки)?

1.12.7. Пусть D_n – число беспорядков среди перестановок чисел 1,2,…, n. Найдите . Ответ несколько неожиданный: 1/e. Таким образом, при больших n ПОЛНЫЕ беспорядки составляют примерно треть всех перестановок. Одно из объяснений того, почему в мире так много беспорядка!