Ця симуляція наочно показує принцип включень-виключень — комбінаторне правило для підрахунку елементів об'єднання множин без подвійного врахування спільних частин. Для двох множин формула виглядає як |A∪B| = |A| + |B| − |A∩B|, а для трьох — |A∪B∪C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Принцип почергово додає й віднімає розміри перетинів так, щоб кожен елемент враховувався рівно один раз.
Ви обираєте режим 2 або 3 множини, тоді переміщуєте повзунки областей (лише A, лише B, A∩B, а для трьох множин також A∩C, B∩C, A∩B∩C), щоб змінити діаграму Венна відносно всесвіту з 100 елементів. Кнопки перегляду перемикають між зображенням Венна, покроковим розкладом Формули та Прикладами: підрахунок подільності, безладні перестановки, сюр'єктивні функції та решето — все це ілюструє, де принцип застосовується в реальній комбінаториці.
Що таке принцип включень-виключень?
Це правило підрахунку, яке визначає кількість елементів в об'єднанні кількох множин: додаються розміри окремих множин, потім віднімаються розміри попарних перетинів, потім знову додаються потрійні перетини — і так далі. Знаки, що чергуються, виправляють ситуацію, коли елементи були б пораховані більше одного разу.
Чому перетин потрібно віднімати?
Коли ви додаєте |A| і |B|, кожен елемент, що належить обом множинам, враховується двічі — по одному разу в кожній. Вирахування |A∩B| прибирає один із цих дублікатів, залишаючи кожен спільний елемент порахованим лише один раз. Симуляція показує це виправлення у режимі Формули.
Яка формула для трьох множин?
|A∪B∪C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Спочатку додаються окремі множини, потім віднімаються три попарні перетини, а центральний потрійний перетин знову додається, бо спочатку він був порахований тричі, а потім тричі вилучений.
Кожен повзунок задає кількість елементів в одній непересічній ділянці діаграми Венна: лише A, лише B, A∩B у режимі двох множин, а також лише C, лише A∩C, лише B∩C та A∩B∩C у режимі трьох множин. Розміри повних множин, наприклад |A|, отримуються підсумовуванням усіх ділянок всередині кола A.
Пунктирний прямокутник із позначкою 𝒰 = 100 — це загальна сукупність елементів, що розглядається. Результат «Ні в одній» показує, скільки з цих 100 елементів не потрапили до жодної множини; він обчислюється як 100 мінус розмір об'єднання і не може бути від'ємним.
Режим 2 множини показує два кола, що перетинаються, і простішу формулу з одним виправленням, а режим 3 множини додає третє коло із сімома окремими ділянками та довшою формулою зі знаками, що чергуються. Перемикання режимів змінює доступні повзунки й спосіб обчислення об'єднання.
Так. Оскільки ви безпосередньо вводите кількість елементів у непересічних ділянках, об'єднання — це просто їхня сума, а режим Формули відтворює той самий результат через розкладання включень-виключень. Обидва способи завжди збігаються, що наочно підтверджує: знаки, що чергуються, справді усувають подвійний підрахунок.
Для n множин об'єднання дорівнює сумі розмірів окремих множин, мінус усі попарні перетини, плюс усі потрійні, і так далі, причому знак кожного доданка визначається як (−1) у степені на одиницю меншому за кількість множин, що перетинаються. Кількість доданків зростає як 2 у степені n мінус один.
Безладна перестановка — це перестановка, в якій жоден елемент не залишається на своєму початковому місці. Застосування включень-виключень до подій «елемент i залишився на місці» дає D(n) = n! · Σ (−1)^k / k! для k від 0 до n. У режимі Прикладів показано, що D(4) = 9.
Він лежить в основі підрахунку подільності та простих чисел у теорії чисел, решета Ератосфена, підрахунку сюр'єктивних функцій, ймовірності об'єднань подій, а також багатьох задач баз даних і пошуку, пов'язаних із категоріями, що перекриваються. Панель Прикладів демонструє кілька таких випадків.