Скажем, что дерево с выделенным корнем и упорядоченными списками сыновей для каждой вершины сбалансированное, если все расстояния от корня до листьев равны. Найдите количество различных сбалансированных деревьев из $$$n$$$ вершин. Два дерева считаются различными, если им соответствует разные скобочные последовательности.

Более подробно, каждое дерево можно представить в виде скобочной последовательности. Для этого определим функцию $$$f$$$ следующим образом:

• если $$$x$$$ — лист, то $$$f(x) = ()$$$;
• иначе $$$f(x) = (f(\texttt{сын 1}) f(\texttt{сын 2}) ... f(\texttt{сын n}))$$$.

Значение функции $$$f$$$ от корня и даст соответствующую скобочную последовательность.