Formula lui Cayley

În matematică, Formula lui Cayley este un rezultat în teoria grafurilor, numit după Arthur Cayley. Formula stabilește că, pentru orice număr natural n, numărul de arbori etichetați este de n^{n - 2}.

Lista completă a arborilor cu 2, 3 sau 4 noduri etichetate : 2^{2 - 2} = 1 arbori cu două noduri, 3^{3 - 2} = 3 arbori cu trei noduri și 4^{4 - 2} = 16 arbori cu patru noduri.

Sunt cunoscute multe demonstrații ale formulei lui Cayley, cum ar fi cu ajutorul teoremei lui Kirchhoff pentru arbori de matrici, prin șiruri Prüfer sau prin dublă numărare.

Numărare prin calculul cu specii

După punctarea a două noduri (roșu și albastru) într-un arbore, toate nodurile (roz) de pe unicul traseu liniar care le unește devin la rândul lor determinate producând o vertebră, sau un Lin(Ars).

O mulțime de două cicluri a câte trei și două arborescențe. Orice endo-funcție poate fi reprezentată astfel, urmărind șirurile x, F(x), F(F(x)),.... care afluesc, convergând înspre cicluri.

Să notăm cu M_n numărul de arbori etichetați pentru un n dat. Dacă într-un arbore se marchează două noduri, numărul de realizări ale noii specii „arbore cu două noduri marcate” (numită și vertebră) este de n.n.M_n.

Între oricare două noduri ale unui arbore există un unic drum. Prin marcarea a două noduri (ele pot coincide) se marchează, implicit, și toate nodurile intermediare. Astfel, vertebra poate fi descrisă ca un șir de noduri marcate, în care fiecare nod este rădăcina unui arborescențe (arbore cu rădăcină).

| Vertebră | = n.n.M_n,

Vertebră = Lin (Ars)

Mai departe, specia Lin(Ars) este echipotentă cu specia Perm(Ars) pentru că există tot atâtea ordini lineare câte permutări definite pe o aceeași mulțime.

Lin (Ars) ≈ Perm(Ars)

Însă Perm(Ars) nu este altceva decât specia funcțiilor definite de la o mulțime la ea însăși, Ens(Cyc(Ars))

Perm(Ars) = [Ens(Cyc)]°(Ars) = Ens(Cyc(Ars)) = End,

a cărei număr de realizări este nⁿ :

| End | = nⁿ

În concluzie, M_n = n^n-2.

Istoric

Formula a fost descoperită prima dată de către Carl Wilhelm Borchardt in 1860 și demonstrată cu ajutorul determinanților. Cu toate acestea, numele de formula lui Cayley a rămas înrădăcinat în domeniu.

Bibliografie

• Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. pp. 141–146. .
• Borchardt, C.W. (1860). „Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung”. Math. Abh. der Akademie der Wissenschaften zu Berlin: 1–20. 
• A. Cayley (1889). „A theorem on trees”. Quart. J. Math. 23: 376–378.