A Cayley-formula egy gráfelméleti leszámlálási tétel, melyet Arthur Cayley-ről neveztek el. Meghatározza, hogy hány különböző ${\displaystyle n}$ csúcsú számozott fa adható meg. Ez az érték:

${\displaystyle n^{n-2}\,.}$

Történet

Arthur Cayley 1889-ben publikálta cikkét, mely tartalmazza ezt a formulát. A tételt azonban már korábban bebizonyították. 1860-ban Carl W. Borchardt (akinek elsőbbségét maga Cayley is elismerte), és még ennél is korábban, 1857-ben, James Joseph Sylvester közölt egy ezzel egyenértékű eredményt. Cayley cikkében az újdonság a gráfelmélet alkalmazása volt, és a tétel azóta is az ő nevéhez fűződik.

Bizonyítás

Tekintsük az

${\displaystyle N=\{1,2,3,4...,n\}\,}$

halmazt, mint a gráf csúcsainak halmazát. Jelöljük ${\displaystyle T_{n}}$-nel a lehetséges fák számát ${\displaystyle n}$ csúcson. Nyilvánvalóan adódik, hogy

${\displaystyle T_{1}=1,\quad T_{2}=1,\quad T_{3}=3,\quad T_{4}=16\,}$.

Hangsúlyozzuk, hogy számozott fákat vizsgálunk, vagyis 3 csúcspontú fa (gráf-izomorfizmus erejéig) csak 1 van, míg a számozott esetben a másodfokú pontot háromféleképpen választhatjuk meg, így ott 3 különböző megoldás létezik.

1. bizonyítás

A tétel legismertebb bizonyítása a Prüfer-kód felhasználásával történik. Mivel ez kölcsönösen egyértelmű (bijektív) megfeleltetést ad a számozott fák száma és az n - 2 hosszú számsorozatok között (melyeknek minden eleme 1 és n közti egész), így nyilvánvalóan adódik az állítás, vagyis

${\displaystyle T_{n}=n^{n-2}\,.}$

Lemma. A számozott fák és a Prüfer-kódok között kölcsönösen egyértelmű megfeleltetés létezik.

Bizonyítás.

Nyilvánvaló, hogy minden fához egyértelműen tartozik egy Prüfer-kód. Azt kell még belátni, hogy minden Prüfer-kódhoz (legyen ez v₁, v₂, … ,v_n-2) is egyértelműen létezik egy fa, amit leír. Abból, hogy hány számból áll a kód azonnal kapjuk n értékét, hiszen a sorozat n - 2 hosszú. Legyen w_k az a pont, amelynek elhagyásakor v_k-t feljegyeztük. Tehát ha meghatározzuk w_k-t minden k-ra, akkor már egyértelműen rekonstruálható a fa, hiszen élei pontosan a {w_k, v_k} párok. A w_k-k pedig könnyen meghatározhatók, hiszen w₁ a legkisebb olyan szám, ami nem fordul elő v₁,v₂,…,v_n-1 között, általánosan pedig w_k az a szám, ami nem fordul elő w₁,w₂,…,w_k-1,v_k,…,v_n-1 számok között. Ilyen szám mindig létezik, hiszen ha mind különböző lenne, akkor is csak n - 1 -et zártunk ki az n-ből. Megkaptuk tehát a

${\displaystyle \{v_{1},w_{1}\},\quad \{v_{2},w_{2}\},...,\{v_{n-1},w_{n-1}\}\,}$

éleket. Be kell látnunk, hogy ezek fát határoznak meg (tehát körmentes gráfot), és ekkor a gráf Prüfer-kódja éppen v₁,v₂,…,v_n-1. Tegyük fel indirekt módon, hogy van a gráfban kör. A Prüfer-kód „visszafejtése” során minden egyes újabb w_i felírásakor egy újabb pontot, és egy újabb élet kapunk meg. Kell lennie egy olyan lépésnek, amikor a kör utolsó élét húzzuk be, de ekkor egy olyan w_i-t kéne felírnunk, amely már korábban szerepelt, ez azonban a fenti eljárásban nem lehetséges. Tehát minden n - 1 elemű sorozathoz, amelyben az első n - 2 elem mindegyike lehet {1,2,…,n} és az utolsó elem n, tartozik egy fa, és különböző sorozatokhoz különböző fa tartozik.

2. bizonyítás

A következő ötlet Riordantól és Rényitől származik. A bizonyítás alapgondolata egy olyan rekurzió megadása, melynek segítségével könnyen megoldható a probléma. A megfelelő rekurzió megtalálásához egy bonyolultabb probléma vizsgálatán keresztül juthatunk el. Legyen A az N = {1,2,3,…,n} csúcsok egy tetszőleges k elemű részhalmaza. Tekintsük az n csúcson megadható k darab fát tartalmazó (számozott) erdők számát, ahol az A halmaz elemei különböző fákban vannak. Jelöljük ezt T_n,k-val. Nyilvánvaló, hogy az A halmaznak csak az elemszáma számít. Ekkor T_n,1 = T_n. Tekintsünk egy F erdőt az A = {1,2,3,…,k} halmazzal, és ennek 1 csúcsát, melynek i db szomszédja van. Amennyiben ezt a csúcsot elhagyjuk, úgy az i db szomszéd és a 2,3,…,k pontok együtt T_n-1,k-1+i darab erdőt adnak. Mivel i-t tetszőlegesen választhatjuk ki aközül az n-k csúcs közül, mely az 1,2,…,k csúcsoktól különbözik, így n ≥ k ≥ 1 -re az következik, hogy

${\displaystyle T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}T_{n-1,k-1+i}\qquad \qquad (1)\,.}$

Legyen T_0,0= 1 és n > 1 esetén T_n,0= 0. T_0,0 = 1 azért szükséges, hogy fennálljon T_n,n = 1. Ekkor

${\displaystyle T_{n,k}=kn^{n-k-1}\,}$

amiből speciálisan:

${\displaystyle T_{n,1}=n^{n-2}\,.}$

Bizonyítás. A bizonyítás teljes indukcióval történik. A rekurziót (1)-et és az állítást felhasználva kapjuk:

${\displaystyle T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}T_{n-1,k-1+i}\,}$

${\displaystyle T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(k-1+i)(n-1)^{n-1-k-i}\,}$

Legyen i = n - k - i

${\displaystyle T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(n-1-i)(n-1)^{i-1}\,}$

${\displaystyle T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(n-1)^{i}-\sum _{i=1}^{n-k}{\binom {n-k}{i}}i(n-1)^{i-1}\,}$

${\displaystyle T_{n,k}=n^{n-k}-(n-k)\sum _{i=1}^{n-k}{\binom {n-1-k}{i-1}}(n-1)^{i-1}\,}$

${\displaystyle T_{n,k}=n^{n-<!--\; -\; -->k}-<!--\; -\; -->(n-<!--\; -\; -->k)\underset{i=0}{\overset{n-<!--\; -\; -->1-<!--\; -\; -->k}{\sum <!--\; \sum \; -->}}(}$Információ forrás: https://hu.wikipedia.org/wiki/Cayley-formula
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.

---