n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
小学2年级学生能掌握微积分吗？虚数存在的意义是什么？
我学习数学的时候做总会停止思考，脑子转不过来，连简单的例题都看不懂，是怎么回事？？
怎样计算圆内任意两点间距离的期望值？
2021年高考数学难度如何？大题都有哪些解答思路？毕业之后的你还记得当年考试时的感受吗？
行列式的本质是什么？
从0,2 中选一个数字,从1,3,5中选两个数字,组成无重复数字的三位数,构成奇数的概率是多少？
国内是否有教授现代数学(非应付考试)的机构？
在图像处理中，散度 div 具体的作用是什么？
数学界为何走向抽象？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
如何通俗地解释因子分析？大学数学具体学什么，以及相关的自学用书？
为什么IMO的国家队成员很少有女生？
如果在莫比乌斯带或者球面上下围棋会怎么样？
有人认为，数学的本质是计算，另外一个人认为，数学的本质是免于计算，请问相比之下，谁更有道理？
圆周率的这个连分数展开式怎么证明?
加法交换律 a＋b＝b＋a 是怎么证明的？
如果历史上没有牛顿、莱布尼茨、欧拉、高斯、阿贝尔……等人，我们的科学、技术和文明还有这么强大吗？
为何诺贝尔奖得主大多白发苍苍，但规定得主年龄必须在四十岁以下的菲尔兹奖是数学界的最高荣誉之一？
圆周率里包含你的银行卡密码吗？
如何证明Metropolis Hastings algorithms)能够达到马尔科夫稳态？
为什么国内一流高校的理工科专业的学生大多对民科充满反感和鄙夷？
(lnx)'＝1/x，为什么 (ln3)'≠1/3？
“如果你是一张卷子，我希望我是那份标准答案”是什么意思？
俄罗斯“物理数学中学”的教学模式是什么样的？
哪些数学命题曾经长期被误认为是正确的，但之后被严格证明是错的？
数学上能不能说「2≥1」?
x^7+1=(x^4+x^2+x+1)(x^3+x+1) 是如何分解得到的呢？
可以找到两个质数，他们的比值最接近 π 吗？
研究数学花钱多吗？
数学中的“π”是加何推算的？
单片机编程最早是汇编，然后从汇编转为c语言，那么，c++会不会替代c语言来进行单片机编程 ？
男孩比女孩更擅长数学是真的吗？
「一种科学只有在成功地运用数学时，才算达到了真正完善的地步」是什么意思？
棋类和数学所涉的智商相同吗？
「大数定律现象」的成立是数学推出的结果么？
若零向量没有方向，那它还是向量吗？
为什么不少数学和理论物理的专栏文章喜欢配萌妹子的图？
如何求解洛朗级数?
5⁴³²¹ 与 4⁵³²¹ 哪个更大？