科研之友
微信
新浪微博
Facebook
分享链接
摘要
Cayley's tree formula is one of the most beautiful results in enumerative combinatorics with a number of well-known proofs. A fascinating and recurring theme in mathematics is the existence of rich and surprising interconnections between apparently disjoint domains. We will, hopefully, see one such instance in this note, in which we give a short proof of Cayley's tree formula for counting the number of distinct labeled trees on n vertices by employing a combinatorial argument. In fact, we deduce a nonlinear recursive relation for the number of labeled trees on n vertices and then we show that this recursion is same as the celebrated Cayley tree formula. One interesting feature of this proof is that a discrete counting problem is solved by going from a recursion, to a differential equation, to complex analysis, and then back to a discrete formula.
- 出版日期2018
