n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
AI 有可能代替人类从事数学研究吗？综合除法的数学依据是什么？
学习数论图论有必要先学抽代和高代吗？
数学学来有什么用？
斐波那契数列倒数和收敛吗，是多少？
如何更深入理解物理意义或概念？
学习计算几何是什么样的体验？
方程 x³+y³+z³=33 是否存在整数解？
（回答前请阅读描述）吐槽小学数学一边进水一边排水问题的现象到底说明了什么(已更新)？
如何评价由杨振宁Atiyah等众多领域泰斗编著的《拓扑和物理》? 有哪些阅读收获？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
一些人为什么会去选数学专业？十个人赛跑第一名和一百人赛跑的第十名，谁厉害？
柯西审敛原理是证得收敛还是一致收敛?
如何证明这个图的染色问题？
负数的正无穷趋于0吗例如（-1/2）的正无穷？
请问B项和D项有什么区别吗？
微分和导数的关系是什么？两者的几何意义有什么不同？为什么要定义微分 ?
体现具体与抽象相结合的数学例子有哪些？
这个积分怎么处理?
威尔逊定理中 p=4是一个例外，为什么？是否存在其他非质数的例外？
离散型随机变量有没有概率密度？
请问这道积分题如何证明？
如何计算下面的级数？
如何在田字格中作出一个正三角形？
请问一下数学上是否有什么定理已经被证明，但是还没找到相对应的例子（实例）？
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？
0到1之间所有有理数之和 ，和1到2之间的有理数之和，哪个大？
为什么喝醉的人可以走回家，喝醉的鸟却不能飞回家？
高斯作出正 17 边形的依据是什么？
普通人对于现代数学各个分支的理解难度，从高到低排名是怎样的？
为什么祖冲之的355/113等于3.1415929而不是3.1415926?
二维世界真的可能存在吗？如果存在，如何去理解它？
如何使用LaTeX模板写数学建模论文或自己写模板？
诗歌《冰雹之路》，大家觉得如何？
哪些伟大的数学家没有自己的传人或后代的？
请问这两个数分不等式如何证明?
大一数分高代需要努力才能学好是不是意味着天赋不够？
熵权TOPSIS法和投影寻踪法解决数学建模评价类问题各有什么特点？
如何看待《中国科学报》刊文评论美女数学博士后获奥运冠军：其实没啥了不起？
Γ（i）怎么算？