Wedderburn–Etherington number

In mathematics and computer science, the Wedderburn–Etherington numbers are an integer sequence named after Ivor Malcolm Haddon Etherington[1][2] and Joseph Wedderburn[3] that can be used to count certain kinds of binary trees.

[7] The Wedderburn–Etherington numbers grow asymptotically as where B is the generating function of the numbers and ρ is its radius of convergence, approximately 0.4027 (sequence A240943 in the OEIS), and where the constant given by the part of the expression in the square root is approximately 0.3188 (sequence A245651 in the OEIS).

[11] Young & Yung (2003) use the Wedderburn–Etherington numbers as part of a design for an encryption system containing a hidden backdoor.

[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.

Otter trees and weakly binary trees, two types of rooted binary tree counted by the Wedderburn–Etherington numbers