2015-05-20
539
Число упорядоченных корневых деревьев с 
ребрами не превосходит 
.
Доказательство. Так как между упорядоченными корневыми деревьями и их кодами существует биекция, то их число равно числу кодов деревьев. Код дерева с ребрами – слово длины 
, состоящее из нулей и единиц.
Число кодов не превосходит общего числа слов длины , состоящих из 
и 
, которое равно 
. Таким образом, число упорядоченных корневых деревьев с ребрами не превосходит .
