Что нет различных бинарных деревьев возможно с n помеченных узлов?

Question

В этой ссылке указано:

Для двоичного дерева с n узлами значение no.ребер n − 1.Таким образом, эта проблема может быть сведена к нет.способов, которыми мы можем сделать n − 1 ребер из n вершин.Ребро может быть сделано либо как левый потомок узла, либо как правый потомок.Следовательно, для n узлов у нас есть 2n возможностей для первого ребра, 2n − 1 для второго ребра и так далее.Таким образом, для n − 1 ребер общее число нет.путей

= 2n × (2n − 1) × (2n − 2) ×…. × (2n– (n – 2))

= 2n × (2n − 1) ×(2n − 2) ×…. × (n + 2)

= (2n)! / (N + 1)!

Я понял, что первое ребро может иметь2n возможностей, потому что для каждого узла есть левый и правый дочерние варианты.Я не могу понять, как второй край может иметь 2n-1 возможностей?

Каковы возможности для второго края, когда n = 3?

Answer 1

как второй край может иметь 2n-1 возможностей?

Было 2n возможностей, пока вы не добавили первое ребро.

После добавления первого ребра занята одна возможность, и осталось только 2n-1 возможностей.

После второго ребра осталось только 2n-2 возможности и т. Д.

Для n = 3 существует 6! / 4! = 30 вариантов. Просто проверьте: есть 5 конфигураций, каждая имеет 6 перестановок:

/\    /     /     \     \
     /      \     /      \