Eine Baumschule
Eine Folge von
zueinander passenden Klammern wird Liste
genannt, wenn ein Klammernpaar alle anderen Klammern umfasst.
Eine Liste wie die folgende
((()(())())((()())))
kann zu einem Busch aufgeblasen werden.
Und der Busch vertrocknet dann zu einem Baum.
() ()()
()( )() ( )
( )( )
( )
O O O
| \ /
O O O O
\|/ |
O O
\ /
O
Natürlich kann man umgekehrt jeden Baum in eine Liste verwandeln
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]
Der Wald im ersten Abschnitt enthält nicht alle Bäume sondern nur die, die "wirklich"
verschieden sind.
(Erstaunlicherweise finden das Leute interessant, die sich mit Differentialgleichungen
beschäftigen.)
Die beiden folgenden Bäume
O O O O O O
\ / | | \ /
O O O O O O O O
| \|/ \|/ |
O O O O
\ / \ /
O O
sind nicht "wirklich" verschieden, weil man bloß ein paar Zweige verdrehen muss,
um aus dem einen den anderen zu machen. Sie heißen deshalb isomorph.
Wie schafft man viele Bäume aus dem Wald, so dass im aufgeräumten Wald keine isomorphen Bäume
mehr stehen?
Der Vorschlag, erst alle Bäume wachsen zu lassen und dann alle isomorphen Bäume
auszureißen, wird natürlich wegen Grausamkeit strikt zurückgewiesen.
Wir ziehen die Bäume deshalb durch gezieltes Propfen heran.
Aus zwei Bäumen
O O
\ /
O
+
O O O
\|/
O
|
O
erzeugen wir einen neuen, indem wir den linken Baum auf die unterste Gabelung des
rechten Baumes pfropfen:
O O
\ /
O
\
O O O
\|/
O
/
O
Für die dazugehörenden Listen heißt das, dass die erste Liste am Anfang der
zweiten Liste eingesetzt wird:
(()()) + ((()()())) = ((()())(()()()))
Um den ganzen gewünschten Wald aufzuforsten, muss man jetzt noch darauf aufpassen,
dass man auf einen Stamm niemals einen Pfropf setzt, der größer als derjenige Teilbaum ist,
der sein rechter Nachbar werden würden.
Nach dieser Regel ist das obige Pfropfen erlaubt.
Aber wenn man die beiden Bäume vor dem Pfropfen vertauscht, kriegt man
O O O
\|/
O
|
O O O
\|/
0
Dieser Baum wäre im Wald unerwünscht. (Sein Spiegelbild würde aber
regelgemäß dort wachsen.)
Man braucht noch eine zusätzliche Regel: Auf den ersten und einfachsten Baum ()
darf jeder andere Baum gepfropft werden.
Bemerkungen
Um sich im Dschungel aller Bäume zurechtzufinden, kann man die Bäume
nummerieren, indem man den dazugehörenden Listen wie folgt eine Nummer gibt:
((()(())())((()())))
11101100100111010000
Zu jeder Liste kann man auch eine Menge wie folgt betrachten
((()(())())((()())))
{{{}{{}}{}}{{{}{}}}}
und bemerken, dass isomorphe Bäume zu gleichen derartigen Mengen
gehören - was erst mal nicht viel zur Herstellung des gewünschten Waldes nützt.
Arboretum Mustila
Arboretum de Villardebelle
Arboretum Trompenburg
Arboretum Göttingen
[1] Becker,J.: Checking Quickly the Order of a Runge-Kutta-Nyström Method for y''=f(x,y). ZAMM 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.
an Josef Gräf, der mir solche Bäume vorstellte.