Основні правила комбінаторики
Отже, комбінаторні задачі бувають різних видів. Проте більшість з них використовує 2 основних правила комбінаторики – правило суми і правило добутку.
Правило суми. Якщо деякий об’єкт можна вибрати способами, а інший об’єкт можна вибрати способами, то вибір „ або ” можна здійснити способами.
При використанні правила суми треба слідкувати, щоб жоден із способів вибору об’єкта не співпадав з будь-яким способом вибору об’єкта . Якщо ж такі співпадіння існують, правило суми втрачає силу, і ми отримаємо лише способів вибору, де – кількість співпадінь.
Правило добутку. Якщо деякий об’єкт можна вибрати способами і при кожному виборі об’єкта а інший об’єкт можна вибрати способами, то вибір пари „ і ” можна здійснити способами.
Наочно правило добутку можна продемонструвати за допомогою таблиці чи матриці:
.
Узагальнене правило добутку. Якщо об’єкт можна вибрати способами, об’єкт – способами і т.д., об’єкт – способами, то вибір впорядкованої системи об’єктів (кортежу) можна здійснити способами.
Приклад. Нехай з пункту до пункту існує доріг, з пункту до пункту – доріг, з пункту до пункту – доріг, а з пункту до пункту – доріг. Пункти і між собою дорогами не сполучені. Скількома способами можна пройти з пункту до пункту ?
Дата добавления: 2014-12-22; просмотров: 3099;