Wedderburn–Etherington number explained

The Wedderburn–Etherington numbers are an integer sequence named for Ivor Malcolm Haddon Etherington[1] [2] and Joseph Wedderburn[3] 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

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

xn

for a binary multiplication operation that is assumed to be commutative but neither associative nor idempotent.[4] For instance

x5

can be grouped into binary multiplications in three ways, as

x(x(x(xx)))

,

x((xx)(xx))

, or

(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

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

(the tree with one node). In this algebraic structure, each grouping of

xn

has as its value one of the n-leaf Otter trees.[10]

Formula

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

a2n-1

n-1
=\sum
i=1

aia2n-i-1

a2n=

an(an+1)
2
n-1
+\sum
i=1

aia2n-i

beginning with the base case

a1=1

.[4]

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

Growth rate

The Wedderburn–Etherington numbers grow asymptotically as

an\sqrt{

\rho+\rho2B'(\rho2)
2\pi
} \frac,where B is the generating function of the numbers and ρ is its radius of convergence, approximately 0.4027, and where the constant given by the part of the expression in the square root is approximately 0.3188 .[11]

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

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]

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

See also

Further reading

Notes and References

  1. .
  2. .
  3. .
  4. .
  5. .
  6. .
  7. .
  8. .
  9. .
  10. This equivalence between trees and elements of the free commutative magma on one generator is stated to be "well known and easy to see" by .
  11. .
  12. .
  13. .
  14. .