学习

完全图树的计数

Wider · 1月26日 · 2020年 · · 2368次已读

完全图树的计数

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

  • n 个点的有标号无根树的计数:n(n-2)
  • n 个点的有标号有根树的计数:n(n-2)\times 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{\displaystyle\sum_{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)}
0 条回应