n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
哪些看似与图论无关的问题可用图论模型解决？证明「哥德巴赫猜想」到底有多难？
学习经济要达到怎样的数学水平？
数学难还是画画难？
如何评价美国俄勒冈州教育局让全州公立学校的教师们进行「民族性数学」的大讨论？
这个定积分应该怎样计算呢?
有哪些无用的论文、研究？
n! 和 n²，哪个更大呢？
如果一个圆的度数是361°世界会有什么影响？
此函数式如何求最小值？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
这个结论是对的吗？能否初等证明？如何证明圆上若干点构成的多边形最大面积在正多边形时取到？
体现具体与抽象相结合的数学例子有哪些？
不用计算机程序，如何求1，2，…，n中所有与n互素的数的平方和？
上初三的女儿对我说，觉得学数学、化学、物理什么的都没有意义，我该怎么回答她？
为什么n为素数时，n能整除2^n - 2，怎么证明?
中国有哪些描写随机过程的古诗词？
“太阳从西边或东边出来”是必然事件，随机事件还是不可能事件？
有哪些有趣的数学史？
下雨的时候，跑与不跑落在身上的雨点是一样多的吗？为什么？
如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？
为什么有那么多人不承认0.9无限循环=1，且振振有词？
下面这个题该如何做？
是否有多人认为程序员的工作就是复制粘贴？为什么？
我在网上淘到一本1930年的数学论文，微分几何方面的，作者DAN SUN，不知哪位大神给证实一下？
经济类问题可以用逻辑来解释吗？
抛掷a0枚硬币，表面朝上的枚数为a1,然后再投掷a1枚硬币类推，这样最后an的概率分布可求吗？
为什么中国学生在国际奥林匹克数学竞赛中经常拿金牌，但却没有获得菲尔兹奖呢？
概率论和实变函数（测度论）有什么联系？
如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？
有哪些玩游戏时能使用的高等数学知识？
如何证明调和级数前n项和（n大于等于2）不为整数？
你喜欢数学吗，为什么？
小学数学为什么不从集合论学起？
如何理解希尔伯特空间？
以「不可证伪」批判中医的人，为什么没有以此批判数学？
国内有哪些基础数学好的大学？
在你的研究领域(物理)里，有哪些数学课是应该在读本科的时候学的？
如何通过卫星图判断这架飞机距离地面的高度？
奥斯曼帝国的数学和自然科学成就如何？