n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
为什么法国历史上产生了如此多的一流数学家？设H包含n个非零复数，关于复数乘法组成n阶群，证明H＝{n个n次单位根}，怎么证明呢，谢谢大家了？
这道题如何用柯西审敛准则证明收敛?
如何更深入理解物理意义或概念？
「物理的本质是数学」和「数学是物理的工具」，哪一种说法更正确？
关于悬链线问题，除了变分法，有什么巧妙解法吗？
你最喜欢的数学家是谁，为什么？
为什么说数学建模中，层次分析法(AHP)很low？
数学系的鄙视链是什么？
求大佬指教一道新定义数列问题如何做？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
柯西审敛原理是证得收敛还是一致收敛?整个宇宙是不是都比不上一个葛立恒数？
没有阿拉伯数字、拉丁字母和希腊字母，古代中国的数学是什么样的情况？
为什么有限维赋范线性空间中的范数是等价的？
如何评价2021年第37届全国中学生数学竞赛决赛（CMO）？
为什么中国本土出不了拿菲尔兹奖的数学家？
比较高深的数学在经济学有哪些运用相当漂亮？
如何评价文章《我为什么不认为韦东奕会有大成就》？
矩形的面积等于长乘以宽，为什么？
缠论是唯一用数学证明了的理论，谁能说说这是怎么回事？
环中不可逆元一定是零因子嘛？
在线性代数中如何用几何表示非方阵矩阵相乘？
为什么「数学」不属于「自然科学」？
有理数a/b的乘法为什么能先定义下来，为什么不怕会有问题?
如何看待的法兰西的数学水平？
0.0……1中0的个数是无穷尽的，也就是说永远都不会出现1，那么0.0…1存在的意义是什么？
既然勒贝格积分是黎曼积分的改进，那为什么还要学黎曼积分？淘汰黎曼积分，直接学勒贝格积分不好吗？
如何把微信群/QQ群构造成一个阿贝尔群？
请问这个关于全排列的图论结论如何证明？
小数点后可以有无数位，为什么两个物体仍可以相互接触？
一个程序员多年累计编写一百万行代码是什么体验？
请问如何理解极限的精确定义？
处处不连续的函数乘以一个非 0 连续函数连续么？
根号 2 是无理数，每位小数都是 0~9 之间的数，为什么相乘之后全是 0？
比较高深的数学在经济学有哪些运用相当漂亮？
有没有一套统一的办法处理非初等的原函数？
如果高中生跑步速度超过光速，会被北京体育大学保送吗？
如何评价四川大学数学学院付昌建老师?
既然牛顿的导数理论是有问题的，为什么现在高中依然在教牛顿的导数理论而不是威尔斯特拉斯的 ε-δ 语言？
这道组合难题怎么解?