imported>Ulanwp: 3 fehlende Sprachparameter eingefügt

2026-02-15T15:09:47Z

3 fehlende Sprachparameter eingefügt

Neue Seite

[[Datei:Cayley's formula 2-4.svg|mini|Alle bezeichneten Bäume der Größen 2,3 und 4.]]
[[Datei:Spanning Trees qtl1.svg|mini|Alle 16 aufspannenden Bäume des vollständigen Graphen mit 4 Knoten.]]

Die '''Cayley-Formel''' (benannt nach [[Arthur Cayley]]), manchmal auch '''Satz von Cayley''' genannt, ist ein Satz aus der [[Abzählende Kombinatorik|abzählenden Kombinatorik]].
Er besagt, dass es <math>n^{n-2}</math> verschiedene bezeichnete [[Baum (Graphentheorie)|Bäume]] mit <math>n</math> Knoten gibt.

== Formulierungen ==
* Es gibt <math>n^{n-2}</math> verschiedene bezeichnete [[Baum (Graphentheorie)|Bäume]] mit <math>n</math> Knoten.
* Der bezeichnete [[Vollständiger Graph|vollständige Graph]] mit <math>n</math> Knoten hat <math>n^{n-2}</math> verschiedene [[Spannbaum|aufspannende Bäume]].

== Beweise ==
Für die Cayley-Formel gibt es unzählige Beweise, einige davon werden von vielen Mathematikern als besonders schön angesehen.
Das spiegelt sich unter anderem in der Tatsache, dass der Cayley-Formel ein Kapitel in ''[[Das Buch der Beweise]]'' gewidmet ist.
Dort werden vier verschiedene Beweise präsentiert:
# mittels einer [[Bijektion]] von der Menge aller Bäume in eine einfacher zu zählende Menge (siehe [[Prüfer-Code]]),
# unter Verwendung des [[Satz von Kirchhoff|Satzes von Kirchhoff]],
# mittels [[Rekursion]],
# durch [[doppeltes Abzählen]].

== Geschichte ==
Die Formel wurde zuerst von [[Karl Wilhelm Borchardt|Carl Wilhelm Borchardt]] (1860) publiziert.
1889 erweiterte Cayley die Formel und formulierte sie in der Graphenterminologie, weshalb sie seitdem mit seinem Namen verbunden wird.

Auch erwähnenswert ist, dass [[James Joseph Sylvester]] schon (1857) ein äquivalentes Resultat publizierte.

== Literatur ==
* {{Literatur |Autor=Martin Aigner, [[Günter Ziegler|Günter M. Ziegler]] |Titel=[[Das Buch der Beweise]] |Verlag=Springer-Verlag |Datum=2010 |Kapitel=Kapitel 30 – ''Cayleys Formel für die Anzahl der Bäume'' |Seiten=227–233 |Sprache=de}}
* {{cite journal |author=Borchardt, C.W. |year=1860 |title=Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung |journal=Math. Abh. der Akademie der Wissenschaften zu Berlin |pages=1–20 |language=de}}
* {{cite journal |author=A. Cayley |year=1889 |title=A theorem on trees |journal=Quart. J. Math |volume=23 |pages=376–378 |url=http://books.google.com/?id=M7c4AAAAIAAJ&pg=PA26 |language=en}}

[[Kategorie:Kombinatorik]]
[[Kategorie:Satz (Mathematik)]]

Cayley-Formel - Versionsgeschichte

imported>Ulanwp: 3 fehlende Sprachparameter eingefügt