完全图树的计数

完全图树的计数

把两年前的东西忘干净了
n 个结点的无向完全图的生成树的个数

• n 个点的有标号无根树的计数：(n(n-2))
• n 个点的有标号有根树的计数：(n(n-2) imes n=n(n-1))
• n 个点的无标号有根树的计数：
  令
  [S_{n,j}=sum_{1 leqslant j leqslant frac{n}{j}}a_{n+1-i,j} ]
  则有
  [S_{n,j}=S_{n-j,j}+a_{n+1-j} ]
  因此我们得到了求(a_n)比较理想的递推式：
  [a_{n+1}=frac{displaystylesum_{i leqslant j leqslant n}ja_j S_{n,j}}{n} ]
  根据这个递推式，我们就可以求出(A(z)):
  [A(z)=z+z^2+2z^3+4z^4+9z^5+20z^6+48z^7+115z^8+286z^9+719z^10+1842z^11+... ]

• n 个点的无标号无根树的计数：
  • 当n是奇数时，无根树共有(displaystyle{a_n-sum_{1 leqslant i leqslant frac{n}{2}}a_i a_{n-i}})
  • 当n是偶数时，无根树共有(displaystyle{a_n-sum_{1 leqslant i leqslant n}a_i a_{n-i}+frac{1}{2}a_{frac{n}{2}}(a_{frac{n}{2}}+1)})