Формула включень-виключень
З Вікіпедії, безкоштовно encyclopedia
Формула включень-виключень (або принцип включень-виключень) — комбінаторна формула, що дозволяє визначити потужність об'єднання скінченного числа скінченних множин, які в загальному випадку можуть перетинатися один з одним.
Наприклад, у випадку двох множин та формула включень-виключень має вигляд:
У сумі елементи перетину враховані двічі, тому віднімаємо з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, яка наведена на малюнку праворуч.
У випадку трьох множин A, B та C формула має вигляд:
Ця формула може бути перевірена підрахунком того, скільки разів кожна область діаграми Ейлера-Венна використовується в правій частині формули. В цьому випадку, можна зауважити, що елементи перетину трьох множин будуть три рази враховані і три рази відняті, тому їх потрібно додати задля правильного підрахунку.
Таким же чином і в разі множин процес знаходження кількості елементів об'єднання полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули.