n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
有哪些玩游戏时能使用的高等数学知识？为什么在数轴上随便取一个点，一定取到的是无理数？
有哪些数学定理或者数学知识惊呆了你？
存在一点的极限值不等于该点的函数值吗？
如果变量X Y独立怎么证明E(X+Y)=E(X)+E(Y),E(XY)=E(X)E(Y)？
你所见过的最美的数学公式是什么？
这个级数应该怎么计算呢?求解答?
这个问题怎么做?最后怎么解出多项式？
有且仅有函数e^x的导数与本身相等吗？如何证明？
学习数论图论有必要先学抽代和高代吗？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
对任意无理数，都存在有理数列趋近于这个无理数，为什么，怎么找这个有理数列？为什么英美大学都这么厉害？
能否求出n次对称群中置换的最大阶？
看看题目?那个才是对的，为什么？
对这个图有什么看法？
为什么数学专业要学计算机？
矩阵思维是什么意思？
如何评价IMO（国际奥数） 2019中国队团体总分与美国并列第一，重新夺回团体桂冠？
如何评价2019年高考全国卷数学?
在学生时期独立地探索出自己的数学发现，是什么体验？
为什么样本方差（sample variance）的分母是 n-1？
如何理解数学证明中的容易验证？
既然负数开平方可以拓展出一个复数系，那 1/0 也可以拓展出新的数系吗？
是否存在一个世界，这个世界没有任何关于物理化学甚至数学方面的性质，只是一个单纯的世界？
为什么任何阶数等于其定义空间维数的全反对称张量在该空间中坐标系转动下不变？
准高一学生想自学数学有什么建议吗？
是否存在将中国大陆部分一分为二的铁路路线？
面积有限的物体，周长是否有限？
f（x,y)->(x,y),是2维实数空间的 一一映射函数，f连续，f的反函数是否也连续，why？
这个题怎么求概率？
是否存在多项式 f(x)、g(x)、m(y)、n(y)，使得 (xy)²+xy+1=fm+gn？
请问这个三重积分怎么计算？
从上海沿G318国道一路向西到西藏，用什么速度行驶可以做到“出发时天刚开始暗下来，到达时天正好全黑”？
假如一个人立志要在有生之年攻克哥德巴赫猜想，那他应该付出哪些努力？
代数几何是不是被神化了？
希尔伯特空间、内积空间的定义有什么关系和区别？
各类科研领域中哪些公式，原理或定律的推出，用到了有趣的思维方式？
现在希尔伯特的23个问题都研究得怎么样了？
平均多少个 [a, b] 间的随机数之和才大于 c？
学完泛函分析可以做哪些事情？