Cayleys formel
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Cayley%27s_formula_2-4.svg/250px-Cayley%27s_formula_2-4.svg.png)
Inom matematiken är Cayleys formel ett uttryck inom grafteorin som uppkallats efter Arthur Cayley. Det säger att för varje positivt heltal n, är antalet träd över n märkta noder lika med nn-2.
Dessutom anger formeln antalet uppspännande träd för en komplett graf med märkta noder.(talföljd A000272 i OEIS).
Bevis
Det finns många anmärkningsvärda bevis för Cayleys trädformel:[1]
Ett klassiskt bevis använder Kirchhoffs trädsats, en formel för antalet uppspännande träd i en godtycklig graf genom beräkning av determinanten för en matris som härletts från grafen.
Med prüfersekvenser får man ett bijektivt bevis för Cayleys formel.
Ett annat bijektivt bevis gavs av André Joyal och finner en ett-till-ett-övergång mellan träd med två utvalda noder och maximala riktade pseudoskogar (en pseudoskog är en skog där träden har högst en cykel).
Ett bevis genom dubbelräkning av Jim Pitman räknar (på två olika sätt) ut antalet olika följder av riktade kanter som kan läggas till en tom graf och därigenom skapa ett rotat träd. Genom att sätta dessa beräkningar lika får man Cayleys formel: Tn ⋅ n! = nn-2 ⋅ n!.
Historia
Formeln upptäcktes först av Carl Wilhelm Borchardt 1860 och visades med hjälp av en determinant[2] Genom att beakta nodernas grader utvecklade Cayley formeln i flera riktningar 1889 i en kort notis,[3] och fastän han refererade till Borchardts originaluppsats, blev namnet "Cayleys formel" bestående.
Referenser
- ^ Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. sid. 141–146. ISBN 3-540-40460-0. http://books.google.se/books?id=KvQr9l0wgf8C&pg=PA173&lpg=PA173 , sid. 173 ff.
- ^ Borchardt, C. W. (1860). ”Über eine Interpolationsformel für eine Art Symmetrischer Funktionen und über Deren Anwendung”. Math. Abh. der Akademie der Wissenschaften zu Berlin: sid. 1–20.
- ^ Cayley, A. (1889). ”A theorem on trees”. Quart. J. Math 23: sid. 376–378. http://books.google.com/?id=M7c4AAAAIAAJ&pg=PA26.