n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
几乎处处收敛和依测度收敛的区别是什么呢？二维空间有四色定理，那三维空间中存在 n 色定理吗？如果有，那么是几色定理？
《图灵传》中讲到「狄拉克基于抽象数学预言了正电子的存在」，其中细节为何？
有哪些定理在高维情况下与三维情况下培养出来的直觉不符？
阅遍所有数学的重要领域的结果是否有可能？
高一新生看欧几里得的几何原本好还是希尔伯特的几何基础好？
一个程序员多年累计编写一百万行代码是什么体验？
关于传染病的数学模型有哪些？
如何理解矩阵的「秩」？
有哪些式子行列式答案等于520？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
我希望中国举办一个更有分量的奥数天才赛，出一些很难的题目和各种猜想，可以花一年解题，吃住在考场可以吗？如何用数学的方法说明极限理论的表现力强于初等数学？
如何证明e为无理数?
1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
质数在生活中有什么用？
如何评价2021年丘赛分析试题？
为什么矩形面积等于长乘宽？
数学分析中最重要的定理是哪个？为什么？
为什么没有开区间上的 R 正常定积分的定义；开区间勒贝格可积，再加什么特殊条件，可得到开区间黎曼可积？
如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？
什么样子的人适合做数学？
请问有什么方法确定，指标的权重?
二维空间的封闭是圆，三维空间的封闭是球，四维空间的封闭是什么？
这种不等式的本质是什么？
这个几何证明题怎么做？
请问，一加一为啥等于二？
如何更深入理解物理意义或概念？
伟大的数学家是如何培养的呢？
一个脑洞：理论上，是否有可能用一根棍子记录无限多的信息？
如何评价 EPFL 数学博士后 Anna Kiesenhofer 夺得东京奥运会女子公路自行车金牌？
如何证明 1^2021＋2^2021＋…＋1000^2021 能被 7、11、13 整除？
物理或化学方程为什么往往是偏微分方程？
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
如何估计这个级数？
如何对幼儿进行数学（不是算数）启蒙？
如何证明该级数收敛?
天赋一般是不是不适合学数学？
如何看待 2021 年 USNews 排名数学学科曲阜师范大学超越北大排名第一，山东科技大学排名第三？
对这个图有什么看法？
这个相关系数背景的证明题如何做？