n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
闭区间上的导函数f'有界，是否可以在闭区间上取到最大值，最小值？如果历史上没有牛顿、莱布尼茨、欧拉、高斯、阿贝尔……等人，我们的科学、技术和文明还有这么强大吗？
勾股数有有限多组还是无限多组？
极坐标表示 5000 到 50000 之间的素数为什么会形成一条螺旋线？
为什么中国本土出不了拿菲尔兹奖的数学家？
在三角形abc中，∠B=90°，点D在边BC上，∠BAD=2∠C，AC=12,DC=8求AB？
请问下面这道题怎么解决？
统计学中「矩」这个概念是怎么引入的？它为什么被称为矩？它与物理意义上的矩有什么相同与不同？
圆内均匀随机地取三个点，三点确定的新圆在旧圆内的概率是多少？
孩子今年六年级，数学一塌糊涂，作为家长该怎么帮助她提升成绩？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
不同国家和制度的数学PhD成才率（永久学术职位）是多少？有多大差别？关于凑微分上下限的一个小小疑问？
知乎现在都有哪些值得关注的严肃输出？
怎么回答很多人看到哪个大公司的系统就跑过来问你帮我做这个大概要多少钱？
学经济金融专业，高考后假期需要做什么准备（特别是数学方面）？
为什么写程序的时候可以坚持很久，但是学习数学就很难保持注意力？
下面的组合等式是否恒成立？
怎么计算概率积分 ∫[0, +∞) (e^(-x²))dx？
[-5e^(2i*π)+1*3]/2=1*4这一串有什么特殊意义吗？
数理金融和金融工程需要修的数学课程有哪些?
如何证明R^2上的不可数集至少在一点附近局部不可数啊？
大学线性代数怎么求四阶行列式？
在一个现实中的数轴上可以找出无理数吗？
阿⻄莫夫三定律，会不会被打破？
有没有大佬会算这个无穷级数？
n 座桥，连通 n+1 个岛，有多少种连法？
MIT 学者算出 π=3.115，是 π 的值变了吗？
请问可以给出一个自己对于所在生存空间(宇宙)的终极解释吗?(可公式理论，可想象，可哲学)?
“二分之一乘二等于一”，在这个算式里面“二分之一”该如何定义？
身份证号不会用完吗？
自旋为 1/2 的粒子是什么形状的？三维空间真的有转两圈才能和自己重合的形状吗？
中国有哪些描写随机过程的古诗词？
如何定义数？
你认为一个游戏的黄金游玩时长有多久？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
为什么前人花了大量时间，用他们的聪明才智发现的定理，后人只要花相对很少的时间就能弄明白？
到底是奇数多还是偶数多？
一个什么学历的人在知乎上自称证明了哥德巴赫猜想会有人相信？
数学系学渣怎么写毕业论文呢？
数学家如何定义无穷大？有人能在数学上证明无限存在吗？