Возможное количество бинарных деревьев поиска, которые могут быть созданы с помощью N ключей, определяется N-м каталонским номером. Зачем?

Это беспокоило меня некоторое время. Я знаю, что при заданных N ключах в виде дерева двоичного поиска возможное количество деревьев, которые можно создать, соответствует N-му числу изКаталонская последовательность.

Я пытался определить, почему это так; неспособный найти что-либо, что могло бы даже попытаться объяснить это интуитивно, я прибегаю к коллективному знанию SO. Я нашел другие способы вычисления количества возможных деревьев, но они казались менее интуитивными, и не было предложено никаких объяснений, кроме как их использовать. Кроме того, на вики-странице (эта ссылка выше) даже показано изображение возможных древовидных образований с 3 ключами, что заставило бы меня подумать:хорошее и аккуратное объяснение, которое нужно услышать (что, разумеется, не включено в статью).

Заранее спасибо!

Ответы на вопрос(3)

Ваш ответ на вопрос