n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
请问这道题能不能带值计算？第6题第(2)问怎么证明？
格林公式教材上的证明是否存在漏洞？
数学证明题可以这样做吗？
是否存在将中国大陆部分一分为二的铁路路线？
如何确定该双变量函数的所有间断点？
假如数学没有了自然数的概念及其性质会怎样？
整數分拆中的分拆函數能否延拓至非整數？
有哪些关于数学哲学的入门书籍？（给数学系的学生看）
一个边长为a的正方形，能否用三个直径为a的圆完全覆盖？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？这道题如何用柯西审敛准则证明收敛?
欧氏空间到自身的局部同胚、连续、满映射，是否一定是单射？
PDE 中的先验估计是什么意思？
高中数学解析几何圆锥曲线大题真的是硬解就能解出吗？
抽水马桶大便时屁股被溅到水，是抬高屁股溅的水会少点还是压低屁股溅的水少点？
Lagrange 如何用连分数理论推导出一次同余方程的通解？
为什么方差要定义成平方？这么定义有什么利弊？如果把方差定义成 |X－E(X)|，这又有什么利弊？
两块完全一样饼，如何平均分给三个人？
这个数学分析的问题该如何求解？
极坐标下，形如 r = (sin(kθ)/sin((n + k)θ)) l 的曲线如何判断形状？
当我用手指划过尺子 3 和 4 刻度之间时，我是否触摸到了 π？
各位大佬有什么好方法证明这个不等式?
如何准备2021高教社杯全国大学生数学建模竞赛？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
运用复数证明平面几何的原理有哪些？
程序员有很厉害，不外传的代码吗？
数学和物理中这些符号到底念什么？来源是什么？
x^2/(1+x^2)^n为什么小于等于1/n?
头发上的漩涡可以弄掉吗？
什么日常现象只能用意想不到的复杂科学或数学来解释？
莱布尼兹发明的微积分符号比牛顿的好在啥地方？
0到1之间所有有理数之和 ，和1到2之间的有理数之和，哪个大？
怎样理解任何有限集都是紧集？
数学家下围棋，水平一定会很高吧？
如何看待两名数学家在家隔离期间，成功破解 109 年前的数学证明难题？具有怎样的价值？
前N个整数的最小公倍数有没有近似公式？
数学中数列有什么技巧？
数列 2，4，6，7，8…… 后面的数字是什么？
数学是怎样走进音乐和国际象棋的世界中的？数学在两者的发展过程中产生了怎样的影响？