Wzór Cayleya - Cayley's formula

Pełna lista wszystkich drzew na wierzchołkach 2,3,4 oznaczonych etykietami: drzewo z 2 wierzchołkami, drzewa z 3 wierzchołkami i drzewa z 4 wierzchołkami. ${\ Displaystyle 2 ^ {2-2} = 1}$${\ Displaystyle 3 ^ {3-2} = 3}$${\ displaystyle 4 ^ {4-2} = 16}$

W matematyce , formuła Cayleya jest wynikiem w teorii grafów nazwie po Arthur Cayley . Stwierdza, że ​​dla każdej dodatniej liczby całkowitej liczba drzew na oznaczonych wierzchołkach wynosi . ${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle n ^ {n-2}}$

Wzór równoważnie zlicza drzew rozpinających o pełnej wykresie znakowanym wierzchołków (sekwencja A000272 w OEIS ).

Dowód

Znanych jest wiele dowodów na formułę drzewa Cayleya. Jeden klasyczny dowód wzorze wykorzystuje Kirchhoffa macierzy drzewa twierdzenie , wzór na liczbie drzew rozpinających, w dowolnym wykresie z udziałem determinant o matrycy . Sekwencje Prüfera dają bijektywny dowód wzoru Cayleya. Kolejny dowód bijektywny , autorstwa André Joyal , wskazuje na transformację jeden do jednego między drzewami n- węzłowymi z dwoma rozróżnionymi węzłami i maksymalnymi ukierunkowanymi pseudolesami . Dowód przez podwójne liczenie z powodu Jima Pitmana liczy na dwa różne sposoby liczbę różnych sekwencji skierowanych krawędzi, które można dodać do pustego wykresu na n wierzchołkach, aby utworzyć z niego zakorzenione drzewo; patrz Liczenie podwójne (technika dowodowa) § Liczenie drzew .

Historia

Formuła została po raz pierwszy odkryta przez Carla Wilhelma Borchardta w 1860 roku i udowodniona za pomocą wyznacznika . W krótkiej notatce z 1889 roku Cayley rozszerzył formułę w kilku kierunkach, biorąc pod uwagę stopnie wierzchołków. Chociaż odniósł się do oryginalnej pracy Borchardta, nazwa „wzór Cayleya” stała się standardem w tej dziedzinie.

Inne właściwości

Wzór Cayleya natychmiast podaje liczbę oznaczonych ukorzenionych lasów na n wierzchołkach, czyli ( n + 1) ^{n - 1} . Każdy oznaczony jako ukorzeniony las można przekształcić w oznaczone drzewo z jednym dodatkowym wierzchołkiem, dodając wierzchołek z etykietą n + 1 i łącząc go ze wszystkimi korzeniami drzew w lesie.

Istnieje ścisły związek z ukorzenionymi lasami i funkcjami parkingowymi , ponieważ liczba funkcji parkingowych na n samochodach również wynosi ( n + 1) ^{n - 1} . W 1968 roku poseł Schützenberger podał sprzeczność między ukorzenionymi lasami a funkcjami parkingowymi .

Uogólnienia

Poniższy wzór uogólnia wzór Cayleya na lasy z etykietami: Niech T _{n , k} będzie liczbą oznaczonych lasów na n wierzchołkach z k połączonymi komponentami, tak że wierzchołki 1, 2, ..., k należą do różnych połączonych komponentów. Wtedy T _{n , k} = k n ^{n - k - 1} .

Bibliografia