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

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

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

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

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

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

.

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

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








Дата добавления: 2014-12-22; просмотров: 3099;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.