Combinatorik. Wahrscheinlichkeitsrechnung.

605

Die zweite Aufgabe von 1751 bat Euler damals in eiuein Briefeau Goldbach gestellt 1 ). Sie lautet: Auf wie vielerlei Arten kannein Vieleck durch Diagonalen in Dreiecke zerlegt werden?Ein Viereck AB CI) wird entweder durch AC oder durch BJ), durchdie eine oder durch die andere Diagonale, zusammen aut zwei Arten,in zwei Dreiecke zerlegt. Die Zerlegung eines Fünfecks ABCDEin drei Dreiecke mittels zweier Diagonalen findet auf fünf Arten statt,nämlich mittels AC und AI), mittels BI) und BE, mittels CA undCE, mittels DB und DA, mittels EC und EB. Bei einem mittelsdreier Diagonalen in vier Dreiecke zu zerlegenden Sechsecke giebt esvierzehn verschiedene Arten. Um die Arten zu zählen, nach welchenein «-eck mittels n — 3 Diagonalen in n — 2 Dreiecke zerlegt wird,hat man, wenn z ihre Anzahl heisst, folgende Zusammenstellung:

3, 4, 5, 6

14, 42, 132, 429, 1430

und allgemein

4 n —10n — 1

2 6 10 14

7 ”3 ‘ 1 b

Die Iiuluction, sagt Euler, so ich gebraucht, war ziemlich mühsam,doch zweifle ich nicht, dass diese Sache nicht sollte weit leichterentwickelt werden können.

Auch an Segner muss Euler die sieben ersten Zerlegungszahlen1, 2, 5, 14, 42, 132, 429 aber ohne die zu ihrer Berechnung führendeFormel haben gelangen lassen, und nun entwickelte dieser in denVeröffentlichungen der Petersburger Akademie eine Recursionsformelzur Lösung der Aufgabe 2 ). SeiACDEFGB (Fig. 101) das zur ^

Zerlegung gegebene Vieleck und /1\ \

A B irgend eine der n -f- 2 Seiten / . \

desselben. Die Diagonalen von A ( / I \

und von B nach C, deren erstere \ 1 \ /

eine Vielecksseite selbst ist, lassen \ 1 \ ^ /( - :

links nur die Seite AC, rechts das N.-

(M-j-l V-Eck BCDEFG erscheinen. ' Fig 1C1

Das Dreieck ist das erste über-haupt mögliche Vieleck und kann mit dem Index 1 versehen werden,das Viereck mit dem Index 2, das (m-|- 1)-Eck mit dem Index n — 1.Eine Seite ist eigentlich keine Figur und hat den Index 0 zu führen.Die Indices der durch Ziehung von AC und BC links und rechts

>) Corresp. math. (Fuss) I, 551—552. J ) Novi Commcnturii AcademiaeBctropolitanac pro annis 1758 et 1759. T. VII, 283—310.