弱二叉树

弱二叉树是一种有根树，其中所有非根图顶点最多与三个图顶点相邻。

设

(1)

为节点数为的弱二叉树数量的生成函数，其中

			(2)
			(3)
			(4)
			(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) 证明了

(6)

其中

(7)

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

(8)

和

(9)

(OEIS A086318; Knuth 1997, p. 583). 也由快速收敛的极限给出

(10)

其中由下式给出

			(11)
			(12)

其前几项为 6, 38, 1446, 2090918, 4371938082726, ... (OEIS A072191)，给出

(13)

另请参阅

二叉树, 有根树, 强二叉树, 树

使用 Wolfram|Alpha 探索

更多尝试

参考文献

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. "函数方程

。" Ann. Math. 24, 121-140, 1922-1923.

在 Wolfram|Alpha 中被引用

弱二叉树

引用为

Weisstein, Eric W. "弱二叉树。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/WeaklyBinaryTree.html

弱二叉树

另请参阅

使用 Wolfram|Alpha 探索

参考文献

在 Wolfram|Alpha 中被引用

引用为

主题分类