查看“︁凱萊公式”︁的源代码

{{Refimprove|time=2020-02-17T10:37:14+00:00}}
在[[图论]]中，'''凯莱公式（Cayley formula）'''计算[[完全图]]的[[生成树]]的总数。若有<math>n</math>个[[顶点 (图论)|顶点]]，生成树的数量是<math>n^{n-2}</math>。<ref>{{Cite book|last1=Aigner|first1=Martin|author1-link=Martin Aigner|last2=Ziegler|first2=Günter M.|author2-link=Günter M. Ziegler|pages=141–146|publisher=[[Springer-Verlag]]|title=Proofs from THE BOOK|year=1998|title-link=Proofs from THE BOOK}}</ref><ref>{{Cite web|title=A000272 - OEIS|url=https://oeis.org/A000272|accessdate=2020-02-14|work=oeis.org|archive-date=2020-02-16|archive-url=https://web.archive.org/web/20200216200944/http://oeis.org/A000272|dead-url=no}}</ref><ref>{{cite journal|title=A theorem on trees|url=https://books.google.com/books?id=M7c4AAAAIAAJ&pg=PA26|last=Cayley|first=A.|authorlink=Arthur Cayley|journal=Quart. J. Pure Appl. Math|year=1889|volume=23|pages=376–378|access-date=2020-02-14|archive-date=2017-04-06|archive-url=https://web.archive.org/web/20170406111232/https://books.google.com/books?id=M7c4AAAAIAAJ&pg=PA26|dead-url=no}}</ref><ref>{{cite journal|title=On an enumeration problem|last=Schützenberger|first=M. P.|authorlink=Marcel-Paul Schützenberger|journal=Journal of Combinatorial Theory|year=1968|volume=4|pages=219–221|mr=0218257}}</ref><ref>{{cite journal|title=On Cayley's formula for counting forests|first1=Lajos|date=March 1990|journal=Journal of Combinatorial Theory, Series A|issue=2|doi=10.1016/0097-3165(90)90064-4|volume=53|pages=321–323|last1=Takács}}</ref>

这个定理以[[阿瑟·凱萊|阿瑟·凯莱]]的名字命名。
[[File:Cayley's_formula_2-4.svg|链接=https://zh.wikipedia.org/wiki/File:Cayley's_formula_2-4.svg|缩略图|2、3、4个顶点中的生成树]]

== 证明办法 ==

* 使用[[矩阵树定理]]<ref>{{cite journal|title=Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung|last=Borchardt|first=C. W.|authorlink=Carl Wilhelm Borchardt|journal=Math. Abh. der Akademie der Wissenschaften zu Berlin|year=1860|pages=1–20}}</ref>
* 使用[[母函数]]<ref>{{Cite web|title=Download generatingfunctionology|url=https://www.math.upenn.edu/~wilf/DownldGF.html|accessdate=2020-02-14|work=www.math.upenn.edu|archive-date=2020-02-14|archive-url=https://web.archive.org/web/20200214231926/https://www.math.upenn.edu/~wilf/DownldGF.html|dead-url=no}}</ref>
* [[普吕弗序列]]

== 参考文献 ==
<references group="" responsive="1"></references>

[[Category:图论]]