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

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

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

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

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

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

所以，下面的步骤其实就很简单了。令[;g(x, y) = \sum_{k=3}^{x}F(x, k)y^{(k)};]。要求的就是[;g(N, N);]的函数值。回想一下第二类Stirling数生成函数的求法，根据公式[;xx^{(k)} = x^{(k+1)} + kx^{(k)};]带入，即可得到一个关于g的递推式：[;g(x, y) = yg(x-1, y) - \frac{y!}{2x(x-1)(y-x)!};]，初值为[;g(3, y) = \frac{y(y-1)(y-2)}{6};]。根据这个递推式，很容易就可以得出一个在[;O(N);]时间内计算任意[;g(N, y);]的算法，递推时顺便将[;y = N;]带入即可。

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