3. Формула включень та виключень

Нехай множина складається з елементів, причому деякі з елементів можуть мати одну чи декілька з властивостей. Позначимо черезмножину елементів, що мають властивість, а черезкількість елементів у цій множині. Тоді має місце рівність

₍₁₅₎

Ця формула називається формулою включень та виключень. Інколи застосування даної формули є єдиним методом розв’язання задачі.

Приклад 1. Скільки чисел серед першої тисячі натуральних чисел не діляться без остачі ні на 2, ні на 3, ні на 5, ні на 7?

Розв’язання. Позначимо через властивість:“число ділиться без остачі на ”. Тоді – це множина чисел з першої тисячі натуральних чисел, що діляться без остачі на. Очевидно, що

, ,,

, ,,,,,,

, ,,,,

де позначає цілу частину числа. Кількістьчисел, що не діляться без остачі ні на 2, ні на 3, ні на 5, ні на 7 дорівнює . Згідно з (15) маємо

.

Отже кількість чисел, жодне з яких не ділиться ні на 2, ні на 3, ні на 5, ні на 7 дорівнює

Приклад 2. По пустелі іде караван із 5 верблюдів. Скількома способами можна переставити верблюдів таким чином, щоб попереду кожного верблюда йшов інший, ніж раніше?

Розв’язання. Перенумеруємо верблюдів згідно з їх розташуванням у каравані: 12345. Загальна кількість можливих перестановок дорівнює . Позначимо черезвластивість:“перестановка містить пару ”. Нехай – це множина перестановок, що мають властивість. Треба обчислити кількістьперестановок, які не належать жодній з множин, тобто

.

Далі застосовуємо формулу включень та виключень, зазначивши, що (парарозглядається як один елемент; маємо усього чотири елементи для перестановок),(якщо, торозглядається як один елемент; якщо ж, то паритарозглядається як два елементи; легко бачити, що в обох цих випадках маємо усього три елементи для перестановок),(для всіх варіантів взаємного розташуваннямаємо усього два елементи для перестановок),(існує єдина комбінація, коли всі п’ять цифр ідуть у зростаючому порядку). Враховуючи те, що кількість доданків у-й сумі формули (15) дорівнює(у нашому випадку), маємо

Приклад 3. Треба надіслати 6 термінових листів за допомогою 3 кур’єрів. Скількома способами це можна зробити, якщо: a) листи різні і кожен лист можна дати довільному кур’єру; b) листи різні і кожен з кур’єрів повинен везти хоча б один лист; c) листи однакові і кожен з них можна дати довільному кур’єру; d) листи однакові і кожен з кур’єрів повинен везти хоча б один лист?

Розв’язання. Ці чотири випадки потребують принципово різних методів розв’язання.

А. Кожен з 6 листів незалежно від інших можна дати довільному кур’єру (існує 3 способи). Тому за правилом множення загальна кількість способів дорівнює .

B. Якщо ж кожен з кур’єрів везе хоча б один лист, то метод розв’язання задачі принципово змінюється. У цьому випадку використовується формула включень та виключень. Як було з’ясовано вище, загальна кількість варіантів дорівнює . Позначимо черезвластивість:“-й кур’єр не везе жодного листа”. Нехай – це множина способів, якими можна розподілити листи таким чином, щоб була виконана властивість. Треба обчислити кількістьспособів розподілу листів, які не належать жодній з множин, тобто

.

Враховуючи те, що (6 листів розподіляємо між двома кур’єрами),(всі 6 листів дістаються одному кур’єру),(не існує варіантів, коли жоден з кур’єрів не везе листів), за формулою (15) обчислюємо

C. У випадку однакових листів застосовується формула для комбінацій з повтореннями. А саме, треба розподілити 6 однакових листів на три групи (). Використовуючи метод перегородок (приклад 11 у розділі 1), вводимо дві перегородки, які визначають скільки саме листів повезе кожен з кур’єрів. В результаті чого отримуємо відповідь.

D. Розглянемо випадок, коли кожен з кур’єрів повинен везти хоча б один лист. Оскільки всі листи однакові, то кожному з кур’єрів можна наперед дати по одному листу. В цьому випадку задача зводиться до попередньої, а саме, треба розподілити 3 однакових листа на три групи (). Використовуючи метод перегородок, отримуємо відповідь.