Cayleys formel

En fullständig uppsättning märkta träd med 2, 3 respektive 4 noder: $2^{2-2}=1$ träd med två noder, $3^{3-2}=3$ träd med tre noder och $4^{4-2}=16$ träd med fyra noder.

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 n^n-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:

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: T_n ⋅ n! = n^n-2 ⋅ n!.

Historia

Formeln upptäcktes först av Carl Wilhelm Borchardt 1860 och visades med hjälp av en determinant Genom att beakta nodernas grader utvecklade Cayley formeln i flera riktningar 1889 i en kort notis, och fastän han refererade till Borchardts originaluppsats, blev namnet "Cayleys formel" bestående.