Number of trees with 5 unlabeled nodes

hbghlyj

ma116 notes
我们知道，一个具有5个顶点的树必须有4条边。而且，任何具有4条边的图的总度数（缩写TD）必须为8。
因此，我们的问题变成了找到所有使得具有5个顶点的树的TD为8的方法，并且每个顶点的度数≥ 1。
1，1，1，1，4  

将最后一个顶点的度数4减1，并分给度数为1的顶点得到：
1，1，1，2，3  

再次将最后一个顶点的度数减1，并分给度数为1的顶点得到：
1，1，2，2，2  

我们无法再做更多了。这些是三个等价类。

我们之前讨论过的“星号和竖线”方法在这里也适用吗？
答案是否定的。
我们有5个顶点，它们是我们的“类别”，这给出了4个“竖线”。每个类别已经至少有一个“星号”，因为我们有度数≥ 1的顶点。
\begin{array}c
顶点1 &| &顶点2 &| &顶点3 &|& 顶点4 &|& 顶点5\\
*&| &*& |& *& |&&|& **\end{array}因此，我们必须在这$n = 5$个类别中分配三个额外的“星号”，得到：
$$C(5-1 + 3, 3) = C(7, 3) = 35$$
因此，这比我们上面的3要多得多！
但是，我们没有考虑到每个等价类中度数的排列。基本上，哪个顶点获得额外的“星号”并不重要。
例如，在1，1，4，1，1和1，1，1，1，4之间没有区别。因此，有5个可能的度数为4的顶点。
在1，1，1，2，3中，有$5\times 4 = 20$种可能的配置来找到度数为2和3的顶点。
最后，在1，1，2，2，2中，有$C(5,3) = 10$种度数为2的5个顶点的组合。
如果我们将这些可能性相加，我们得到$5 + 20 + 10 = 35$，这正是我们预期的结果。“星号和竖线”过多计数，因为它不将顶点视为不可区分的。

hbghlyj

A000055 Number of trees with $n$ unlabeled nodes.
上面是a(5)=3.
       
a(1) = 1 [o];
a(2) = 1 [o-o];
a(3) = 1 [o-o-o];
a(4) = 2 [o-o-o and o-o-o-o]
            |
            o

hbghlyj

图论计数
6 Jun 2023 — 题目大意：求有min 个结点的分别满足下列性质的树的方案数。 有标号有根树A000169。 有标号无根树A000272。 无标号有根树A000081。 无标号无根 ...

hbghlyj

hbghlyj 发表于 2023-7-16 22:41
ma116 notes
将最后一个顶点的度数4减1，并分给度数为1的顶点得到：

这里用到了Havel-Hakimi Algorithm