(((()()())()()()(()())))
1 Intro
1.1 Trees and lists
1.2 A list of trees

2 How does it work?
2.1 Isomorphic trees
2.2 Grafting

3 What else?
3.1 Links to trees
3.2 References
3.3 Thanks

Deutsche Version

© Johannes Becker

Growing Trees

1.1 Trees and lists

A sequence of matching brackets is called a list, if a pair of brackets enclose all other brackets. A list like

can be blown up to a bush and the bush can be dehydrated to a tree

()()() ()() ( )()()()( ) ( ) ( )
 
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
 
O O O O O \|/ \ / O O O O O \ \ // / O | O
 
(((()()())()()()(()())))

It's obvious that you can turn a tree into a list, going backwards.

1.2 A list of trees

O
()
1: [,]
O | O
(())
2: [1,1]
O O \ / O
(()())
3: [1,2]
O | O | O
((()))
4: [2,1]
O O O \|/ O
(()()())
5: [1,3]
O | O O \ / O
(()(()))
6: [1,4]
O O \ / O | O
((()()))
7: [3,1]
O | O | O | O
(((())))
8: [4,1]
O O O O \\ // O
(()()()())
9: [1,5]
O | O O O \|/ O
(()()(()))
10: [1,6]
O O \ / O O \ / O
(()(()()))
11: [1,7]
O | O | O O \ / O
(()((())))
12: [1,8]
O O | | O O \ / O
((())(()))
13: [2,4]
O O O \|/ O | O
((()()()))
14: [5,1]
O | O O \ / O | O
((()(())))
15: [6,1]
O O \ / O | O | O
(((()())))
16: [7,1]
O | O | O | O | O
((((()))))
17: [8,1]

Ok, trees!

2.1 Isomorphic trees

The forests in section 1 do not contain all trees, only those that are "really" different.
(Surprisingly, people involved in differential equations are keen on listing only those trees.)

The following two trees

O O O O O O \ / | | \ / O O O O O O O O | \|/ \|/ | O O O O \ / \ / O O
are not "really" different, because you just twist some branches to turn one tree into the other. They are called isomorphic.

How do you get rid of a lot of trees, so that the reduced forest doesn't contain any two isomorphic trees?

The method of growing all trees and eradicating the isomophorpic trees is, of course, rejected as beeing utterly cruel. We grow the desired trees directly by grafting.

2.2 Grafting

Given two trees like

O O \ / O
+
O O O \|/ O | O
we create a new one by grafting the left tree to the lowest knot of the right tree:
O O \ / O \
O O O \|/ O / O
Speaking in terms of lists, grafting means inserting the first list at the beginning of the second list:
(()()) + ((()()())) = ((()())(()()()))
In order to get the desired forest, you just have to pay attention, that you never graft a tree which is greater than the subtree that becomes its right neighbour. According to this rule the grafting example above is o.k. But if you exchange the two trees above before grafting, you get
O O O \|/ O | O O O \|/ 0
It would be illegal to add this tree to the forest. (The mirror image of this tree would grow according to the rule.)

You need just one additional rule: the first and most simple tree () can be used as a trunk to be grafted with any other tree.

Remarks

To find your way through the jungle of all trees, we put them in order. The associated list gets a number like this:
((()(())())((()())))
11101100100111010000
We associate to every trees list a set like
((()(())())((()())))
{{{}{{}}{}}{{{}{}}}}
and notice that isomorphic trees go with identical sets - which unfortunately doesnt help a lot in getting the desired forest.

3.1 Links to trees

Arboretum Mustila
Arboretum de Villardebelle
Arboretum Trompenburg
Arboretum Göttingen

3.2 References

[1] Becker,J.: Checking Quickly the Order of a Runge-Kutta-Nyström Method for y''=f(x,y). Z. angew. Math. Mech. 71 (1991) 3, 190.
[2] Filippi,S.; Gräf,J.: Ein Programm zur Aufstellung und Überprüfung der Bedingungsgleichungen für Runge-Kutta-Nyström-Verfahren unter Verwendung der Theorie von Hairer-Wanner. Mitt. Math. Sem. Gießen 173 (1986), 42-57.

3.3 Thanks

To Josef Gräf, who introduced me to this kind of trees.

Baum