Inmathematics andcomputer science, theWedderburn–Etherington numbers are aninteger sequence named afterIvor Malcolm Haddon Etherington^[1][2] andJoseph Wedderburn^[3] that can be used to count certain kinds ofbinary 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)

These numbers can be used to solve several problems incombinatorial enumeration. Thenth number in the sequence (starting with the number 0 forn = 0)counts

• The number of unorderedrooted trees withn leaves in which all nodes including the root have either zero or exactly two children.^[4] These trees have been called Otter trees,^[5] after the work of Richard Otter on their combinatorial enumeration.^[6] They can also be interpreted as unlabeled and unrankeddendrograms with the given number of leaves.^[7]
• The number of unordered rooted trees withn nodes in which the root has degree zero or one and all other nodes have at most two children.^[4] 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. Inchemical graph theory, these trees can be interpreted asisomers ofpolyenes with a designated leaf atom chosen as the root.^[8]
• The number of different ways of organizing asingle-elimination tournament forn players (with the player names left blank, prior to seeding players into the tournament).^[9] 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${\displaystyle x^n}$ for a binary multiplication operation that is assumed to becommutative but neitherassociative noridempotent.^[4] For instance${\displaystyle x^5}$ can be grouped into binary multiplications in three ways, as${\displaystyle x(x(x(xx)))}$,${\displaystyle x((xx)(xx))}$, or${\displaystyle (xx)(x(xx))}$. This was the interpretation originally considered by both Etherington^[1][2] and Wedderburn.^[3] An Otter tree can be interpreted as a grouped expression in which each leaf node corresponds to one of the copies of${\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 thefreecommutative magma on one generator${\displaystyle x}$ (the tree with one node). In this algebraic structure, each grouping of${\displaystyle x^n}$ has as its value one of then-leaf Otter trees.^[10]

The Wedderburn–Etherington numbers may be calculated using therecurrence relation

${\displaystyle a_{2n-1}=\sum _{i=1}^{n-1}{a}_i{a}_{2n-i-1}}$

${\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${\displaystyle a_1=1}$.^[4]

In terms of the interpretation of these numbers as counting rooted binary trees withn 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 ofn 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.^[7]

The Wedderburn–Etherington numbers growasymptotically as

${\displaystyle a_n\approx \sqrt{\frac{\rho +{\rho }^2{B}^{\prime }({\rho }^2)}{2\pi }}\frac{{\rho }^{-n}}{n^{3/2}},}$

whereB is thegenerating function of the numbers andρ is itsradius of convergence, approximately 0.4027 (sequenceA240943 in theOEIS), and where the constant given by the part of the expression in the square root is approximately 0.3188 (sequenceA245651 in theOEIS).^[11]

Young & Yung (2003) use the Wedderburn–Etherington numbers as part of a design for anencryption system containing a hiddenbackdoor. When an input to be encrypted by their system can be sufficientlycompressed byHuffman coding, it is replaced by the compressed form together with additional information that leaks key data to the attacker. In this system, the shape of the Huffman coding tree is described as an Otter tree and encoded as a binary number in the interval from 0 to the Wedderburn–Etherington number for the number of symbols in the code. In this way, the encoding uses a very small number of bits, the base-2 logarithm of the Wedderburn–Etherington number.^[12]

Farzan & Munro (2008) describe a similar encoding technique for rooted unordered binary trees, based on partitioning the trees into small subtrees and encoding each subtree as a number bounded by the Wedderburn–Etherington number for its size. Their scheme allows these trees to be encoded in a number of bits that is close to the information-theoretic lower bound (the base-2 logarithm of the Wedderburn–Etherington number) while still allowing constant-time navigation operations within the tree.^[13]

Iserles & Nørsett (1999) use unordered binary trees, and the fact that the Wedderburn–Etherington numbers are significantly smaller than the numbers that count ordered binary trees, to significantly reduce the number of terms in a series representation of the solution to certaindifferential equations.^[14]

• Catalan number
• Cryptography
• Information theory

• Finch, Steven R. (2003),Mathematical constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge: Cambridge University Press, pp. 295–316,doi:10.1017/CBO9780511550447,ISBN 978-0-521-81805-6,MR 2003519.

• Integer sequences
• Trees (graph theory)
• Graph enumeration

• Articles with short description
• Short description is different from Wikidata