最近沒什么心情更新博客，原來的文章可能永遠都不會修改
由于學校組合數(shù)學課即將學到拉反，所以預(yù)習一下
拉反的描述：給定一個形式冪級數(shù)\(F(x)\)滿足方程關(guān)系\(x=\frac{F(x)}{G(F(X))}\)，它是代數(shù)組合學最重要的定理之一。
\(F\)可能沒有解析解，有時我們想要求出\(F\)的某項系數(shù)可以使用拉反（必須滿足\(G\)的常數(shù)項為\(0\)）：\([x^n]H(F(x))=\frac{1}{n}[x^{n-1}]H'(x)G(x)^n\)
拉反存在解析和組合證明，但是這里先不寫（而且組合證明考試也不會考）。
應(yīng)用：例1：數(shù)列\(\{a_i\}\)滿足\(a_0=1,a_{n+1}=\sum_{i+j+k=n}a_i+a_j+a_k\)，求\(a_n\)
解：假設(shè)\(a\)的母函數(shù)為\(F(x)\)，根據(jù)題意有\(F(x)=xF(x)^3+1,\frac{F(x)-1}{F(x)^3}=x\)
令\(G(x)=F(x)-1\)，得到\(\frac{G(x)}{(G(x)+1)^3}=x\)。由于\(a_0=1,[x^0]G(x)=0\)
根據(jù)拉反令\(H(x)=1\)，得知\([x^n]G(x)=\frac{1}{n}[x^{n-1}](x+1)^{3n}=\frac{1}{n}\binom{3n}{n-1}\)
例2（ABC222H）：轉(zhuǎn)化后得到方程\(F=x(F+(F+1)^2)^2\)
所以\(\frac{F}{(F+(F+1)^2)^2}\)，根據(jù)拉反得知\([x^n]F(x)=\frac{1}{n}[x^{n-1}](x+(x+1)^2)^{2n}\)
\(=\frac{1}{n}[x^{n-1}]\sum_{i=0}^{2n}\binom{2n}{i}x^i(x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{2n}\binom{2n}{i}[x^{n-1}]x^i(x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{n-1}\binom{2n}{i}[x^{n-1-i}](x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{n-1}\binom{2n}{i}\binom{4n-2i}{n-1-i}\)，顯然可以在\(O(n)\)時間內(nèi)計算。
例3：證明\((a+b)(a+b+n)^{n-1}=\sum_{k=0}^n\binom{n}{k}a(a+k)^{k-1}b(b+n-k)^{n-k-1}\)
考慮計算\(e^{(a+b)F(x)}\)，\(F(x)=xe^{F(x)}\)
首先把\(e^{(a+b)F(x)}\)當做一個整體運用拉反，得到\([x^n]e^{(a+b)F(x)}=\frac{1}{n}[x^{n-1}](a+b)e^{(a+b)x}e^{nx}\)
\(=\frac{1}{n}[x^{n-1}](a+b)e^{(a+b+n)x}=\frac{1}{n}(a+b)(a+b+n)^{n-1}\frac{1}{(n-1)!}\)
然后顯然\(e^{(a+b)F(x)}=e^{aF(x)}e^{bF(x)}\)
\([x^n]e^{aF(x)}e^{bF(x)}=\sum_{i=0}^n([x^i]e^{aF(x)})([x^{n-i}]e^{bF(x)})\)
首先計算\([x^i]e^{aF(x)}\)，根據(jù)拉反可以得到\([x^i]e^{aF(x)}=\frac{1}{i}[x^{i-1}]\)
例4：證明