Какие существуют методы решения задач по комбинаторике с помощью дерева вариантов?

Метод решения задач по комбинаторике с помощью дерева вариантов заключается в построении специальной схемы — дерева возможных вариантов. 12 Она похожа на перевёрнутое дерево, «корень» которого обозначается звёздочкой. 1

Порядок построения: 5

1. Из одной точки («корня дерева») проводят столько отрезков, сколько существует различных способов выполнить первое действие (каждый отрезок соответствует выбору конкретного способа выполнить действие). 5
2. Из конца каждого отрезка проводят столько отрезков, сколько существует способов выполнить второе действие, после выбора способа выполнить первое действие, соответствующего этому отрезку, и т. д.. 5
3. В результате такого построения получается «дерево», в n-ом ярусе которого количество вершин соответствует количеству способов выполнить цепочку действий до n-го шага включительно. 5

Пример решения задачи: 2 Петя, Коля и Вася решили съесть мороженое. 2 У мальчиков было одно клубничное, одно шоколадное, одно малиновое и одно вишнёвое мороженое. 2 Сколько вариантов выбора мороженого было у мальчиков? 2

Решение: обозначим клубничное мороженое буквой «к», шоколадное — буквой «ш», малиновое — буквой «м», вишнёвое — буквой «в». 2 Поскольку мы учтём все возможные варианты, то нам всё равно, в каком порядке мальчики будут выбирать мороженое. 2 Сначала проиллюстрируем все возможные варианты выбора Пети. 2 Теперь для каждого из вариантов выбора Пети проиллюстрируем все возможные варианты выбора Коли. 2 И наконец, для каждого из вариантов выбора Пети и Коли проиллюстрируем все возможные варианты выбора Васи. 2 Мы перебрали все возможные варианты. 2 Полученная схема и называется деревом возможных вариантов. 2 Осталось определить количество этих вариантов. 2 Для этого нужно посчитать количество вариантов в последней строке. 2

Ещё один метод решения комбинаторных задач — метод отрезков. 1 Он используется только для составления всевозможных пар. 1