Pull to refresh

Comments 12

Вы выбрали для произвольных деревьев и для двоичных разные способы подсчёта. Произвольных деревьев с 2 вершинами бесконечно много. Два 2-ичных дерево, три 3-ичных, четыре 4-ичных и т.д.
Данная статья — перевод на русский статьи Эрика Липперта. Такого рода вопросы — это к нему.
Вы путаете n-арное дерево и дерево общего вида (произвольное).

В n-арном дереве потомки имеют порядок (позицию): 1й, 2й, 4й, n-й. Какие-то позиции могут отсутствовать точно также, как в двоичном может не быть правого или левого потомка.

В произвольном дереве просто есть список потомков.
Если уж говорить совсем честно, то надо смотреть на неориентированые графы. Тогда двоичное дерево это просто деверо со степенями вершин не больше трёх. И тогда ответ очевиден.

Стоило бы уточнить определения перед тем, как пытаться шокировать широкую публику.
Очевидно, что это не может быть совпадением.

Гм, конечно не может.
Давайте будем искать F(n) — число двоичных деревьев из n вершин. Предположим, что мы умеем решать задачи меньшей размерности чем n. Пусть в левом поддереве i вершин, тогда в правом (n-1-i) — значит всего таких деревьев F(i)*F(n-1-i). Число i изменяется от 0 до n-1, а значит ответ — сумма указаных произведений для i от 0 до n-1, что совпадает с формулой числа Каталана, что и требовалось.
Перечитал статью с утра и понял, что число двоичных деревьев искалось в прошлой статье (хотя почему-то не обосновалось). Потому мой комментарий надо отправить к туда. :-)

Очень понравилось, кстати, превращение произвольных неизоморфных деревьев в двоичные «с точки зрения структур данных». Если держать его в голове, то обоснование выше легко превращается в искомое C(n-1).
Интересная статья.
А блоки из Тетриса на картинках специально?
Всё же, надо заметить, что в математике дерево — это связный граф без циклов. И два дерева (собственно, как и просто два графа) считаются изоморфными, если можно пронумеровать вершины обоих так, что если вязть два номера, то вершины под этими номера одновременно соединены или не соединены ребром в обоих деревьях (графах). Поэтому 2, 3 и 4 деревья у Вас на рисунке — изоморфны, т.е., неразличимы с точки зрения теории графов.
Поэтому имеет смысл уточнить, что здесь считается произвольным деревом.
Only those users with full accounts are able to leave comments. Log in, please.