Раскрашивание вершин цепочки и пропеллера в три цвета

Цепочка  — это дерево, все вершины которого, кроме двух вершин степени $1$, имеют степень $2$. Пропеллер  — это дерево, у которого есть одна вершина степени $3$, три вершины степени $1$, а остальные вершины имеют степень $2$. Правильный пропеллер  — это пропеллер, у которого вершины степени $1$ равноудалены от вершины степени $3$. В работе решается следующая задача: найти число способов раскрасить вершины цепочки или правильного пропеллера в три цвета, если задано число вершин каждого цвета.