主题
Search

有根树

下载 Mathematica Notebook下载 Wolfram Notebook
RootedTrees

有根树是一种 树，其中一个特殊的（“标记的”）节点被 выделен 出来。这个节点被称为树的“根”或（较少见的）“始祖”。有根树等价于有向树 (Knuth 1997, pp. 385-399)。未被确定根的树有时被称为 自由树，尽管不加限定的术语“树”通常指自由树。

根 顶点 度 为 1 的有根树被称为 种植树。

对于 n=1, 2, ...，n 个节点的有根树的数量为 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, ... (OEIS A000081)。将具有 n 个节点的有根树的数量表示为 T_n，则 生成函数 为

T(x)=sum_(n=0)^(infty)T_nx^n
(1)
=x+x^2+2x^3+4x^4+9x^5+20x^6+48x^7+115x^8+286x^9+719x^(10)+....
(2)

这个 幂级数 满足

T(x)=xexp[sum_(r=1)^(infty)1/rT(x^r)]
(3)
t(x)=T(x)-1/2[T^2(x)-T(x^2)],
(4)

其中 t(x) 是无根 树 的 生成函数。生成函数 T_n 可以使用包含序列本身的乘积写成：

xproduct_(n=1)^infty1/((1-x^n)^(T_n))=sum_(n=1)^inftyT_nx^n.
(5)

有根树的数量也可以从 递推关系 计算得出

T_(i+1)=1/isum_(j=1)^i(sum_(d|j)T_dd)T_(i-j+1),
(6)

其中 T_0=0 和 T_1=1，其中第二个求和是对所有 d 整除 j 的 除数 d 进行的 (Finch 2003)。

正如 Otter (1948) 所示，

alpha=lim_(n->infty)(T_n)/(T_(n-1))
(7)
=2.955765...
(8)

(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396)，其中 alpha 由 正 根 的唯一值给出

T(1/x)=1.
(9)

如果 T_n 是 n 个节点上的非同构有根树的数量，则 T_n 的渐近级数 由下式给出

T_n∼alpha^nn^(-3/2)(0.4399240125...+(0.0441699018...)/n+(0.2216928059...)/(n^2)+(0.8676554908...)/(n^3)+...),
(10)

其中常数可以用函数偏导数计算

F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y
(11)

(Plotkin 和 Rosenthal 1994; Finch 2003)。

另请参阅

自由树, 有序树, 种植树, 红黑树, 有根图, 树, 弱二叉树

使用 Wolfram|Alpha 探索

参考文献

Borwein, J. 和 Bailey, D. 实验数学：21世纪的似真推理。 Wellesley, MA: A K Peters, p. 22, 2003.Finch, S. R. "Otter 的树计数常数。" §5.6 in 数学常数。 Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Finch, S. "两个渐近级数。" December 10, 2003. http://algo.inria.fr/bsolve/.Harary, F. 图论。 Reading, MA: Addison-Wesley, pp. 187-190 和 232, 1994.Harary, F. 和 Palmer, E. M. "有根树。" §3.1 in 图计数。 New York: Academic Press, pp. 51-54, 1973.Knuth, D. E. 计算机程序设计艺术，第 1 卷：基本算法，第 3 版。 Reading, MA: Addison-Wesley, 1997.Nijenhuis, A. 和 Wilf, H. 计算机和计算器的组合算法，第 2 版。 New York: Academic Press, 1978.Odlyzko, A. M. "渐近计数方法。" In 组合数学手册，第 2 卷 (Ed. R. L. Graham, M. Grötschel, 和 L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.Otter, R. "树的数量。" Ann. Math. 49, 583-599, 1948.Plotkin, J. M. 和 Rosenthal, J. W. "如何从生成函数满足的解析恒等式中获得序列的渐近展开式。" J. Austral. Math. Soc. Ser. A 56, 131-143, 1994.Pólya, G. "论图像文字。" Amer. Math. Monthly 63, 689-697, 1956.Ruskey, F. "关于有根树的信息。" http://www.theory.csc.uvic.ca/~cos/inf/tree/RootedTree.html.Sloane, N. J. A. "整数序列在线百科全书"中的序列 A000081/M1180 和 A051491。Wilf, H. S. 组合算法：更新。 Philadelphia, PA: SIAM, 1989.

在 Wolfram|Alpha 中被引用

有根树

请引用为

Weisstein, Eric W. "有根树。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/RootedTree.html

主题分类