Weakly Binary Tree

A weakly binary tree with at least two graph vertices is a planted tree in which all nonroot graph vertices are adjacent to at most three graph vertices. By convention, the one-vertex rooted tree is also counted as a degenerate weakly binary tree.

Let

(1)

be the generating function for the number of weakly binary trees on nodes, where

			(2)
			(3)
			(4)
			(5)

Here the recurrences for and apply for integers . This gives the sequence 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, ... (OEIS A001190), sometimes also known as the Wedderburn-Etherington numbers.

Otter (1948) showed that (Harary and Palmer 1973, Knuth 1997)

(6)

where

(7)

(OEIS A086317; Knuth 1997, p. 583; Finch 2003, p. 297) is the unique positive root of

(8)

and

(9)

(OEIS A086318; Knuth 1997, p. 583). is also given by the rapidly converging limit

(10)

where is given by

			(11)
			(12)

for integers in the recurrence. The values are 6, 38, 1446, 2090918, 4371938082726, ... (OEIS A072191), giving

(13)