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, ... ()

Combinatorial interpretation

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

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.
  • 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 <math>x^n</math> for a binary multiplication operation that is assumed to be commutative but neither associative nor idempotent.

Formula

The Wedderburn–Etherington numbers may be calculated using the recurrence relation

:<math>a_{2n-1}=\sum_{i=1}^{n-1} a_i a_{2n-i-1}</math>

:<math>a_{2n}=\frac{a_n(a_n+1)}{2}+\sum_{i=1}^{n-1} a_i a_{2n-i}</math>

beginning with the base case <math>a_1=1</math>.

Applications

use the Wedderburn–Etherington numbers as part of a design for an encryption system containing a hidden backdoor. When an input to be encrypted by their system can be sufficiently compressed by Huffman 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.

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.

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 certain differential equations.

See also

  • Catalan number
  • Cryptography
  • Information theory

References

Further reading

  • .