主題
Search

弱二叉樹

下載 Mathematica 筆記本下載 Wolfram 筆記本

弱二叉樹是一種有根樹，其中所有非根圖頂點最多與三個圖頂點相鄰。

WeaklyBinaryTrees

設

g(z)=sum_(i=0)^inftyg_iz^i,
(1)

為節點數為 i 的弱二叉樹數量的生成函式，其中

g_0=0
(2)
g_1=g_2=g_3=1
(3)
g_(2i+1)=sum_(j=1)^(i)g_(2i+1-j)g_j
(4)
g_(2i)=1/2g_i(g_i+1)+sum_(j=1)^(i-1)g_(2i-j)g_j.
(5)

這給出了序列 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, ... (OEIS A001190)，有時也稱為 Wedderburn-Etherington 數。

Otter (Otter 1948, Harary and Palmer 1973, Knuth 1997) 證明了

lim_(n->infty)(g_nn^(3/2))/(xi^(n-1))=eta,
(6)

其中

xi=2.48325...
(7)

(OEIS A086317; Knuth 1997, p. 583; Finch 2003, p. 297) 是方程的唯一正根

g(1/x)=1,
(8)

和

eta=0.7916032...
(9)

(OEIS A086318; Knuth 1997, p. 583). xi 也由快速收斂的極限給出

xi=lim_(n->infty)c_n^(2^(-n)),
(10)

其中 c_n 由下式給出

c_0=2
(11)
c_n=c_(n-1)^2+2,
(12)

其前幾項為 6, 38, 1446, 2090918, 4371938082726, ... (OEIS A072191)，給出

eta=1/2sqrt(xi/pi)sqrt(3+1/(c_1)+1/(c_1c_2)+1/(c_1c_2c_3)+...).
(13)

另請參閱

二叉樹, 有根樹, 強二叉樹, 樹

使用 探索

參考文獻

Comtet, L. 高階組合數學：有限和無限展開的藝術，修訂和擴充版。 Dordrecht, Netherlands: Reidel, p. 55, 1974.Cyvin, S. J. et al. . "多烯烴的同分異構體計數。" J. Molec. Structure (Theorochem.) 357, 255-261, 1995.Etherington, I. M. H. "非結合冪和一個函式方程。" Math. Gaz. 21, 36-39 and 153, 1937.Etherington, I. M. H. "關於非結合組合。" Proc. Royal Soc. Edinburgh 59, 153-162, 1938-39.Finch, S. R. "奧特的樹計數常數。" §5.6 in 數學常數。 Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Franklin, J. N. and Golomb, S. W. "研究非線性遞迴序列的函數理論方法。" Pacific J. Math. 56, 467, 1975.Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1969.Harary, F. and Palmer, E. M. 圖計數。 New York: Academic Press, 1973.Knuth, D. E. 計算機程式設計藝術，第 1 卷：基本演算法，第 3 版。 Reading, MA: Addison-Wesley, 1997.Olds, C. D. "問題 4277：遺傳代數。" Amer. Math. Monthly 56, 697-699, 1949.Otter, R. "樹的數量。" Ann. Math. 49, 583-599, 1948.Sloane, N. J. A. 序列 A001190/M0790 A072191, A086317, 和 A086318 在 "整數序列線上百科全書" 中。Stanley, R. P. Problem 6.52 in 計數組合學，第 2 卷。 Cambridge, England: Cambridge University Press, 1999.Wedderburn, J. H. M. "函式方程 g(x^2)=2ax+[g(x)]^2。" Ann. Math. 24, 121-140, 1922-1923.

在 中被引用

弱二叉樹

引用為

Weisstein, Eric W. "弱二叉樹。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/WeaklyBinaryTree.html

主題分類