n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
一个函数的不定积分存在有哪些必要条件或者充分条件？怎么计算概率积分 ∫[0, +∞) (e^(-x²))dx？
怎么看待考研数学老师李林「神押题」？
如何看待山东大学泰山学堂数学取向要做大量的大物实验？
目前 x³＋y³＋z³＝42（x、y、z 均为整数）是怎么求解的？
∑ (1/n) 为何不收敛？
想要学习流形的话需要哪些预备知识？
如何计算 sqrt(tan x) 在 0 到 π/2 的定积分？
Fabrice Bellard 是个什么水平的程序员？
天赋一般是不是不适合学数学？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
我今年 14 岁，想了一个数学思路，把数学各领域的联系写出来了，这个思路有什么问题吗？能否通过列举一些代数式、方程加以分析、说明，直观解释阿贝尔定理（Abel–Ruffini th.）？
全序关系和偏序关系的区别是什么？
如何计算 sqrt(tan x) 在 0 到 π/2 的定积分？
一道数学分析题? 应该如何做呢?
如何用李雅普诺夫第二法分析非线性系统在每个平衡点处的稳定性？
有一函数F(x)，其导数为F`(x)，现在它们共同出现在同一等式里，是否能计算出F(x)的表达式？
S²×S¹是否可以嵌入到R⁴中？
怎么建立复数与实数的一一对应？
这种游戏规则是否有必胜策略？
为什么 lnx 求导是 1/x？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
代数好的人但立体几何不好的男生是智商低吗？
中国的物理学、数学在未来一段时间内有望跻身世界领先水平，或者说能够成为世界的一个重要数学或物理中心吗？
数学这种东西也许有用，但是，如何在现实生活当中用到它？
哥德巴赫的猜想如果被证实，对数学和全人类有什么意义？
在没有能量损失的理想台球桌上任意击球，球是否最终必然进洞？
假如一个人立志要在有生之年攻克哥德巴赫猜想，那他应该付出哪些努力？
数学中的充分条件、必要条件如何理解？
怎么看待搞民科的人?
为什么三体中说改变数学规律是很可怕的？
有限域上为什么有x的m次方=e的解的个数不超过m？
除了π，e，0.618，还有没有其他一些有特殊意义的数？
为什么大多数物理公式中乘法和乘方相比加法来说占了多数？
救命，现在我是考研阶段，在自习室看见一个男生?
定量生物学（系统生物学、计算生物学、理论生物学）是否将成为未来生命科学研究的热点？
与1相邻的实数存在吗？
2 的 100 次方到底有多大？
如何尽可能精确地称量 π 斤肉？
如何理解「数学中可行的在物理学中并不一定可行，反之亦然」？