Cayley-Formel

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

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 ${\displaystyle n^{n-2}}$ verschiedene bezeichnete Bäume mit ${\displaystyle n}$ Knoten gibt.

Formulierungen

• Es gibt ${\displaystyle n^{n-2}}$ verschiedene bezeichnete Bäume mit ${\displaystyle n}$ Knoten.
• Der bezeichnete vollständige Graph mit ${\displaystyle n}$ Knoten hat ${\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

• 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.
• 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.