n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
以数学史的观点来看，集合论是如何成为数学基础的？如何比较这两个数的大小?
有没有哪个素数可以以多种方式写成两个正整数的平方和？
如何通俗地讲解「仿射变换」这个概念？
QQ 群为什么叫 QQ 群，而不叫 QQ 环，QQ 域或者 QQ 格？
目前 x³＋y³＋z³＝42（x、y、z 均为整数）是怎么求解的？
有哪些有趣的概率问题？
这个结论是对的吗？能否初等证明？
基础薄弱怎么学好高中数学？
如何看待清华大学数学新领军计划和丘班综合测试？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
“如果你是一张卷子，我希望我是那份标准答案”是什么意思？如下图，这个级数如何求出来呢？
「只要整数的各个位数之和是 3 的倍数，那么这个整数就一定是 3 的倍数」是如何证明的？
被人问，数学上为什么减去一个负数等于加它的相反数（这种规定从何而来）？
有什么学习数学的好网站？
累加的连续是积分，那么累乘的连续是什么？
实变泛函都是很容易的课，为何说「实变函数学十遍，泛函分析心犯寒」？
如果在一个密闭空间里给一个普通人1亿年的时间，他可以推演出现在的数学定理吗？
请问如何用拉格朗日插值法及其推论解决此题？
为什么英美大学都这么厉害？
你所见过的被引用次数最多的文献是哪本？
学什么数学，为什么不直接学逻辑，为什么不把数学改成逻辑？
有理数域加减乘除都是封闭的，那为什么部分无理数可以表示为有理数加减后的无穷级数呢？
根号 2 与根号 3 之和约等于 π，这是巧合，还是有什么特殊意义？
为什么数学专业要学计算机？
既然勒贝格积分是黎曼积分的改进，那为什么还要学黎曼积分？淘汰黎曼积分，直接学勒贝格积分不好吗？
4x5的表写入20个不同正整数，相邻数不互质，表中最大的数至少是多少？
你认为你所在学科最杰出的思想是什么？
现代理论物理的新成果中，有没有因为使用不严格的数学最后被证明因此导致错误结果的案例？
为什么实系数多项式方程的虚数解总是成对出现？
学经济金融专业，高考后假期需要做什么准备（特别是数学方面）？
哪个瞬间让你觉得一入数学深似海？
泊松换元公式有直接用二重积分换元而不变为曲面积分的方法吗？
为什么虚数不能比大小？
中国象棋的走法是有限的吗？如果有限，有没有先走或者后走的人必赢的可能？
现代数学是不是比大学数学中优雅的结论少了很多？
如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？
证明n维线性空间中任何n+1个向量都线性相关。?
拿破仑时代的炮兵究竟数学要多好？
家人们，帮我看看这个极限?