n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
为什么有的人长时间学习也没有取到效果？高一怎么恶补数学？
电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？
哪个瞬间让你觉得一入数学深似海？
如果高考允许以一百万人民币一分的价格无限量购买分数（收入归大学所有），那对社会会有怎样的影响？
求解决这道题目？
数学系大一学生学习数分时看一页书花 20~30 分钟合理吗？
数学证明费了这么大劲把这些东西证明出来，对一个人的人生、对我们身处其中的这个世界，到底有什么影响呢？
有哪些没有（或无法）证明却经常被我们使用的结论或定理？
有限群的群行列式因式分解后，各因式的次数是否与重数相等？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
五子棋先下的一定赢吗？如何证明？如何评价一些数学大佬在推导过程中的「我们不难发现…」、「显然有…」、「易得…」等语言?
有没有休闲级别、能读懂的讲「群论」的书籍？
以下对“真命题的逆命题一定是真命题”的证明错在哪里？
是否存在一个函数，在它定义域内连续，递增，但处处不可导？
程序员在上班的时候允不允许大量的看说明文档来帮助写程序？
如何看待 2020 全国二卷文科高考数学第 3 题以钢琴键为背景？
你的科研之路是怎样的？
请问这到微积分证明题题怎么证?？
理论物理在哪些方面促进了数学的发展？
数学不好能读理科吗?
大一高数完全听不懂怎么办?
请教高人137这个数字做为周期数有啥特别的含义？
数学分析中最重要的定理是哪个？为什么？
如何系统学习机器学习？
若 a=0.248163264128256...，请问 a 是否为有理数？理由是什么？
如何评价清华附中校长王殿军叫停女儿奥数？
我家孩子现在上四年级了，数学特别好，但是语文学习就还没入门，我得怎么办呢？
世界上大约有多少人可以完全看懂并理解怀尔斯对于费马大定理的证明？
如何计算函数 f(x)=log(x)/x 的 n 阶导数？
什么样的数能同时满足「＞0」且「＜0」？
魔方最少知道几个方格就可以推算出其他所有格呢？
下列数字方块移动得到一定排列顺序的问题有解吗？
做数学做得狂躁了，我该怎么平静下来?
游戏只有一个玩家，有 1~9 九张牌，掷俩骰子并设点数之和为 n，此时（详见描述）……？
摩托车真的可能在超高速的情况下从水面穿过吗？
世界上是不是不存在完美的圆？
你数学考过的最低分是多少分？
数学中以 e 为底的指数函数 f(x)=exp(x) 求导后为什么还是它本身？
单调的环境下永生能让人变成傻子吗？