主題
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)。

另請參閱

自由樹, 有序樹, 種植樹, 紅黑樹, 有根圖, 樹, 弱二叉樹

使用 探索

參考文獻

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.

在 中被引用

有根樹

請引用為

Weisstein, Eric W. "有根樹。" 來自 Web 資源。 https://mathworld.tw/RootedTree.html

主題分類