找到可以从给定节点集形成的不同未标记树的公式是什么？
我刚刚对一个项目进行研究，遇到了一个问题。如果有人能帮助我解决这个问题，我将非常感激。考虑下图：
由一条线连接的两个点仅产生一个图表，由单个点连接的三个点线也能得到一个图形，无论你如何连接点，结果都是一样的。但当我们增加点时，就会出现不同的可能性，如四个点所示。
是否有一个公式来计算一组节点可以形成的未标记树的数量？
I am just doing a research on a project and came across a problem. I would be very grateful if anybody could help me out with this. Consider the figure below:
Two dots joined by a line results in only one diagram, three dots joined by single lines also results in one figure no matter how you join the dots, the result is the same. But as we increase the dots there are different possibilities, as seen with four dots.
Is there a formula for counting the number of unlabeled trees that can be formed from a set of nodes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
正如评论中所建议的，您的问题可以表述为确定 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 。它给出了最多十个顶点的树的一些计数和图像。
As suggested in the comments, your question can be phrased as determining the number of unlabeled trees on n vertices. Notice this differs significantly from the question of counting labeled trees (of which there are n^{n-2}) or labeled graphs (of which there are 2^\binom{n}{2}).
The Online Encyclopedia of Integer Sequences has a lot of good data about this problem (including code to generate the sequence): https://oeis.org/A000055. In particular, it gives a generating function A(x) for these numbers, which is the best solution known to date (from a mathematician's perspective):
A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2x^3 + ...
If you are not familiar with generating functions, think of it as a carefully designed polynomial whose coefficients form the desired sequence. That is, the coefficient of x^n in this polynomial would be the number of unlabeled trees on n vertices.
As a final plug, you may find this reference useful: http://austinmohr.com/work/trees. It gives some counts and images for trees of up to ten vertices.
这是非同构图计数问题。
对于一般情况，在
n个顶点上有 2^(n2) 个非同构图，其中 (n 2) 是二项式系数“n 以上 2”。然而，这可能会给你一些额外的图表，具体取决于哪些图表被认为是相同的（你也不是 100% 清楚哪些图表适用）。
查看本文.
以及关于 MathWorld 的这篇文章。
编辑：如果您想计算标记树的数量，则公式为
n^(n-2)。维基百科。
This is non-isomorphic graph count problem.
For general case, there are 2^(n2) non-isomorphic graphs on
nvertices where (n2) is binomial coefficient "n above 2".However that may give you also some extra graphs depending on which graphs are considered the same (you also were not 100% clear which graphs do apply).
See this paper.
And this article on MathWorld.
EDIT: In case you want to count labeled trees only the formula is
n^(n-2).Wikipedia.