Математикадан республикалық олимпиада, 2014-2015 оқу жылы, 9 сынып

Пирамида түріндегі $n+1$ деңгейлі толық ағаш берілген. Түбір (1-ші деңгей) мен ең соңғы ($(n+1)$-ші) деңгейдегі нүктелерден басқа қалған деңгейлердегі әр нүктеден төмен қарай екі қабырға шығады, және төбеден бір қабырға кіреді. 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}$$