Cayley-Formel

Datei:Cayley's formula 2-4.svg

Alle bezeichneten Bäume der Größen 2,3 und 4.

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]:

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ählenden Kombinatorik. Er besagt, dass es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} verschiedene bezeichnete Bäume mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten gibt.

Formulierungen

• Es gibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} verschiedene bezeichnete Bäume mit $n$ Knoten.
• Der bezeichnete vollständige Graph mit $n$ Knoten hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} verschiedene 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:

1. mittels einer Bijektion von der Menge aller Bäume in eine einfacher zu zählende Menge (siehe Prüfer-Code),
2. unter Verwendung des Satzes von Kirchhoff,
3. mittels Rekursion,
4. durch doppeltes Abzählen.

Geschichte

Die Formel wurde zuerst von 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

• Martin Aigner, Günter M. Ziegler: Das Buch der Beweise. Springer-Verlag, 2010, Kapitel 30 – Cayleys Formel für die Anzahl der Bäume, S. 227–233. 
• Borchardt, C.W.: Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung. In: Math. Abh. der Akademie der Wissenschaften zu Berlin. 1860, S. 1–20.
• A. Cayley: A theorem on trees. In: Quart. J. Math. 23, 1889, S. 376–378.