Задача про екіпаж корабля
Якщо варіанти вибору залежать від того, які об’єкти були обрані раніше, то такий процес зручно відобразити у вигляді “дерева”. На першому кроці з однієї точки відкладається стільки ліній, скільки існує можливих виборів на першому кроці. На кінцях кожної лінії також проводять стільки додаткових ліній, скільки можна зробити на другому кроці і т. д. В результаті буде намальовано свого роду дерево або граф. Комбінаторика і теорія може звучати досить заплутано і незрозуміло, тому розглянемо на прикладі.
Перед початком експедиційного року у керівництва стоїть завдання – зібрати екіпажі для поїздок. Кожна команда повинна включати в себе три людини: командир, інженера і лікаря. При цьому кількість фахівців у тій чи іншій галузі може змінюватись. Припустимо, наприклад, щоб у дві різні експедиції вирушав один лікар, т. к. лікарів всього двоє, а командирів і інженерів може бути по троє. При цьому укладачеві експедиційного плану необхідно враховувати психологічну сумісність членів команди. Дана характеристика є однією з найбільш важливих в довгих і далеких експедиціях для їх успішного проведення. Виходячи з усіх описаних умов, вимальовується наступна картина:
Де ai – командири, bi – інженери і ci – лікарі. При цьому в ході тестування кожної людини було з’ясовано, що командир a1 психологічно добре ладнає з інженерами b1 і b3, a2 – з b1 і b2, а ось лікар c3 несумісний з інженером b1 і т. д. Питання, які спочатку ставилося перед керівником проекту – скільки екіпажів можна скласти при таких умовах. З складеної діаграми видно, що всього таких екіпажів може бути 10. Але що було б, якщо питання про психологічної сумісності не мав ваги? Тоді виходить, що після вибору командирів ai, існувало б по 3 альтернативи для кожного з них у виборі інженера. Відповідно, для пари командира та інженера також було б 3 варіанти лікарів. Тоді кількість комбінацій досягне 4*3*3 = 36 екіпажів.
