题目： 求 n n n个点的无向连通图个数
思路： 设 G ( n ) G(n) G(n)表示无向图的个数， F ( n ) F(n) F(n)表示 n n n个点的无向图连通的个数，则 G ( n ) = 2 ( n 2 ) 枚 举 每 条 边 选 不 选 G ( n ) = ∑ i = 1 n ( n − 1 i − 1 ) F ( i ) ⋅ 2 ( n − i 2 ) 枚 举 1 号 点 所 在 连 通 块 有 几 个 点 \begin{aligned} G(n)&=2^{{n\choose 2}}\quad 枚举每条边选不选\\ G(n)&=\sum_{i=1}^{n}{n-1\choose i-1}F(i)\cdot2^{{n-i\choose 2}}\quad 枚举1号点所在连通块有几个点 \end{aligned} G(n)G(n)=2(2n)枚举每条边选不选=i=1∑n(i−1n−1)F(i)⋅2(2n−i)枚举1号点所在连通块有几个点 所以 2 ( n 2 ) = ∑ i = 1 n ( n − 1 i − 1 ) F ( i ) ⋅ 2 ( n − i 2 ) 2 ( n 2 ) ( n − 1 ) ! = ∑ i = 1 n F ( i ) ( i − 1 ) ! 2 ( n − i 2 ) ( n − i ) ! \begin{aligned} 2^{{n\choose 2}}&=\sum_{i=1}^{n}{n-1\choose i-1}F(i)\cdot2^{{n-i\choose 2}}\\ \frac{2^{{n\choose 2}}}{(n-1)!}&=\sum_{i=1}^{n}\frac{F(i)}{(i-1)!}\frac{2^{{n-i\choose 2}}}{(n-i)!}\\ \end{aligned} 2(2n)(n−1)!2(2n)=i=1∑n(i−1n−1)F(i)⋅2(2n−i)=i=1∑n(i−1)!F(i)(n−i)!2(2n−i) 令 C ( i ) = 2 ( i 2 ) ( i − 1 ) ! , A ( i ) = F ( i ) ( i − 1 ) ! , B ( i ) = 2 ( i 2 ) i ! , A ( 0 ) = 0 , C ( 0 ) = 0 C(i)=\frac{2^{{i\choose 2}}}{(i-1)!},A(i)=\frac{F(i)}{(i-1)!},B(i)=\frac{2^{{i\choose 2}}}{i!},A(0)=0,C(0)=0 C(i)=(i−1)!2(2i),A(i)=(i−1)!F(i),B(i)=i!2(2i),A(0)=0,C(0)=0， 令 C = ∑ i = 0 ∞ C ( i ) x i , A = ∑ i = 0 ∞ A ( i ) x i , B = ∑ i = 0 ∞ B ( i ) x i C=\sum_{i=0}^{\infty}C(i)x^i,A=\sum_{i=0}^{\infty}A(i)x^i,B=\sum_{i=0}^{\infty}B(i)x^i C=∑i=0∞C(i)xi,A=∑i=0∞A(i)xi,B=∑i=0∞B(i)xi C ( n ) = ∑ i = 0 n A ( i ) B ( n − i ) C = A ∗ B A = C ∗ B − 1 \begin{aligned} C(n)&=\sum_{i=0}^{n}A(i)B(n-i)\\ C&=A*B\\ A&=C*B^{-1} \end{aligned} C(n)CA=i=0∑nA(i)B(n−i)=A∗B=C∗B−1 用多项式求逆即可
