[math-fun] Enumerating trees

17 Dec 2010

      I have found an interesting bijection between trees (binary trees, not
Christmas trees!) and natural numbers, allowing numbers to be
displayed as trees, and trees to be associated with numbers. This gives
a nice, fun alternative to our positional notation for writing numbers.

The rules are very simple:

* Let the single-point tree, (), be designated the value 0.

* Let the tree (XY) be designated the value ((x+y)Â²+3x+y+2)/2, where
x and y are the values corresponding to the trees X and Y, respectively.

In full parenthetic notation, the first few trees are:

0 ()
1 (()())
2 (()(()()))
3 ((()())())
4 (()(()(()())))
5 ((()())(()()))
...

Using the more compact notation of expressing () as * and (XY) as
#XY, the trees then become:

0 *
1 #**
2 #*#**
3 ##***
4 #*#*#**
5 ##**#**
...

And removing the final asterisk results in:

0 (empty string)
1 #*
2 #*#*
3 ##**
4 #*#*#*
5 ##**#*
...

This also serves as an enumeration of Dyck words.

Now, if we replace # with ( and * with ), we have an enumeration of
parenthetic statements:

0 (empty string)
1 ()
2 ()()
3 (())
4 ()()()
5 (())()
...

This gives us another enumeration of trees (this time, not restricted to
binary trees). For example, the balanced ternary tree:

(()()())(()()())(()()())

can be reverse-engineered into the Dyck word:

##*#*#**##*#*#**##*#*#**

and the binary tree:

##*#*#**##*#*#**##*#*#***

with the full parenthetic expansion:

((()(()(()())))((()(()(()())))((()(()(()())))())))

So, this is a simple bijection between the set of binary trees and the
set of all trees, without having to convert to and from integer notation.

We can go further, by allowing more than one type of root node (and
slightly altering the 'composition' formula). Letting K = 0, S = 1, and
`XY = ((x+y)Â²+3x+y+4)/2, we have the following:

0 K
1 S
2 `KK
3 `KS
4 `SK
5 `K`KK
...

Ooh, an enumeration of SK-calculus supercombinators. This gets
interesting!

(` denotes the application operator)

We can express I as `S`KK, or 9. `S`II then becomes 16389. The
number 537231422 corresponds to the irreducible term, ``S`II`S`II.

However, this is not very efficient for unbalanced binary trees. The
fixed-point combinator, Y', becomes:

20330403641472985212299390532838786314945647725862859321210046999865821897931

(This is larger than the order of the Monster Group, but smaller
than the number of atoms in the Universe.)

So, this is a programming language, where each valid program is an
integer, and vice-versa. The rules for an interpreter are as follows, in
pseudocode:

(WARNING: May not be suitable for programmers who insist on
elegance!)

combinator interpret(int n)
{

combinator r;

if (n == 0)
{
r = K;
}

if (n == 1)
{
r = S;
}

if (n > 1)
{

int a = 0;

while ((n - (2 + a))*8 + 1 is not a perfect square) // A beautiful test for 
triangular numbers!
{
increment a; // Exit when n - (2 + a) is a triangular number.
}

b = (sqrt((n - (2 + a))*8 + 1)-1)/2 - a; // This retrieves the side length 
of a triangular number.

r = apply(interpret(a),interpret(b)) // Recursively call the interpreter on 
the two sub-terms.

}

return r; // Return the combinator corresponding to the value, n.

}

Merry Christmas!

Sincerely,

        Adam P. Goucher