На этом шаге мы рассмотрим число бинарных деревьев.
Число бинарных деревьев определяется, исходя из рекурсивного определения бинарного дерева: число деревьев с n вершинами определяется как сумма чисел возможных комбинаций левых и правых поддеревьев. Это дает возможность составить уравнения, решение которых и дает искомое число.
Обозначим tn - число различных бинарных деревьев, содержащих n вершин. Под различными деревьями мы понимаем в том числе учет свойства вершины быть левым или правым потомком. Таким образом, симметричные деревья, изоморфные с точки зрения теории графов, являются различными. Например, вырожденные деревья, представляющие собой цепи левых и правых потомков - различны с нашей точки зрения, хотя и изоморфны. Имеет место формула:
которую можно объяснить следующим образом.
Пусть tk обозначает количество возможных левых поддеревьев, содержащих k вершин, tn-k-1- количество соответствующих правых поддеревьев, содержащих n-k-1 вершину (k вершин в левом поддереве и одна вершина - корень). Левое поддерево может быть пустым, разумеется, существует только один вариант пустого дерева, т. е. t0=1. При этом в правом поддереве n-1 вершина и имеется tn способ построить такое дерево. Общее количество способов построить дерево, сохраняя заданное соотношение количеств вершин в левом и правом поддеревьях k и n-k-1, равно tktn-k-1. Суммируя по всем возможным значениям k, получаем количество tn деревьев с n вершинами.
Приведенное равенство можно использовать для итерационного вычисления количества деревьев, начиная с деревьев, содержащих одну вершину:
t1 = t0 = 1, t2 = t1t0 + t0t1 = 2, t3 = t0t2 + t1t1 + t2t0 = 5 и т.д.
В частности, t4 = 14, t5 = 42, t6 = 132, t7 = 429. Таким способом можно вычислить количество бинарных деревьев с любым числом вершин, но сложность и громоздкость вычислений возрастают с ростом n. Хотелось бы получить результат в виде явной зависимости tn от параметра n без использования значений tn-i.
Для этого используется производящая функция 
членов последовательности {tn}, где z - некая формальная переменная. Отыскивается
она следующим образом. Вместо суммы для tn запишем сумму для tn+1:
Правая часть принимает классический вид свертки двух последовательностей (в данном случае - это свертка последовательности {tn}
с самой собой) и ее производящая функция равна Т1(z) в соответствии с теорией z-преобразований.
Левая часть задает член последовательности {tn+1}, сдвинутой относительно последовательности
{tn} на одну позицию и ее производящая функция по правилам z-преобразований может быть определена как
(T(z)-t0) z-1 =T2(z)
для определения неизвестной функции T(z), которое имеет решение:
Разложение его в ряд по степеням z в районе точки z = 0 имеет вид:
Таким образом,
На следующем шаге мы рассмотрим число вырожденных деревьев.
