Formula lui Cayley

Lista completă a copacilor etichetați cu 2, 3 și 4 vârfuri.

Formula lui Cayley este utilizată în matematică în teoria graficelor .

Se afirmă că numărul copacilor care se pot întinde pe un grafic cu n vârfuri etichetate (cu n > 1) este egal cu n ^n-2 .

Vorbim despre vârfurile „etichetate” atunci când sunt identificate prin numere, culori etc. Copacii cu vârfuri etichetate sunt uneori numiți copaci Cayley .

De exemplu, pentru copacii cu 2, 3 și 4 vârfuri, formula oferă următoarele rezultate:

$A_{2}=2^{2-2}$ ${\ displaystyle A_ {2} = 2 ^ {2-2}}$ ${\ displaystyle A_ {2} = 2 ^ {2-2}}$ (1 copac cu 2 vârfuri)
$A_{3}=3^{3-2}$ ${\ displaystyle A_ {3} = 3 ^ {3-2}}$ ${\ displaystyle A_ {3} = 3 ^ {3-2}}$ (3 copaci cu 3 vârfuri)
$A_{4}=4^{4-2}$ ${\ displaystyle A_ {4} = 4 ^ {4-2}}$ ${\ displaystyle A_ {4} = 4 ^ {4-2}}$ (16 copaci cu 4 vârfuri)

Istorie

Această formulă a fost descoperită de germanul Carl Borchardt în 1860, care a dovedit-o printr-un determinant . ^[1]
În 1889, englezul Arthur Cayley a extins formula, luând în considerare și gradul (adică multiplicitatea) vârfurilor. Cayley a recunoscut faptul că Borchardt este autorul formulei originale, dar mai târziu a intrat în folosință numele „formula lui Cayley”. ^[2]

Demonstrații

Există mai multe dovezi ale formulei lui Cayley. Un exemplu clasic folosește teorema lui Kirchhoff , aplicabilă oricărui grafic, în timp ce formula lui Cayley este limitată la grafice complete .

Același subiect în detaliu: teorema lui Kirchhoff .

În 1918 Heinz Prüfer a demonstrat acest lucru prin intermediul codului Prüfer , care oferă o descriere compactă și unică a unui copac cu n vârfuri etichetate folosind o secvență de tipul

P=(x_{1},x_{2},x_{3},...,x_{n-2})

{\ displaystyle P = (x_ {1}, x_ {2}, x_ {3}, ..., x_ {n-2})}

{\ displaystyle P = (x_ {1}, x_ {2}, x_ {3}, ..., x_ {n-2})}

Fiecărei secvențe P îi corespunde unul și un singur arbore cu n vârfuri marcate.

Notă

^ Borchardt CW, Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung , în "Math. Abh. Der Akademie der Wissenschaften zu Berlin" (1860), pp. 1-20.
^ A. Cayley: A Theorem on Trees in Quarterly Journal of Mathematics 1889, pp. 376-378.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Borchardt CW, Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung , în "Math. Abh. Der Akademie der Wissenschaften zu Berlin" (1860), pp. 1-20.

[2] A. Cayley: A Theorem on Trees in Quarterly Journal of Mathematics 1889, pp. 376-378.

[1]

[2]