Основні правила комбінаторики

Отже, комбінаторні задачі бувають різних видів. Проте більшість з них використовує 2 основних правила комбінаторики – правило суми і правило добутку.

Правило суми. Якщо деякий об’єкт можна вибрати способами, а інший об’єкт можна вибрати способами, то вибір „або ” можна здійснити способами.

При використанні правила суми треба слідкувати, щоб жоден із способів вибору об’єкта не співпадав з будь-яким способом вибору об’єкта . Якщо ж такі співпадіння існують, правило суми втрачає силу, і ми отримаємо лише способів вибору, де – кількість співпадінь.

Правило добутку. Якщо деякий об’єкт можна вибрати способами і при кожному виборі об’єкта а інший об’єкт можна вибрати способами, то вибір пари „і ” можна здійснити способами.

Наочно правило добутку можна продемонструвати за допомогою таблиці чи матриці:

.

Узагальнене правило добутку. Якщо об’єкт можна вибрати способами, об’єкт – способами і т.д., об’єкт – способами, то вибір впорядкованої системи об’єктів (кортежу) можна здійснити способами.

Приклад. Нехай з пункту до пункту існує доріг, з пункту до пункту – доріг, з пункту до пункту – доріг, а з пункту до пункту – доріг. Пункти і між собою дорогами не сполучені. Скількома способами можна пройти з пункту до пункту ?

Дата добавления: 2014-10-17