带标号的连通图计数
统计 n 个顶点的连通图有多少个，每个顶点有标号。记 f(n) 为带标记的连通图的个数，g(n) 为带标记的非连通图的个数，则 f(n) + g(n) = h(n) = 2^(n(n-1)/2) ；考虑 g(n) 的计数：按照结点 1 所在的联通分量的点数分类，设结点 1 所在联通分量包含 k 点（k = 1 ... n-1）则有 C(n-1, k -1) 种不同情况，每种情况下，结点 1 所在连通分量有 f(k) 种，剩余的 n - k 点组成的图有 h(n-k) 种，所以有递推关系：g(n) = ∑c(n-1, k-1)f(k)h(n-k), k = 1...n ；初始值为 f(1)=1, g(1)=1。
另外，h(n) / h(n-1) = 2^(n(n-1)/2-(n-1)(n-2)/2) = 2^(n-1)，所以 h(n) = h(n-1)2^(n-1)
public class NumberOfConnectedGraph {public static long solve(int N) {long[] f = new long[N+1];// 连通图数目long[] g = new long[N+1];// 非连通图数目long[] h = new long[N+1];// 图数目f[1] = 1; g[1] = 1; h[1] = 1;for ( int n=2; n<=N; n++ ) {// h(n) = h(n-1) * 2^(n-1)h[n] = ( 1 << (n-1) ) * h[n-1];long comb = 1;g[n] = 0;for ( int k=1; k<=n-1; k++ ) {// 递推 c(n-1,k-1) = c(n,k-2)*(n-k+1)/(k-1)comb = (k==1)?1:comb*(n-k+1)/(k-1);g[n] += comb * f[k] * h[n-k];}f[n] = h[n] - g[n]; }return f[N];}// 测试public static void main(String[] args) {int[] v = { 3, 4, 5, 6 };for ( int x : v ) {System.out.println(solve(x));}}}