math - 找到可以从给定节点集形成的不同未标记树的公式是什么？

Question

我只是在做一个项目的研究，遇到了一个问题。如果有人能帮我解决这个问题，我将不胜感激。考虑下图:



两点连成一个图，三个点连成一个图，不管怎么连，结果都是一样的。但是随着我们增加点数，就会出现不同的可能性，如四个点所示。

是否有计算可以从一组节点形成的未标记树的数量的公式？

Answer 1

正如评论中所建议的，您的问题可以表述为确定 n 个顶点上未标记树的数量。请注意，这与计算标记树(其中有 n^{n-2} 个)或标记图(其中有 2^\binom{n}{2} 个)的问题有很大不同。

整数序列在线百科全书有很多关于这个问题的好资料(包括生成序列的代码):https://oeis.org/A000055 .特别是，它给出了这些数字的生成函数 A(x)，这是迄今为止已知的最佳解决方案(从数学家的角度来看):

A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2，其中 T(x) = x + x^2 + 2x^3 + ...

如果您不熟悉生成函数，请将其视为精心设计的多项式，其系数形成所需的序列。也就是说，该多项式中 x^n 的系数将是 n 个顶点上未标记树的数量。

作为最后的插件，您可能会发现此引用很有用:http://austinmohr.com/work/trees .它为最多十个顶点的树提供了一些计数和图像。