Число корневых деревьев

[cyb12]

Рассматриваются ориентированные корневые деревья, у которых ребра идут "по направлению к корню". Степень входа каждой вершины $\le$2. Всего внутренних (не листьев) вершин p, а листьев t. Как оценить, сколько всего таких различных деревьев?

[Хорхе]

1. Деревья планарные? То есть эти два:

   |             | 
  / \           / \
    |          |

(корень сверху) отличаются?

2. Вершины пронумерованы?

[cyb12]

1. Под различными понимались попарно не изоморфные. А разве деревья не всегда планарные?

2. Вершины не пронумерованы. То есть на Изоморфизм накладывается условие только перехода корня в корень.

[Хорхе]

1. Если деревья планарные, то два нарисованных мной дерева отличаются. Смысл этого названия такой - непланарное дерево можно вынуть из плоскости, перемешать ветки и положить обратно.

-- Пн мар 22, 2010 14:21:29 --

2. Я так понимаю, под "степенью" Вы все же понимаете исходящую степень, иначе Ваши деревья - линейные графы

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

дмвл = метка листа + (метка вершины)x(дмвл + неупорядоченная пара дмвл)

Это легко переводится на язык производящих функций (переменная $z$ отмечает вершины, $u$ --- листья):

$$ D(z,u) = u + z(D(z,u) + N(z,u)), $$

где $N(z,u)$ -- производящая функция неупорядоченных пар дмвл. В свою очередь, каждой упорядоченной паре дмвл (их производящая функция, очевидно, $D^2(z,u)$) соответствует две неупорядоченные пары, если деревья разные и одна (=две-одна) пара одинаковых дмвл (у таких пар производящая функция $D(z^2,u^2)$), если деревья одинаковые. Таким образом, $D^2(z,u) = 2N(z,u) - D(z^2,u^2)$. Окончательно имеем

$$ D(z,u) = u + z( D(z,u) + D^2(z,u)/2 + D(z^2,u^2)/2), $$

можно отсюда выразить $D(z,u) = F(z,u,D(z^2,u^2))$ и уже работать с этим. Например, можно написать рекуррентную формулу с небольшой глубиной рекурсии (за счет $z^2$ и $u^2$) и эффективно считать. Можно проводить асимптотический анализ, но это дело гораздо сложнее.

-- Пн мар 22, 2010 14:34:14 --

Еще есть слабая надежда угадать решение: посчитать несколько последовательных приближений по схеме

$$D_0(z,u) = 0, D_n(z,u) = u + z(D_{n-1}(z,u) + D_{n-1}^2(z,u)/2 + D_{n-1}(z^2,u^2)/2), $$

вдруг что-то знакомое получится, потом попробовать доказать догадку.

[Хорхе]

Посмотрел OEIS, ничего (кроме коэффициентов при младшей степени $z$ около $u^k$, которые, очевидно, равны количеству бинарных деревьев с $k$ листьями; я считал листья тоже вершинами, в этом случае немного другая рекуррентная формула).