漏了有些不能到达那些情况,贴一点代码,
例如n = 6 是还可以分成两个3 连通集合
      
.-----.
 \  /
  \/

.-----.
 \  /
  \/


下面是递推公式:
Cnk(n,k) = n!/( k! * (n-k )! //组合公式
fact(k) = (k + 1)!/2         //都能相互到达,树
Pnk(n,k) = n * (n - 1) * ....(n - k) //排列公式 
f (n+1)  += Cnk(n, k) * fact(k+1) * f(n-k)( k = 2, 3, ...n - 3)
	+= Pnk(n,k) / 2 * f(n - k)( k = 2, 3, ...n - 3);
int main( )
{
	int N;
	scanf("%d",&N);
	BigInt Pnk(1);
	BigInt Fact(12);
	BigInt f[101];
	f[3] = 1;
	f[4] = 3;
	f[5] = 12;
	for(int n = 5; n < N; n++)
	{
		Pnk = n * (n - 1) / 2;
		Fact *= n;
		f[n + 1] = Fact;
		for(int k = 2; k <= n - 3; k++)
		{
			f[n + 1] += f[n - k] * Pnk;
			Pnk *= n - k;
		}
	}
	f[N].print();
	return 0;
}
n = 100:
结果如下
2471641764938128875384537111032337276789146403463070281544942559167144414390282180693506917092587398129354739513362308403613446732362107926985081552594712451