n 座桥，连通 n+1 个岛，有多少种连法？ 第1页
1
nayilus 网友的相关建议:
Cayley公式， 个顶点的不同树总数为 。个顶点，条边的连通图必然为树。因此本题答案即 。
Cayley传统上以Kirchoff定理通过线代证明，下面列出Pitman的一种比较有趣的算两次证明：
假设n个顶点可以组成的不同树总数为 。
现在从一个有个顶点，没有边的图出发，逐渐加入边，直到形成一棵有根树（有固定的根，两棵一样的树如果上面代表根的顶点不同视为不同的有根树），求这些边加入顺序的总数。
算一次：从 棵树之一开始，任选一点为根，有种选法，接下来条边有 种排法，总顺序数为
算两次：从空图开始一条条边加，假设加入 条边，则图中会有 棵互不连通的有根树，现在再增加一条边，这条边的起点可以是 顶点中的任一，终点只能是和起点不同的有根树的根，共 种选择，所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。
所以总共的可能性有
因此 ，即
1
相关话题
你有没有推导过一个复杂的却「贴近生活」的公式？只有三维向量有向量积吗？
证明如果幂级数在收敛圆上一点收敛，那么从圆内沿任意不与圆周相切的方向逼近时有极限？
如果高考允许以一百万人民币一分的价格无限量购买分数（收入归大学所有），那对社会会有怎样的影响？
如何看待卡西·曼夫妇发现的可无缝密铺平面的五边形？
连续的周期函数都有最小正周期吗？
请问以下两个概率问题的答案是否一样？
这道定积分怎么算（据说是某211期末考试题）？
本人文科生 喜欢数学 大学想读数学系但没选物理 怎么办?
下一次数学突破会在哪里？
前一个讨论
一水龙头在高空拧开，垂直下落，水流最细可达多少？
下一个讨论
有哪些有趣的或者是反常识的数学问题？
相关的话题
一道难度较大的不等式问题，请问如何入手？如何通俗易懂地解答双信封悖论？
有哪些一看就会，一做就错的数学题？
数学专业为什么没有那么多劝退贴？
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
如何求如下n阶导数？
数学中，有哪些方程和思想让你体会到了美感？
怎样计算两个不同事物的灰色关联度？
质数在生活中有什么用？
任何自然数都能用包含「1、1、4、5、1、4」这 6 个数字的式子表示吗？
卡尔·马克思的数学水平怎样?
是否有多人认为程序员的工作就是复制粘贴？为什么？
这个实变函数题怎么分析）？
数学建模竞赛中可以用c++代替matlab嘛？
如果高考去掉一科，你会选数学吗？
求大佬指教一道新定义数列问题如何做？
非数学系学的数学离数学探索的前沿有多远？
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？
哪个瞬间让你觉得一入数学深似海？
拓扑学究竟是是一种什么样的学科？
如何证明树的树叶个数比度数不少于3的顶点数多？
这道题该怎么做呢？(数分)？
复数范围内，一个数的整数次方是不是永远只有一个值？以及如何证明一个数的无理数次方对应无穷个值？
初中数学考19分还有救吗？
能不能绕过π，来计算一个圆的面积?
5⁴³²¹ 与 4⁵³²¹ 哪个更大？
如何评价知乎用户@Aries？
(t³+1)/(t+1) 如何化成 t²-t+1？
为什么数学概念中，将凸起的函数称为凹函数？
你认为数学的基本思想方法是什么?