Как известно, связный граф без циклов называется деревом. Требуется найти количество деревьев, у которых n пронумерованных вершин, причём степень каждой вершины (кроме висячих вершин) равна 3.

Два дерева считаются различными, если существуют две такие вершины с номерами u и v, что в одном дереве есть ребро между u и v, а в другом — нет.