- Cayleys Formel
-
Alle bezeichneten Bäume der Größen 2,3 und 4.
Cayleys Formel (benannt nach Arthur Cayley), manchmal auch Satz von Cayley, ist ein Satz aus der abzählenden Kombinatorik. Er besagt, dass es nn − 2 verschiedene bezeichnete Bäume mit n Knoten gibt.
Inhaltsverzeichnis
Formulierungen
- Es gibt nn − 2 verschiedene bezeichnete Bäume mit n Knoten.
- Der bezeichnete vollständige Graph mit n Knoten hat nn − 2 verschiedene aufspannende Bäume.
Beweise
Für Cayleys Formel gibt es unzählige Beweise, einige davon von vielen Mathematikern als besonders schöne Beweise angesehen. Das spiegelt sich unter anderem in der Tatsache, dass Cayleys Formel ein Kapitel im Das BUCH der Beweise gewidmet ist. Dort werden 4 verschiedene Beweise präsentiert:
- mittels einer Bijektion von der Menge aller Bäume in eine einfacher zu zählende Menge.
- unter Verwendung Kirchhoffs Matrix-Baum-Theorems
- mittels Rekursion
- 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 seit dem mit seinem Name verbunden wird.
Auch erwähnenswert ist, dass James Joseph Sylvester schon (1857) ein äquivalentes Resultat publizierte.
Literatur
- Das BUCH der Beweise, S. 227–33 (Kapitel 30 - Cayleys Formel fur die Anzahl der Bäume), Springer-Verlag 2010.
- 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.
Wikimedia Foundation.
