Количество видов цепочек

[0101]

Есть N различных сегментов. Из них можно содать набор из N(N-1)/2 двухсегментных звеньев. Из элементов этого набора нужно собрать цепочку из N-1 звеньев, причем сединять можно только сегменты одного типа.
Например можно соединить одинаковые сементы звеньев AB, BC, CD, DE и AB, AC, AD, DE.
По списку количеств использованных в цепочке различных сегментов (для AB, BC, CD, DE это 2,2,2,1,1, для AB, AC, AD, DE-3,2,111) ее можно отнести к некоторому виду.
Существует ли математический аппарат для определения количества видов возможных цепочек для произвольного N?

[Xaositect]

Вторая цепочка выглядит так? $\xymatrix{&C\ar@{-}[d]&&\\B\ar@{-}[r]&A\ar@{-}[r]&D\ar@{-}[r]&E}$

Каждая цепочка - это дерево, вид цепочки - это набор степеней его вершин (в $A$ входят три ребра, в $D$-две). Причем по любому дереву с $n$ вершинами можно построить цепочку.
То есть, надо найти, сколько различных наборов степеней вершин может быть у дерева с $n$ вершинами.

Вот есть вообще количество деревьев: http://www.research.att.com/~njas/sequences/A000055
Но это не совсем то, что Вам нужно: деревья $\xymatrix{&C\ar@{-}[d]&&F\ar@{-}[d]&\\B\ar@{-}[r]&A\ar@{-}[r]&D\ar@{-}[r]&E\ar@{-}[r]&G}$ и $\xymatrix{&C\ar@{-}[d]&F\ar@{-}[d]&&\\B\ar@{-}[r]&A\ar@{-}[r]&D\ar@{-}[r]&E\ar@{-}[r]&G}$ неизоморфны, но имеют один вид.

Сейчас подумаю еще.

-- Вт янв 12, 2010 15:32:54 --

Так.
Сумма степеней вершин дерева равна удвоенному количеству ребер, т.е $2v-2$, где $v$ - количество вершин.
Вроде бы разбиение $2v-2$ реализуется тогда и только тогда, когда $\sum(d_i - 2) = -2$ (каждая иершина степени $>2$ добавляет "ветки", на которых висят листья, имеющие степень 1).

-- Вт янв 12, 2010 15:37:45 --

Если то, что я написал раньше, правда, то искомое число видов цепчек с $v$ буквами равно количеству разбиений $v-2$, т.е. http://www.research.att.com/~njas/sequences/A000041 с еще двумя единицами в начале.

[0101]

Xaositect в сообщении #279728 писал(а):

Вторая цепочка выглядит так? $\xymatrix{&C\ar@{-}[d]&&\\B\ar@{-}[r]&A\ar@{-}[r]&D\ar@{-}[r]&E}$

Спасибо!
Да, вторая цепочка может быть так представлена. Но уточненный вариант 1, 1, 2, 3, 5, 7, 11... получается без учета цепочек такого вида.

[Xaositect]

0101 в сообщении #279742 писал(а):

Но уточненный вариант 1, 1, 2, 3, 5, 7, 11... получается без учета цепочек такого вида.

Не понял?

[0101]

Для двух типов сегментов - 1 цепочка
Для 3- х - 1 цепочка
Для 4-х -3
....
Для 7 у меня 19 получилось

[Sashamandra]

0101 в сообщении #279722 писал(а):

Есть N различных сегментов.

А я не понял условие. Есть N различных сегментов или есть N различных типов сегментов? В условии сказано, что все сегменты различны. Как же тогда можно соединять A с A?

[Xaositect]

Так Вам что нужно посчитать?
Для 7 - 11 различных деревьев (могу нарисовать), 7 различных видов: (22222 11), (3 222 111), (33 2 1111), (4 22 1111), (4 3 11111), (5 2 11111), (6 111111).
А если еще расположение букв учитывать - то получается гораздо больше 19, только на прямой цепочке 2520

[0101]

Xaositect в сообщении #279756 писал(а):

Так Вам что нужно посчитать?
Для 7 - 11 различных деревьев (могу нарисовать), 7 различных видов: (22222 11), (3 222 111), (33 2 1111), (4 22 1111), (4 3 11111), (5 2 11111), (6 111111).
А если еще расположение букв учитывать - то получается гораздо больше 19, только на прямой цепочке 2520

Для 4-х нарисуйте, пожалуйста

[Xaositect]

$\xymatrix{A\ar@{-}[r]&B\ar@{-}[r]&C\ar@{-}[r]&D}$ и $\xymatrix{&D\ar@{-}[d]&\\A\ar@{-}[r]&B\ar@{-}[r]&C\ar@{-}[r]}$. Остальные - это то же самое с точностью до соответствия вершин (изоморфизма графов).

[0101]

Спасибо!
Я понял, что получилось. Нужно уточнить. В цепочке может быть меньше чем N видов сегментов. Там, наверное, не только деревья. Еще цепочка, которую можно замкнуть АВ-ВС-СА. Как такие можно учесть?

[Xaositect]

если цепочки можно замыкать, то это уже произвольные графы получаются.
Для ровно 4 вершин тогда получается еще $\xymatrix{A\ar@{-}[r]\ar@{-}[d]&B\ar@{-}[d]\\C\ar@{-}[r]&D}$

А вот такая вещь будет цепочкой?
$\xymatrix{A\ar@{-}[r]\ar@{-}[d]&B\ar@{-}[r]\ar@{-}[d]&C\ar@{-}[d]\\D\ar@{-}[r]&E\ar@{-}[r]&F}$

А вот такая? Этот граф нельзя расположить на плоскости, чтобы ребра не пересекались
$\xymatrix{A\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]&B\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&C\ar@{-}[dll]\ar@{-}[dl]\ar@{-}[d]\\D&E&F}$

[0101]

Есть, наверное, правило и для цепочек с циклическими вкраплениями. Хорошо, что частично уже можно оценить количество цепочек. А количество деревьев растет экспоненциально?

[Xaositect]

Да, экспоненциально.

-- Вт янв 12, 2010 17:26:49 --

В общем, я думаю, Вам стоит поточнее определить понятие цепочки.

[0101]

Мне теперь понятно, в какую сторону двигаться. Спасибо за помощь!

[0101]

Уточненный вариант формулировки количества цепочек.
Нужно определить количество видов графов с одинаковым количеством ребер N. Граф относим к виду, определяемому по списку количеств соединенных ребер для каждой вершины. Одну пару вершин может соединять только одно ребро.