n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
如何推导下面这个等式？你所在的科研领域有哪些做不动的问题？
x＜|1|为什么等于-1＜x＜1？
正方体的体对角线垂直吗？
n趋近于无穷时1/2 + 1/3 +...+ 1/n+1等于多少?
物理系的学生数学学到什么地步合适？
请问如何把所有自然数均分成三类？
游戏只有一个玩家，有 1~9 九张牌，掷俩骰子并设点数之和为 n，此时（详见描述）……？
高数真的好难，就是不会 打死我也不会…也不是没有数学天赋。当今世界中国大学生不会数学有错吗？
自然数 n 的因数个数的数量级估计？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
既然每个程序占用的内存都是操作系统管理的，为什么内存泄漏还是个问题？有没有反三角函数的「和差角公式」？
有哪些指标可以描述两个图（graph）的相似度？
你知道哪些与数学有关的小故事？
如何用简单易懂的例子解释隐马尔可夫模型？
普通外国人算术真的很差吗？
有没有哪些数学题的某一步处理堪称神来之笔？
为何中学阶段不系统讲授一元三次四次方程？总感觉高中数学的很多内容在初中数学上没有根基，完全是空降的？
诺贝尔奖官方公布爱因斯坦成绩单：文理俱佳从小就是学霸，看完你有什么感受？
如何高效自学国内的苏联式风格的数学教材？
一个简单的数学题，作为大学生的你会吗？
如何看待奥运冠军学霸谷爱凌每年暑假回海淀黄庄补奥数，谷妈妈说「来中国上十天课，能在美国顶一年」？
如何理解洛朗级数？
任何自然数都能用包含「1、1、4、5、1、4」这 6 个数字的式子表示吗？
数学竞赛和数学研究有什么区别？
为何这么多人称赞指标定理？
矩形的面积等于长乘以宽，为什么？
如何用数学严谨证明 宾语前置=前置宾语?
如何证明一个有趣的三角恒等式？
人工智能最终会代替数学家或理论物理学家吗？
埃式筛为什么只要筛到根号n就好了？
如何看待一山东14岁高中生高考数学149分、总分699分，考入中科大少年班？与前几天火的某位相比如何？
关于传染病的数学模型有哪些？
人工智能领域有哪些精妙的数学原理？
数学建立的最底层的逻辑基础1+1=2如果被否认后，现在数学及文明的大厦是否会崩溃？
如何证明圆周率中存在所有的 4 位数密码？
无穷级数 ∑ n=1 ∞ ∫ 0 π sin^n x dx 是否收敛？
为什么国内做偏微分方程（PDE）的人这么多，而且招学生非常快？
「奇变偶不变，符号看象限」这句话最早是谁提出来的？
如何理解50个人中至少两个人生日相同的概率高达97%？