2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Число корневых деревьев
Сообщение21.03.2010, 09:02 
Аватара пользователя
1. Деревья планарные? То есть эти два:
Код:
   |             |
  / \           / \
    |          |

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

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

 
 
 
 Re: Число корневых деревьев
Сообщение22.03.2010, 07:51 
1. Под различными понимались попарно не изоморфные. А разве деревья не всегда планарные?

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

 
 
 
 Re: Число корневых деревьев
Сообщение22.03.2010, 13:03 
Аватара пользователя
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), $$
вдруг что-то знакомое получится, потом попробовать доказать догадку.

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group