L. Fregimus Vacerro (fregimus) wrote,
L. Fregimus Vacerro
fregimus

Деревянная задача

Возможно, что это классическая комбинаторная задача, но что-то никак не припомню, кто бы ее рассматривал. Меня некоторое время назад спросили об этом; ответа у меня не было. С тех пор я над ней думал время от времени.

Вопрос: сколько различных бинарных деревьев с n листьями можно построить? Обозначим число возможных деревьев как T(n).

Все возможные деревья для n=2; 3; 4

Видно, что T(2)=1, T(3)=2, T(4)=5. А в общем виде? Лучше в закрытой форме, чем в рекуррентной, конечно.

Если просто помните решение, пока не говорите, но пообсуждать было бы очень интересно. Не уверен, что мой способ решения достаточно красив.
Tags: math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 23 comments