나무 그래프: 두 판 사이의 차이

임의의 크기 <math>n</math>의 [[유한 집합]] <math>V</math>가 주어졌다고 하자. 그렇다면, <math>V</math>를 꼭짓점으로 하는 나무 그래프의 수를 <math>T_n</math>이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) '''케일리 공식'''({{llang|en|Cayley’s formula}})에 따르면, 이는 다음과 같다.<ref>{{저널 인용|제목=케일리 공식의 네 가지 증명|저널=한국수학사학회지|권=21|호=3|날짜=2008-08|쪽=127–142|저자1=서승현|저자2=권석일|저자3=홍진곤|url=http://society.kisti.re.kr/sv/SV_svpsbs03V.do?method=download&cn1=JAKO200800557082835 | 언어=ko}}

케일리 공식은 1860년에 카를 빌헬름 보르하르트({{llang|de|Carl Wilhelm Borchardt}}, 1817~1880)가 최초로 증명하였다.<ref>{{저널 인용|성=Borchardt|이름=Carl Wilhelm|날짜=1860|제목=Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung|저널=Abhandlungen der Königlichen Akademie der Wissenschaften zu Berlin. Mathematische Klasse|쪽=1–20|url=https://archive.org/details/abhandlungenderk1860deut|url=https://archive.org/stream/abhandlungenderk1860deut#page/n246/|zbl=057.1508cj|언어=de}}</ref> 이후 1889년에 [[아서 케일리]]가 같은 정리의 새 증명을 발표하였다.<ref>{{저널 인용|성=Cayley|이름=Arthur|저자고리=아서 케일리|날짜=1889|제목=A theorem on trees|저널=The Quarterly Journal of Pure and Applied Mathematics|권=23|쪽=376–378|jfm=21.0687.01|언어=en}}</ref> 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.