« vorheriger Beitrag  · nächster Beitrag »

08.04.11 · 00:04 Uhr

Topologie von Flächen CLXII

Kategorie: Naturwissenschaften  ·  Kommentare: 3

"Nun ist die Frage generaliter: da ein polygonum von n Seiten durch n-3 diagonales in n-2 triangula zerschnitten wird, auf wie vielerley verschiedene Arten solches geschehen könne." (Euler an Goldbach)

Letzte Woche hatten wir beschrieben, wie man verschiedene Flächen in Dreiecke zerlegen ("triangulieren") kann.
Passend dazu ist mir diese Woche in der Bibliothek gerade das neue Buch Loera-Rambau-Santos:"Triangulations"
aufgefallen, in dem es zwar kaum um Topologie (sondern eher um Polytope und z.B. auch um Triangulierungen der Ebene) geht, aber dessen erstes Kapitel hier doch ganz gut als Einschub passt, bevor es nächste Woche wieder mit dem Schönflies-Theorem und Triangulierungen weitergeht.

Letzte Woche hatten wir z.B. Triangulierungen des 4-oder 8-Ecks benutzt, mit denen wir dan Triangulierungen des Torus bzw. der Brezel bekamen.

Man kann sich dann natürlich fragen, wieviele verschiedene Möglichkeiten es dafür gibt, also wieviel verschiedene Triangulierungen des 4- oder 8-Ecks, oder allgemein des n-Ecks. Diese Frage wird, quasi zum Aufwärmen, in Kapitel 1.1. des Buches von Loera-Rambau-Santos beantwortet.

Die Triangulierungen des 4-Ecks kann man leicht abzählen - es gibt 2 (nämlich 2 Möglichkeiten, eine Diagonale einzuzeichnen).
Für das Fünfeck gibt es 5 Möglichkeiten:

und für das Sechseck 14:

Sei t_n die Anzahl der Triangulierungen eines n-Ecks, man hat also t₂=t₃=1, t₄=2, t₅=5, t₆=14.

Es gibt dann verschiedene Möglichkeiten, eine Rekursionsformel zu bauen.
Die naheliegende: Eine Kante des n-Ecks muss in einem Dreieck der Triangulierung vorkommen. Je nachdem, welches die dritte Ecke dieses Dreiecks ist, wird das n-Eck für irgendein k in ein k-Eck und ein n+1-k-Eck zerlegt, die dann einzeln trianguliert werden. Also t_n=t₂t_n-1+t₃t_n-2+t₄t_n-3+...+t_n-1t₂
Damit kann man im Prinzip induktiv alle t_n ausrechnen, eine geschlossene Formel für t_n erkennt man aber nicht auf Anhieb.

Besser ist deshalb ein nicht so offensichtlicher Zugang des doppelten Abzählens: man kann ja eine Triangulierung des n-Ecks durch "Verdoppeln" einer Kante zu einer Triangulierung des n+1-Ecks machen (dafür gibt es 2(2n-3) Möglichkeiten, nämlich 2 zu jeder der 2n-3 Kanten der Triangulierung) und umgekehrt eine Triangulierung des n+1-Ecks durch "Kontraktion" einer Kante zu einer Triangulierung des n-Ecks machen. Dabei gibt es jeweils n Triangulierungen des n+1-Ecks, die sich durch Kontraktion in eine gegebene Triangulierung des n-Ecks vereinfachen lassen. Also 2(2n-3)t_n=nt_n+1.
Mit dieser Rekursion bekommt man dann sofort eine geschlossene Formel für t_n: t_n ist gerade die Catalan-Zahl C_n-2.

(Nebenbei: die geschlossene Formel stammt aus einem beim Euler-Archiv online-stehenden Brief von Euler an Goldbach vom 4.9.1751.)

Die Catalan-Zahlen kommen übrigens in der Mathematik noch an vielen anderen Stellen vor (vgl. auch den Wikipedia-Artikel), z.B. als Anzahl der Binärbäume mit n+1 Ecken, oder als Anzahl der eindimensionalen Irrfahrten von 0 nach 2n mit Anfangs- und Endpunkt in 0, so dass sich der Pfad nie unterhalb der x-Achse befindet, oder als Anzahl der Möglichkeiten, n+1 Faktoren zu klammern:

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

In Kapitel 1.1. von Loera-Rambau-Santos werden einige dieser Gleichheiten noch direkt bewiesen (also ohne explizites Ausrechnen der jeweiligen Anzahlen).

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101, Teil 102, Teil 103, Teil 104, Teil 105, Teil 106, Teil 107, Teil 108, Teil 109, Teil 110, Teil 111, Teil 112, Teil 113, Teil 114, Teil 115, Teil 116, Teil 117, Teil 118, Teil 119, Teil 120, Teil 121, Teil 122, Teil 123, Teil 124, Teil 125, Teil 126, Teil 127, Teil 128, Teil 129, Teil 130, Teil 131, Teil 132, Teil 133, Teil 134, Teil 135, Teil 136, Teil 137, Teil 138, Teil 139, Teil 140, Teil 141, Teil 142, Teil 143, Teil 144, Teil 145, Teil 146, Teil 147, Teil 148, Teil 149, Teil 150, Teil 151, Teil 152, Teil 153, Teil 154, Teil 155, Teil 156, Teil 157, Teil 158, Teil 159, Teil 160, Teil 161

 

Autor: Thilo· 3 Kommentare· Permalink· Trackback-URL

Tags: Catalan-Zahl· Diagonale· Euler· Polygon· Triangulierung