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

Дотепер мова йшла про підрахунок числа підмножин, що утворяться шляхом вибірки об'єктів з деякої множині відповідно до умов, що визначають їхню кількість, упорядкованість і повторюваність. Не менше значення мають задачі перерахування, зв'язанізвластивостями об'єктів.

Нехай є N об'єктів і деяка сукупність властивостей . Позначимо через N, N, Nі т.д. кількість об'єктів, що мають відповідно властивостями і т.д. Очевидно, таких чисел буде стільки, скільки підмножин можна утворити з елементів множині Н, тобто (деякі числа можуть дорівнювати нулю). Якщо бажають підкреслити, що враховуються об'єкти, що не мають властивістю , то пишуть . Наприклад, Nозначає число об'єктів, що мають властивості й і не мають властивість .

Формула включення і виключення. Число об'єктів, що не мають жодним із властивостей множини Н, визначається формулою включення і виключення:

Дійсно, при відниманні з N об'єктів із властивостями (і = 1, 2, ..., п) об'єкти, що мають дві властивості і (і j), віднімаються двічі, і тому потрібно додати N, де — попарні сполучення елементів з Н. Але при цьому двічі враховуються ті об'єкти, що мають три властивості і, отже, їх необхідно виключити, тобто відняти суму всіх N, де — сполучення з n властивостей по трьох. Цей процес включення і виключення продовжується до останнього члена , що визначає число об'єктів із усіма п властивостями, знак якого залежить від парності п. Наведена формула відома також під назвами: символічний метод, принцип перехресної класифікації, метод решета, формула обернення.

Якщо записати і розглянути послідовність символів як алгебраїчний добуток, то формулу включення і виключення можна представити в символічному вигляді.

Приклад. Для n = 3 мається

причому приймається, що N(1) = N.

ЗавдЯкі такій формалізації можна записати формулу для числа об'єктів, що мають і не мають деякі властивості:

.

Приклад. Нехай задані властивості шарів: -сталева, -чорна, — сферична, причому N () = 13; N() = 10; N() =14; N== 4; N= 5; N= 3 і N= 1. Якщо є усього N = 38 шарів, то число таких з них, що не мають жодної із зазначених властивостей, буде N=38 — (13 + 10 + + 14) + (4 + 5 + 3) — 1 = 12. Число сталевих, але не чорних і не сферичних шарів дорівнює:

+

+

Принцип включення і виключення наочно ілюструється діаграмою Венна, що для розглянутого прикладу показана на рис. 13.1.

 

Рис. 13.1. Діаграма Венна для множин, що характеризуються трьома властивостями