一个计数问题。给定一个数N()，问N个点N条边的labeled connected graph有多少个。用英语说简单点，中文有点纠结，就是顶点可区分的连通图个数。

这道题我感觉很有一写的价值，至少对我而言，纠结了我好几天。为了搞定它，这几天想了很多种方法，走了无数错误的路线，甚至异想天开的在wikipedia上狂搜二维生成函数的资料看。问题没解决，新知识倒是学了不少。最后还是灵光乍现，想到了一步重要变换，问题才迎刃而解。不过我也只是得出了数学解，到现在我也没有找到对这个公式的直观解释，所以还望牛人释疑。

好，下面言归正传。其实大家一打眼就能看出来，N个点N条边还连通，那实际上就是一棵树上带着一个环。我的一个想法（预先提示一下，完全错误的想法）自然就是枚举环上的点的个数k，共有种可能。剩下的N-K个点呢，自然就是分成一些组连在一起，然后再挂在这个环上。假设分成了m组，这样每个组挂在长度为k的环上的任意一处，共有种可能，而N-k个点分成m组，每个组组内的元素还顺序还不可忽略，这不就是个第一类Stirling数么，也就是。所以再枚举一下组的个数m，总的表达式就变成了。观察一下能发现，后面这个对m求和的东西，正好就是第一类Stirling数的生成函数取在k点的函数值。这样的话整个式子就变成了，而这个东西稍微动一下脑子就可以在的时间内算出来。整个问题好像解决了，还完美的用到了第一类Stirling数的生成函数，不是么？错了。因为每一个组挂在环上并不是k种选择，否则就是默认每一个挂在外面分支只能是一条线，而实际上挂在外面的分支可以是多种形态，对吧。所以这种方法悲剧了。这是我的第一个想法。

好。下面换一个思路，从另外一个角度考虑问题。考虑一下每种可能的结构，它要么有叶子（就是指度为1的点），要么没有叶子。没有叶子的含圈的连通图就是一个圈，所以第二种很简单就能计数，应用第一类Stirling数有结果。第一种有叶子的，假设叶子数为k，我们就可以先删掉一个叶子，这样剩下的图是一个N-1个点N-1条边的连通图。可能敏锐的人已经发现了，这一段弄好了可以动态规划，所以需要仔细的设计一下。删掉一个叶子之后，整个图还会剩下多少叶子呢？可能有k-1个，但是可能仍然存在k个，因为删掉叶子之后，它连接的点可能会变成新的叶子。所以我们需要把图的叶子数K也加入动态规划的状态。对于一个M个点K个叶子的树，用代表它的结构个数，加入一篇新的叶子，如果叶子数增多了一个，那么连接的点必然就是内部节点，选择共有M-K种；如果叶子数不变，那么必然连接的是叶子，选择有K种；由于顶点可区分，所以原始M-1个点的树中顶点编号的组合共有种，还要再乘以一个M。但是这样计数又会发生重复，因为K片叶子的树的每一个叶子在计算的时候，都把这棵树算了一遍，所以还要除以一个K。总的来说，就会出现下面一个递推公式：。边界条件即为。以这个公式计算，就会得到一个的动态规划算法。

这种计数法是没错的，而且没有什么纠结的地方。但是很明显，如果的算法就能解决这个问题，那世界也会清静许多了，本日志也就没有任何存在的价值了。所以不用多说，算法最后的下场就是可耻的失败鸟。这迫使我们不得不对上面这个递推式做更进一步的优化。很明显，上面的式子可以等价写成下面的形式：;。我们注意到，将这个递推式稍微改写，就可以变成下面的形式：。有发现什么了吧，如果令，上式则可变为。

问题到这里好像陷入了僵局。这个方程似乎没有什么很好的办法求下去了，似乎又是一步死路。不过且慢，你会发现两类Stirling数的递推公式和它非常的相似，如果能尽量的向其靠拢，或许会出现转机。所以，我们可以考虑一下下面这个数。令，带入上式，则会发现递推公式变成了下面的形式：。对，不用揉眼睛，你没看错，这不和第二类Stirling数的递推公式完完全全的吻合么？然后我们再仔细看一下我们要求的东西变成了什么。是M个节点中有k个叶子的该图的个数，而由于这个图中有一个环，环上至少有3个点，所以叶子数最多也就是M-3，我们要计数的东西其实是。把这个公式中的T用F带入一下，就是。有没有发现这个是什么东西？这个不就是第二类Stirling数的生成函数在M点处的函数值么？F的递推式又正好满足第二类Stirling数的递推表示，这不就可以仿照求第二类Stirling数生成函数的做法去做了么？

所以，下面的步骤其实就很简单了。令。要求的就是的函数值。回想一下第二类Stirling数生成函数的求法，根据公式带入，即可得到一个关于g的递推式：，初值为。根据这个递推式，很容易就可以得出一个在时间内计算任意的算法，递推时顺便将带入即可。

PS: 这个递推式是否能更进一步的简化，也就是说，直接求出个closed form来，甚至设计一个的算法？这个我暂时就不知道了，没什么精力去做了。的算法已经够了。另外，有牛人能直观的解释一下这个公式的道理么？