Республиканская олимпиада по математике, 2015 год, 9 класс

Дано дерево полного пирамидального вида, которое состоит из ${n+1}$ уровней, и из каждой вершины исходит два ребра вниз и входит одно ребро сверху (при этом в самую верхнюю вершину уровня 1 не входит ни одно ребро, а из вершин последнего $(n+1)$-го уровня не исходят рёбра). На рисунке ниже пример показан для $n = 3$.
Сколько существует способов раскрасить ребра данного дерева в заданные $2^n$ цветов (каждое ребро покрашено в один цвет) так, чтобы для каждого цвета все рёбра, покрашенные в этот цвет, составляли путь из некоторой вершины в вершину последнего уровня? (Путь — это последовательность вершин, где каждая следующая вершина соединена ребром с предыдущей и находится уровнем ниже. )

( Д. Елиусизов )

Комментарий/решение

Ответ: $(2^n )!\cdot 2^{2^n-2}$.

Решение. Разобьем каждое дерево на левое и правое поддерево. Выбрать $2^{n-1}$ цветов для левого поддерева можно ${2^n \choose 2^{n-1}}$ способами. Каждое поддерево имеет в два раза больше способов раскраски, чем дерево с $n$ уровнями (за счет торчащего сверху ребра). Получим рекуррентное соотношение: $F_n={2^n \choose 2^{n-1}}\cdot (2F_{n-1})^2$. Решив и упростив его получим ответ.

Заметим, что на последнем уровне вершин - $2^n$ и в каждую из них входит по одному ребру. Цветов тоже $2^n$ и никакие два ребра не имеют одинаковых цветов, поэтому определить цвета этих рёбер можно ($2^n$)! способами. А теперь вершин на $n$ уровне - $2^{n-1}$ и в каждую входит по ребру и каждое ребро может иметь один из двух цветов, в которых покрашены два ребра, исходящие из него. Способов - $2^{2^{n-1}}$.

Аналогично для $n-1$ уровня - $2^{2^{n-2}}$ способов и т.д. для 2 уровня - $2^2$

Всего-$$(2^n)!*2^{2^{n-1}}*2^{2^{n-2}}*...*2^2=(2^n)!*2^{2^{n-1}+2^{n-2}+...+2^2}=(2^n)!*2^{2^n-2}$$