Формули перерахунку для основних типів комбінаторних з’єднань

З’єднання	Без повторен ь елемент ів	З повторен нями елемент ів
Перестановки
Розміщення
Сполучення

Тема№3

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

 

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

Введемо ряд позначень.

 – кількість об'єктів множини , які володіють властивістю ;

 – кількість об'єктів, що не володіють властивістю ;

 – кількість об'єктів, що володіють двома властивостями  одночасно;

 – кількість об'єктів, що володіють трьома властивостями  одночасно;

 – кількість об'єктів, що володіють усіма  властивостями множини  одночасно;

 – кількість об'єктів, що не володіють ні одним з  властивостей множини .

 

Теорема 4

Доведення.

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

Наприклад:

На фірмі працює 67 співробітників. З них 47 володіють англійською мовою, 35 – німецькою, 20 – французькою; одночасно англійською та німецькою володіють – 23 співробітника, англійською та французькою – 12, німецькою та французькою – 11, трьома мовами володіють 5 співробітників. Скільки співробітників не володіють ні однією із перерахованих мов?

Розв’язання.

Визначимо наступні властивості:

 – "володіти англійською мовою”;

 – "володіти німецькою мовою;

 – "володіти французькою мовою".

За формулою включень і виключень маємо:

 

Окремі випадки формули включень і виключень

1. Якщо всі властивості  попарно несумісні, тобто

то формула включень і виключень має вигляд:

2. Якщо кожне число  залежить не від характеру властивостей, а лише від їх кількості, то формула має вигляд:

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

 

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

Нехай є множина  

Розглянемо перестановки елементів множини .

Елемент перестановки називається нерухомим, якщо , тобто елемент стоїть на своєму місці.

Наприклад.

При  у перестановці  – елемент  – нерухомий, а у перестановці  – усі елементи нерухомі.

Безладом називається перестановка, яка не має нерухомих елементів, тобто

Постановка за дачі

Визначити  – кількість безладів у -елементній множині, або кількість перестановок чисел  таких, що .

Розв’язання.

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

:

Аналогічно, визначимо  – кількість перестановок, у яких рівно два елементи знаходяться на своїх місцях:  та, відповідно,  – кількість перестановок, у яких тільки  елементів знаходяться на своїх місцях: .

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

 

Розпишемо формулу

 – ще називають субфакторіалом.

 

Зада ча про зустріч

Визначити кількість таких перестановок чисел , що точно  елементів із  знаходяться на своїх місцях (тобто ), а інші , перебувають у безладі.

Інакше: нас цікавлять перестановки, в яких рівно  елементів нерухомі.

Розв’язання.

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