Решение комбинаторных задач перебором вариантов
В комбинаторных задачах нужно найти число всех способов (вариантов), удовлетворяющих условию. Чтобы не пропустить ни один вариант и не повторить ни одного, их записывают упорядоченно, например в порядке возрастания или группируя по первому элементу. Другое удобное средство — дерево вариантов: из корня проводят ветвь для каждой возможности первого выбора, а из каждой из них — ветви для следующего выбора; число конечных вершин дерева равно числу всех вариантов. Когда составляют числа из цифр, условие говорит, разрешены ли повторения.
| Выбор | Число |
|---|---|
| порядок важен (капитан и помощник) | 4 · 3 = 12 |
| порядок не важен (пара) | 4 · 3 : 2 = 6 |
Для занятия кружка нужны день и время: понедельник, среда или пятница; утро или день. Дерево имеет 3 ветви, каждая из которых делится на 2, что даёт всего 6 вариантов.
Составитель расписания рассматривает все способы расставить уроки, составитель меню подсчитывает возможные наборы блюд, а тренер подсчитывает возможные составы команды.
Нарисуйте дерево всех возможных исходов при двукратном подбрасывании монеты. Сколько всего исходов?
| A | B | D | G | |
|---|---|---|---|---|
| A | — | AB | AD | AG |
| B | BA | — | BD | BG |
| D | DA | DB | — | DG |
| G | GA | GB | GD | — |
«Нарисуй дерево»: группы рисуют на доске дерево вариантов обеда из двух соков и трёх видов выпечки и считают все виды обеда.