n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
如果你来讲《高等代数》课程，你会如何设计？本科阶段数学系的你的一天是怎么度过的？
如何计算一只鸡的表面积？
为什么各个位数之和是3的倍数的数能被三整除？其他的数为什么不行？
做科研时，都遇到过哪些灵光乍现（Eureka Moment）？
在数学中，为什么我们要视悖论为洪水猛兽？这难道不是在歧视悖论吗？
如何评价 V. I. Arnold 的文章《On Teaching Mathematics》？
C语言指针难吗？如何看待数学大v认为指针比范畴论还难？
21世纪以来（基础）数学在社会科学中有哪些应用？
请问为什么 sin（A+B）=sinAcosB+cosAsinB，有没有详细推导呢？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
想知道这个定积分怎么算?∫[0-1]（arcsin√x）/√(1-x+x^2)dx？牛顿的数学知识储备如何？
如何推导以下几种连分数表示？
俄罗斯的数学教育为什么那么强大？
数值分析中割线法的收敛阶是如何证明的?
“二分之一乘二等于一”，在这个算式里面“二分之一”该如何定义？
为什么在应用上高斯消元法很少被用来求逆矩阵?
如何用最短的距离走过北京所有线路的地铁？
数学建模入门请问要学习什么?
如何理解庞加莱对偶（Poincare Duality）?
弧的长度与弦的长度之比的极限为1，能严格证明吗？
如何证明 π > 3.05 ？
在没有GUI的时代(只有一个文本界面），人们是怎么运行多个程序的？
下面这个关于质数的不等式如何证明？
怎么证明一条线是凸函数?
格林公式为什么不对称啊？
教儿子减法，个位不够要向十位借，儿子问「十位不肯借怎么办」该如何回答？
如何推导下面这个等式？
下雨的时候，跑与不跑落在身上的雨点是一样多的吗？为什么？
小学数学为什么不从集合论学起？
对人类推动最大的学科是物理还是数学？
相对论刚提出时，号称全球能完全理解的人不超过十人，现在却成为理工科必修课程，是我们智商提高了吗？
哪种形状的方糖拥有恒定的溶解速率?
逃离丧尸包围的游戏，你能否逃生？
如何求圆周上随机 n 点构成的 n 边凸包的平均面积？
如何通俗易懂地解释卷积？
数学是绝对真理吗？
2 的 100 次方到底有多大？
如何看待Michael Atiyah爵士疑似证明黎曼猜想，并将在9月24日宣讲？
从自然数 1 ~ n 中随机取 m（1≤m≤n）个，其中最大数的数学期望是多少？