n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
整数和偶数真的是「一样多」的吗？（我知道康托尔那套，但这个表述真的正确吗？）？环中不可逆元一定是零因子嘛？
英国人真的连乘法口诀都不熟悉么？
智商极高是怎样的体验？
如果规定数 j 满足 j 的绝对值为 -1 ，数集会不会有新的扩充？
为什么英美大学都这么厉害？
八股取士/微积分是否为教育上的「毒瘤」？
数学系学渣怎么写毕业论文呢？
计算机大神可以破解卡牌游戏通过不氪金获得想要的卡牌吗？
如何通俗地解释泰勒公式？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
科学为何有那么多近似计算？这样是不是和科学的严谨性相违背？科学为何有那么多近似计算？这样是不是和科学的严谨性相违背？
在三角形abc中，∠B=90°，点D在边BC上，∠BAD=2∠C，AC=12,DC=8求AB？
对任意一个u∈C（复数域），是否有｜ln（1+u）｜≥ln（1+｜u｜）？
如何分析 2021 亚太杯数学建模ABC题？思路代码是什么？
无理数为什么能用图形表示出来？
数学类研究的科研经费用在哪里？
为什么英美大学都这么厉害？
什么是数学之美？
是什么让你对数学或物理感兴趣的？
如何用数论证明 3^x＋4^x＝5^x 只有一个实数解？
如何证明该级数收敛?
如果一个圆的度数是361°世界会有什么影响？
既然微分和积分互为逆运算，为什么积分比微分更难求解？
有哪些用普通人的知识水平就可以巧妙证明的数学难题？
构造微分流形这个概念的动机是什么？
研究了一辈子学问却发现研究的方向错了，或当前流行的理论错了，你会有怎样的感想？你会怎样做？
这道怎么求极限?
为什么不能计算两次哈希，以及在什么情况下不能计算两次哈希？
i 的 i 次方是实数吗？
如何证明R^2上的不可数集至少在一点附近局部不可数啊？
韦东奕 与 高考秒杀数学程伟大神，谁的数学水平更高？如何看待程伟的相关言论？
真的有什么式子能表示圆周率吗？
学什么数学，为什么不直接学逻辑，为什么不把数学改成逻辑？
为什么程序都要用英文写，中文不行吗？
如果哥德巴赫猜想是由现代的普通人提出，是否会被人认可？
若零向量没有方向，那它还是向量吗？
奶茶咖啡等饮料全换成纸吸管到底能降低多少污染？
nπ-［nπ］是否存在收敛于0的子列？
诗歌《冰雹之路》，大家觉得如何？