Теорема о числе упорядоченных корневых деревьев

Число упорядоченных корневых деревьев с ребрами не превосходит .

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

Число кодов не превосходит общего числа слов длины , состоящих из и , которое равно . Таким образом, число упорядоченных корневых деревьев с ребрами не превосходит .