n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
【组合数学】这个魔术有什么策略吗？无限大的围棋盘上某个子的存活概率是多少？
为什么特征值之和会等于矩阵的迹？
如何用初等方法证明k阶齐次线性常系数递推数列的通项公式？
1²＋2²＋……＋1005² 是奇数还是偶数？
圆周率 π 在实际工程领域最多用到了多少位？
印刷体的数学符号在手写的时候有哪些规范？
数学建模竞赛要不要和喜欢的女生组队？
如何用根号表示Sin1°?
理论物理在哪些方面促进了数学的发展？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
100名囚犯猜红绿灯，最多能保证多少人猜对？∑ (1/n) 为何不收敛？
你的生活有没有因为你对数学的热爱，或者坚持有什么影响和改变？
如何看待 bilibili up主 Happylee 对 0.999...≠1 的证明？
《从一到正无穷》第三章的空间想象是什么意思？
三门问题(蒙提霍尔悖论)变种，如果主持人不知道哪个门是汽车随便蒙门打开正好是羊这时观众还需要换门吗？
经济类问题可以用逻辑来解释吗？
是否存在一个世界，这个世界没有任何关于物理化学甚至数学方面的性质，只是一个单纯的世界？
怎么求x的x次方n阶导？
宝宝一岁半左右，如何避免过早的数学启蒙会抑制她的创造力和想象力？
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？
如何证明若行列式 D 中有两行元素分别对应成比例，则 D=0？
如何证明 sinsin…sinx 极限为 0？
这个用什么方法呢？
从一副麻将（136 张）中任取 n 张，总能用其中 14 张组成和牌形，那么 n 至少是多少？
工具变量 (Instrumental variables) 的作用到底是什么？
如何将无穷级数Σ1/n²写成定积分的形式？
假设我们已知三角形内角和为180度,那么(凸)多边形的内角和是如何计算的（用数学方法论的方法解决)?
有哪些不同的物体,他们沿所有轴的转动惯量都相同?
无穷维流形是什么意思？
很多高效排序算法的代价是 nlogn，难道这是排序算法的极限了吗？
在其他宇宙，1+1 可能 = 3 么？
Jean-Pierre Demailly教授于2022年3月17日去世，如何评价他对数学的贡献？
如何看待科学网发布文章称「我国数学家证明 NP=P」，是真的吗？如果是，会带来怎样的影响?
有没有可能一个数学证明是错的，然而所有人都没注意到呢？
是否可以用积分证明球面三角形的面积为 S＝A＋B＋C－π？
有且仅有函数e^x的导数与本身相等吗？如何证明？
最短的可以造成崩溃且编译器无法优化掉的 C++ 代码是什么？
中国真的在文化、数学上都曾经领先世界几百年吗？
专业的数学家只擅长证明不擅长使用数学吗？