树可以看成是无环的连通图
做两个假设
1. N个节点是彼此不同的，例如
1 -- 2 -- 3 和 1 -- 3 -- 2是两棵不同的树
2. 节点的相互顺序无关，例如
1 -- 2 和 2 -- 1是同一棵树
令N个节点可以生成$f[n]$棵树，那么可以得到
$f[1]=f[2]=1;$
$f[n+1]=n*f[n]+\sum_{i=1}^{n-1}f[i]*f[n-i]*C_n^i/2$
解释：
第一个因式表示, 已经有N个节点的树, 则第(N+1)个节点和其中任何一个节点相连都可以构成一棵新的树；
第二个因式表示，已经有N个节点的树，将其分成两个连通分支，第(N+1)个节点和两个连通分支都加一条边可以构成一棵新的树
原文：https://www.cnblogs.com/hazel-wu/p/11688907.html