n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
为什么 1-1+1-1+1-1…=0.5？作为数学博士研究生，以什么频率发文章才有在学术界生存的能力/潜力？
高考数学考场睡一个多小时考 149 分，这种事情有可能发生吗？是不是真的存在牛人？
亚里士多德车轮悖论的正确解释是什么？
你能写出你认为既简洁又很酷的公式么？
matrix67去哪了？
为什么有的数学定理看起来很显然，证明起来却很复杂？
高一没上过竞赛，看了一个月微积分。今天早上尝试后自己推出了球体积公式，大概什么水平?
天赋一般是不是不适合学数学？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
圣彼得堡悖论，期望与实际相差为何这么大？有没有大神回答一下，级数中，比值判别法中的ρ是指什么？
「所有正整数之和是负十二分之一」在数学上是没有矛盾的吗？
任给一张面积为A的纸片，如何证明必可将它剪为面积相等的两块？
为什么文科生要学数学，高中数学有什么用？
我有一个数学猜想，你们能证明吗，下面有关于该问题的详细补充说明？
R^2 与 C 的区别在哪里？为什么有数学家认为复数用 a+bi 表示不好？
中国古代数学形成以计算见长，以解决实际问题为特点的数学理论体系，那为何现代却更重是理论?
李煌的阶乘计算小技巧，与斯特林公式有什么区别？
实数在自然界有用吗？
如何证明闭开区间无最大值(如反证法)？
为什么数学概念中，将凸起的函数称为凹函数？
怎么看待考研数学老师李林「神押题」？
如何评价组合数学（combinatorics）这个学科？
Lagrange 如何用连分数理论推导出一次同余方程的通解？
电脑会算错数吗？
如何用物理和数学名词写成诗？都有哪些作品？
如何计算 sqrt(tan x) 在 0 到 π/2 的定积分？
既然彩票号码中奖概率是一样的，为什么很少有人买「1234……」这组？
下面圆周率的这3个无穷级数公式怎么证明？
10 × 10 的正方形最多可放入多少个直径为 1 的圆？
有没有可能一个数学证明是错的，然而所有人都没注意到呢？
家境普通的姑娘想学物理或数学，怎么看？
初三数学20几分怎么能达到100+?
现代数学里有哪些本质的结论?
数学系哪门课最难学？
如果从图中移去一个边的一个集合将增加亚图的数目时，被移去的边的集合就成为截。”那么，亚图是什么？截呢？
小学2年级学生能掌握微积分吗？
如何看待 Atiyah 宣布证明了黎曼猜想？
为什么中国开发不出流行的编程语言？