Комбінаторні правила суми та добутку

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

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

ПРАВИЛО ДОДАВАННЯ

Якщо дві взаємовиключні події можуть бути виконані відповідно k та m способами, тоді якусь одну з цих подій можна виконати k+m способами.

Приклад 1. З міста А в місто В можна добратися 12 потягами, 3 літаками, 23 автобусами. Скількома способами можна добратися з міста А у місто В?

Розв'язання. Проїзд з А у В на потягу, літаку або автобусом є подіями, які не можуть виконуватися одночасно однією людиною (взаємовиключними), тому загальну кількість маршрутів можна обчислити сумуванням способів пересування
N=12+3+23=38.
В цьому і полягає правило додавання.

ПРАВИЛО МНОЖЕННЯ

Нехай дві виконувані одна за одною дії можуть бути здійснені відповідно k та m способами. Тоді обидві вони можуть бути виконані k*m способами.

Приклад 2. У турнірі беруть участь 8 команд з хокею. Скільки існує способів розподілити перше, друге та третє місця?

Розв'язання. Відповідно до умови аналіз призових місць має бути наступним:
перше місце займе одна з 8 команд, друге – одна з 7, третє – одна з 6, оскільки кожна з них не може претендувати одночасно на два призових місця. Тому таких способів буде
N=8*7*6=336
Обидва правила узагальнюються на випадок будь-якої скінченної кількості дій.

Перегляньте презентацію до теми уроку: