Bernoulli Number - A Binary Tree Representation

A Binary Tree Representation

The Stirling polynomials σ_n(x) are related to the Bernoulli numbers by B_n = n!σ_n(1). S. C. Woon (Woon 1997) described an algorithm to compute σ_n(1) as a binary tree.

Woon's recursive algorithm (for n ≥ 1) starts by assigning to the root node N = . Given a node N = of the tree, the left child of the node is L(N) = and the right child R(N) = . A node N = is written as ± in the initial part of the tree represented above with ± denoting the sign of a_1.

_{Given a node N the factorial of N is defined as}

_{Restricted to the nodes N of a fixed tree-level n the sum of 1/N! is σn(1), thus}

For example B₁ = 1!(1/2!), B₂ = 2!(−1/3! + 1/(2!2!)), B₃ = 3!(1/4! − 1/(2!3!) − 1/(3!2!) + 1/(2!2!2!)).