Количество способов организовать вершины в деревья

[aitap]

Дано $k$ вершин. Пронумеруем их числами от $1$ до $k$.

Задача: сколькими способами из них и вспомогательных вершин можно построить ациклический направленный граф, удовлетворяющий следующим условиям?

• Вспомогательные вершины соответствуют непустым подмножествам из $\{1, \dots, k\}$ и не повторяются.
• Единственная вершина, из которой выходят рёбра и в которую не входят рёбра, соответствует множеству всех чисел от $1$ до $k$.
• В вершины, соответствующие индивидуальным числам, рёбра входят, но не выходят.
• Если ребро выходит из вершины $A$ и входит в вершину $B$, то для соответствующих им множеств $A$ и $B$ верно $B \subsetneq A$, т.е. $B$ должна содержать часть, но не все элементы из $A$.
• Из вспомогательной вершины $\{1, \dots, k\}$ существует путь до каждой из вершин $1, \dots, k$.

Пример для $k = 3$:

• $\{ \{1,2,3\} \rightarrow 1, \{1,2,3\} \rightarrow 2, \{1,2,3\} \rightarrow 3 \}$
• $\{ \{1,2,3\} \rightarrow 1, \{1,2,3\} \rightarrow \{2,3\}, \{2,3\} \rightarrow 2, \{2,3\} \rightarrow 3 \}$
• $\{ \{1,2,3\} \rightarrow 2, \{1,2,3\} \rightarrow \{1,3\}, \{1,3\} \rightarrow 1, \{1,3\} \rightarrow 3 \}$
• $\{ \{1,2,3\} \rightarrow 3, \{1,2,3\} \rightarrow \{1,2\}, \{1,2\} \rightarrow 1, \{1,2\} \rightarrow 2 \}$

Насколько я могу судить, для $k=3$ ответ равен $4$. Если найдутся другие графы, удовлетворяющие условиям, возможно, мне придётся исправить условия.

Зачем всё это надо: выше приведена моя попытка перевести настоящую задачу на язык теории множеств в надежде, что это уже известный результат, который я пока не смог найти. Я занимаюсь бустингом в задачах классификации, в частности, моделями, в которых $k$ классов объединяют в меньшее количество классов (например, $5$ классов можно объединить в $2$ мета-класса $\{1,2\}$ и $\{3, 4, 5\}$), обучают классификационную модель (которая обычно лучше справляется с меньшим количеством классов), а после этого обучают дополнительные модели на подмножествах исходных классов (например, отличить класс $1$ от класса $2$, но не остальных, а также либо разделить классы $3, 4, 5$ сразу, либо предварительно объединить два самых трудноотличимых), пока не станет возможно определить исходные классы. Мне любопытно узнать, сколько всего есть способов так объединять классы, пока не получится серия классификационных моделей, дающих ответ в терминах исходных классов.

Я попробовал подойти к решению, посчитав, сколько всего есть способов объединить $k$ классов.
На каждой итерации можно либо решить закончить объединение (один способ), либо, если ещё осталось больше двух классов, выбрать 2 класса ($C_k^2$ способа) и объединить их. Получается простая рекурсивная формула:

$$ N(k) = 1 + \left\{ \begin{matrix} C_k^2 N(k - 1), & \text{ если } k > 2 \\ 1, & \text{ иначе} \end{matrix} \right. = 1 + \left\{ \begin{matrix} \sum_{i=k}^3 \prod_{j=k}^i C_j^2, & \text{ если } k > 2 \\ 0, & \text{ иначе} \end{matrix} \right. $$

(Если можно так записывать суммы и произведения по индексу, убывающему от $k$ до $3$ и от $k$ до $i$.)

К сожалению, если объединять классы именно таким образом и считать полученные варианты, объединения $\{\{1,2\}, \{3,4\}\}$ и $\{\{3,4\}, \{1,2\}\}$ будут посчитаны отдельно друг от друга, хотя являются одним и тем же способом объединить классы. И это я ещё не дошёл до подсчёта способов переразбить эти классы в дочерних моделях, пока не останутся индивидуальные классы.

Какие ещё подходы я могу применить, чтобы решить эту задачу?

[mihaild]

Это вроде бы получается ровно число деревьев с $k$ пронумерованными листьями (множество в вершине - листья, лежащие в её поддереве).
Эрдёш в An enumerative theory of trees доказывает, что деревьев с $n + 1$ вершинами и $k$ пронумерованными листьями ровно столько же, сколько способов разбить множество $\{1, \ldots, n\}$ на $n - k + 1$ непересекающихся множеств. Из этого ответ на вашу задачу выражается как сумма чисел Стирлинга, которую мне сходу неочевидно как упростить.

[aitap]

mihaild, спасибо за совет!

Для примера посчитаю деревья с $k=3$ листьями. Меня устраивают все деревья с $n+1 = k+1 =4$ вершинами (всего одно: $S( n, n - k + 1) = S(3, 1) = 1$), а также все (?) деревья с $n + 1 = 2k - 1 = 5$ вершинами, которых... $S(4, 2) = 7$? Хмм. Смотрю определение деревьев, которые считаю:

Erdős, Székely, "Applications of antilexicographic order. I. An enumerative theory of trees". Advances in Applied Mathematics, 10(4), 488-496, 1989 писал(а):

A semilabelled tree is a rooted tree on $n + 1$ vertices with $k$ leaves. The leaves are labelled with the numbers $1,2, \dots , k$. (Although the root may have degree one, it is never to be considered as a leaf.) We refer to the vertices differing from leaves and root as branching points. They are unlabelled. The out-degree of a vertex is the number of its descendants,i.e., the number of neighbours, except the one in the root direction.

Какие ещё бывают деревья с $5$ (включая корень) вершинами и $3$ листьями, кроме $3$ деревьев следующего вида?


Нашёл: одно вида и три вида . Итого, действительно, семь. Есть ли способы исключить из рассмотрения деревья, у которых out-degree любой вершины (branching points или корня) равен $1$?

[Geen]

aitap в сообщении #1547551 писал(а):

Вспомогательные вершины соответствуют непустым подмножествам из $\{1, \dots, k\}$ и не повторяются.

Это же не означает, что эти множества не могут пересекаться?...
Кроме того, циклов может и не быть, но могут ли быть "shortcut'ы"?

Может быть нужно добавить требование, что выходящие рёбра соответствуют некоторому разбиению?

[aitap]

Geen в сообщении #1547593 писал(а):

Это же не означает, что эти множества не могут пересекаться?...

Они могут пересекаться, но дважды использовать одно и то же множество нельзя.

Geen в сообщении #1547593 писал(а):

Кроме того, циклов может и не быть, но могут ли быть "shortcut'ы"?

Что именно это значит? С одной стороны, "shortcut'ом" можно назвать случай, когда из вершины $\{1,\dots,k\}$ (корня дерева) выходит ребро сразу в вершину $\{k\}$ (лист дерева). Это разрешено. С другой стороны, если в лист или branching point входит более чем одно ребро, такое дерево не разрешено.

Geen в сообщении #1547593 писал(а):

Может быть нужно добавить требование, что выходящие рёбра соответствуют некоторому разбиению?

Если из $A$ выходят рёбра в вершины $\{B_i\}$, то попарные пересечения последних должны быть пусты $B_i \cap B_j = \emptyset \; \forall i \ne j$, а их же объединение должно давать $A$: $\bigcup_i B_i = A$, плюс к тому, что $B_i \subsetneq A$. Насколько я понимаю, это правило должно запретить деревья с out-degree любой вершины, равным $1$.

[aitap]

В той же статье была доказана интересная теорема. Пусть $n_i$ задают количества вершин с out-degree, равным $i$. Отметим, что $n_0 = k$ - число листьев дерева (только из них не выходят рёбра), а также что мы можем задать $k$ как верхнюю границу для out-degree. Ещё отметим, что $\sum_{i=0}^k n_i = n+1$ - общее число вершин.

Тогда, если $k = 1 + \sum_{i=2}^m (i-1)n_i$, то количество деревьев с заданными количествами вершин соответствующего вида равно (теорема 10):

$$N(\{n_i\}) = \frac{n!}{\prod_{i=1}^k n_i! i!^{n_i}}$$

Потребуем $n_1 = 0$. Тогда для нахождения количества деревьев с $k$ листьями и $n+1$ вершинами достаточно просуммировать $N(\{n_i\})$ по всем $\{n_i \in \mathbb N \cup \{ 0 \}\}$, удовлетворяющим $\sum_{i=2}^k n_i = n+1-k$ и $\sum_{i=2}^k (i-1)n_i = k-1$, а для нахождения общего числа деревьев с требуемыми свойствами - просуммировать $N(n,k)$ по всем $n$ от $k$ до $2k-2$.

Я написал программу, которая перебирает целочисленные композиции $n$ в лоб (до длины $k-1$, дополняя нулями при необходимости). Она на удивление хорошо работает до $k=11$ (дальше не проверял). Вручную проверил случаи $k=3$ и $k=4$. Вроде бы, количества деревьев для $k=4$ получаются такие, как я ожидал: $1$ для $n=4$, $10$ для $n=5$ и $15$ для $n=6$.

Интересно, есть ли менее дурацкий способ посчитать $N(n,k)$, но любопытство более-менее удовлетворено.

[Geen]

aitap в сообщении #1547595 писал(а):

С другой стороны, если в лист или branching point входит более чем одно ребро, такое дерево не разрешено.

Понятно. Просто этого условия не было изначально.

[mihaild]

Тут видимо надо сказать, что граф не содержит даже неориентированных циклов.

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

[aitap]

Geen, спасибо! Это важное условие, я должен был упомянуть его раньше.

mihaild, Вам тоже спасибо. Ещё почитаю про разбиения на слагаемые, вдруг что найдётся.