In mathematics and computer science, the Wedderburn–Etherington numbers are an integer sequence named after Ivor Malcolm Haddon Etherington and Joseph Wedderburn that can be used to count certain kinds of binary trees. The first few numbers in the sequence are
0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... (OEIS: A001190)
Combinatorial interpretation
These numbers can be used to solve several problems in combinatorial enumeration. The nth number in the sequence (starting with the number 0 for n = 0) counts
The number of unordered rooted trees with n leaves in which all nodes including the root have either zero or exactly two children. These trees have been called Otter trees, after the work of Richard Otter on their combinatorial enumeration. They can also be interpreted as unlabeled and unranked dendrograms with the given number of leaves. The number of unordered rooted trees with n nodes in which the root has degree zero or one and all other nodes have at most two children. Trees in which the root has at most one child are called planted trees, and the additional condition that the other nodes have at most two children defines the weakly binary trees. In chemical graph theory, these trees can be interpreted as isomers of polyenes with a designated leaf atom chosen as the root. The number of different ways of organizing a single-elimination tournament for n players (with the player names left blank, prior to seeding players into the tournament). The pairings of such a tournament may be described by an Otter tree. The number of different results that could be generated by different ways of grouping the expression x n {\displaystyle x^{n}} for a binary multiplication operation that is assumed to be commutative but neither associative nor idempotent. For instance x 5 {\displaystyle x^{5}} can be grouped into binary multiplications in three ways, as x ( x ( x ( x x ) ) ) {\displaystyle x(x(x(xx)))} , x ( ( x x ) ( x x ) ) {\displaystyle x((xx)(xx))} , or ( x x ) ( x ( x x ) ) {\displaystyle (xx)(x(xx))} . This was the interpretation originally considered by both Etherington and Wedderburn. An Otter tree can be interpreted as a grouped expression in which each leaf node corresponds to one of the copies of x {\displaystyle x} and each non-leaf node corresponds to a multiplication operation. In the other direction, the set of all Otter trees, with a binary multiplication operation that combines two trees by making them the two subtrees of a new root node, can be interpreted as the free commutative magma on one generator x {\displaystyle x} (the tree with one node). In this algebraic structure, each grouping of x n {\displaystyle x^{n}} has as its value one of the n-leaf Otter trees.
Formula The Wedderburn–Etherington numbers may be calculated using the recurrence relation
a 2 n − 1 = ∑ i = 1 n − 1 a i a 2 n − i − 1 {\displaystyle a_{2n-1}=\sum _{i=1}^{n-1}a_{i}a_{2n-i-1}}
a 2 n = a n ( a n + 1 ) 2 + ∑ i = 1 n − 1 a i a 2 n − i {\displaystyle a_{2n}={\frac {a_{n}(a_{n}+1)}{2}}+\sum _{i=1}^{n-1}a_{i}a_{2n-i}}
beginning with the base case a 1 = 1 {\displaystyle a_{1}=1} . In terms of the interpretation of these numbers as counting rooted binary trees with n leaves, the summation in the recurrence counts the different ways of partitioning these leaves into two subsets, and of forming a subtree having each subset as its leaves. The formula for even values of n is slightly more complicated than the formula for odd values in order to avoid double counting trees with the same number of leaves in both subtrees.
Growth rate The Wedderburn–Etherington numbers grow asymptotically as
… excerpt ends here. Continue reading the full article.
