Формула включень-виключень

Формула включень-виключень (або принцип включень-виключень) комбінаторна формула, що дозволяє визначити потужність об'єднання скінченного числа скінченних множин, які в загальному випадку можуть перетинатися один з одним.

Випадок двох множин

Наприклад, у випадку двох множин та формула включень-виключень має вигляд:

У сумі елементи перетину враховані двічі, тому віднімаємо з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, яка наведена на малюнку праворуч.

Формула включень-виключень для трьох множин

У випадку трьох множин A, B та C формула має вигляд:

Ця формула може бути перевірена підрахунком того, скільки разів кожна область діаграми Ейлера-Венна використовується в правій частині формули. В цьому випадку, можна зауважити, що елементи перетину трьох множин будуть три рази враховані і три рази відняті, тому їх потрібно додати задля правильного підрахунку.

Таким же чином і в разі множин процес знаходження кількості елементів об'єднання полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули.

Історія

Вперше формулу включень-виключень опублікував португальський математик Даніель да Сільва в 1854 році[1]. Але ще в 1713 Микола Бернуллі використовував цей метод для вирішення завдання Монмора, відомої як задача про зустрічі (фр. Le problème des rencontres)[2], окремим випадком якої є задача про безлад. Також формулу включень-виключень пов'язують з іменами французького математика Абрахама де Муавра і англійського математика Джозефа Сильвестра[3]. У теорії ймовірностей аналог принципу включень-виключень відомий як формула Анрі Пуанкаре[4].

Формулювання

Формулу включень-виключень можна сформулювати в різних формах.

У термінах множин

Нехай  скінченні множини. Формула включень-виключень стверджує:

Більш компактно можна записати так:

або

При отримуємо формули для двох або трьох множин, наведені вище.

У термінах властивостей

Принцип включень-виключень часто наводять в такому альтернативному формулюванні [5]. Нехай дано кінцеву множину , яка складається з елементів, і нехай є набір властивостей . Кожен елемент множини може володіти або не володіти будь-якою з цих властивостей. Позначимо через кількість елементів, що володіють відповідно властивостями (і, можливо, деякими іншими). Також через позначимо кількість елементів, що не володіють жодною з властивостей . Тоді має місце формула:

Формулювання принципу включень-виключень у термінах множин еквівалентне формулюванню в термінах властивостей. Дійсно, якщо множина є підмножинами деякої множини , то в силу законів де Моргана (риска над множиною позначає доповнення в множині ), і формулу включень-виключень можна переписати так:

Якщо тепер замість «елемент належить множини » говорити «елемент має властивість », то ми отримаємо формулювання принципу включень-виключень в термінах властивостей, і навпаки.

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

Доведення

Існує кілька доведень формули включень-виключень.

За математичною індукцією

Комбінаторне доведення

Використовуючи індикаторні функції

Застосування

Задача про безлад

Класичний приклад використання формули включень-виключень — задача про безлад[5]. Потрібно знайти число перестановок множини таких що для всіх . Такі перестановки називаються безладом.

Нехай  — множина всіх перестановок і нехай властивість перестановки виражається рівністю . Тоді число безладів є . Легко бачити, що  — число перестановок, що залишають на місці елементи , і таким чином сума містить однакових доданків. Формула включень-виключень дає вираз для числа безладів:

Це співвідношення можна перетворити до вигляду

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

Обчислення функції Ейлера

Інший приклад застосування формули включень-виключень — знаходження явного вираження для функції Ейлера [7], що виражає кількість чисел з взаємно простих з .

Нехай канонічне розкладання числа на прості множники має вигляд

Число взаємно просте з тоді і тільки тоді, коли жоден з простих дільників ділить . Якщо тепер властивість означає, що ділить , то кількість чисел, взаємно простих з є .

Кількість чисел, що володіють властивостями дорівнює , оскільки .

За формулою включень-виключень знаходимо:

Ця формула перетвориться до виду:

Варіації і узагальнення

Принцип включення-виключення для ймовірностей

Нехай  імовірнісний простір. Тоді для випадкових подій виконується формула[1][6][8]

Ця формула виражає принцип включень-виключень для ймовірностей. Її можна отримати з принципу включень-виключень у формі індикаторних функцій:

Нехай  — події імовірнісного простору , тобто . Візьмемо математичне сподівання від обох частин цього співвідношення, і, скориставшись лінійністю математичного сподівання і рівністю для довільного події , отримаємо формулу включення-виключення для ймовірностей.

Принцип включень-виключень у просторах з мірою

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

Очевидно, принцип включень-виключень для ймовірностей і для потужностей скінченних множин є окремими випадками цієї формули. У першому випадку мірою є, природно, ймовірнісна міра у відповідному ймовірнісному простору: . У другому випадку як міра береться потужність множини: .

Вивести принцип включень-виключень для просторів з мірою можна також, як для зазначених окремих випадків, з тотожності для індикаторних функцій:

Нехай  — вимірні множини простору , тобто . Проінтегруємо обидві частини цієї рівності по мірі , скористаємось лінійністю інтеграла і співвідношенням , і отримаємо формулу включень-виключень для міри.

Тотожність максимумів і мінімумів

Формула включень-виключень може розглядатися як окремий випадок тотожності максимумів і мінімумів:

Це співвідношення справедливо для довільних чисел . В окремому випадку, коли ми отримуємо одну з форм принципу включень-виключень. Справді, якщо покласти , де  — довільний елемент із , то отримаємо співвідношення для індикаторних функцій множин:

Обертання Мебіуса

Нехай  — кінцева множина, і нехай  — довільна функція, визначена на сукупності підмножин , яка приймає дійсні значення. Визначимо функцію наступним співвідношенням:

Тоді має місце наступна формула звернення[9] [10]:

Це твердження є окремим випадком загальної формули обертання Мебіуса для алгебри інцидентності сукупності всіх підмножин множини , частково впорядкованих по відношенню включення .

Покажемо, як з цієї формули отримати принцип включення-виключення для скінченних множин. Нехай дано сімейство підмножин скінченної множини , позначимо  — множина індексів. Для кожного набору індексів визначимо як число елементів, що входять тільки в ті множини , для яких . Математично це можна записати так:

Тоді функція , яка визначається формулою

описує кількість елементів, кожний з яких входить у всі множини , і, бути може, ще в інші. Тобто

Зауважимо далі, що  — кількість елементів, що не володіють жодною з властивостей:

З урахуванням зроблених зауважень запишемо формулу обернення Мебіуса:

Це є в точності формула включень-виключень для скінченних множин, тільки в ній не згруповані доданки, пов'язані з однаковим значенням .

Див. також

  • Формула Грассмана
  • Нерівність Буля

Примітки

  1. Ріордан Дж. Введення в комбінаторний аналіз = An Introduction to Combinatorial Analysis. — 289 с.
  2. Weisstein, Eric W. Derangement(англ.) на сайті Wolfram MathWorld.
  3. Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  4. Ріордан Дж. Введення в комбінаторний аналіз = An Introduction to Combinatorial Analysis. — М. : Вид-во іноземної літератури, 1963. — 289 с.
  5. Холл М. Комбінаторика = Combinatorial Theory. — 424 с.
  6. Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  7. Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  8. Боровков, А. А. Теорія ймовірностей. — 2-е вид. — 431 с.
  9. Холл М. Комбінаторика = Combinatorial Theory. — 424 с.
  10. Стенлі Р. Перечислительная комбинаторика = Enumerative Combinatorics. — 440 с.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.