一些重要式子

• ${\sum }_{i=0}^{\infty }{x}^i=\frac{1}{1?x}$
  推論：
  $\frac{1}{1?ax}={\sum }_{i=0}^{\infty }{a}^i{x}^i$
  $\frac{1}{1?x^k}={\sum }_{i=0}^{\infty }{x}^{ik}$
  $\frac{1}{1?c{x}^k}={\sum }_{i=0}^{\infty }{c}^i{x}^{ik}$

• $(1?x{)}^n={\sum }_{i=0}^n(?1{)}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i$

• $\frac{1}{(1?x^c{)}^k}=({\sum }_{i=0}^{\infty }{x}^{ic}{)}^k={\sum }_{i=0}^{\infty }(\genfrac{}{}{0ex}{}{i+k?1}{k?1})x^{ic}={\sum }_{i=0}^{\infty }(\genfrac{}{}{0ex}{}{i+k?1}{i})x^{ic}$

• ${\sum }_{i=1}^{\infty }\frac{x^i}{i}=\ln \frac{1}{1?x}=?\ln (1?x)$

• ${\sum }_{i=0}^{\infty }\frac{x^i}{i!}=e^x$
  推論：
  $e^{cx}={\sum }_{i=0}^{\infty }\frac{c^i{x}^i}{i!}$
  $e^{?x}={\sum }_{i=0}^{\infty }\frac{(?1{)}^i{x}^i}{i!}$
  $\frac{e^x+e^{?x}}{2}={\sum }_{i=0}^{\infty }[2|i]\frac{x^i}{i!}$
  單位根反演

• $(1+x{)}^a={\sum }_{i=0}^{\infty }{a}^{\underline{i}}\frac{x^i}{i!}$

構造冪級數的小技巧

• 平移：
  
• 拉伸：
  

常系數其次線性遞推

一二階線性遞推數列通項的求法

假設對于數列$F$和遞推系數$C$，當$n\ge k$時有${\sum }_{i=0}^{k}C[i]F[n?i]=0$，則稱$F$滿足 ( $k$階 ) 線性常系數遞推關系。

令$F(x)$為$F[n]$的$OGF$。

考慮構造$F_t(x)$，令$[x^n]F_t(x)=[n\ge k]C[t]F[n?t]$，則$$F_t(x)=C[t]x^t\sum _{i=k?t}^{\infty }F[i]x^i=C[t]x^t(F(x)?\sum _{i=0}^{k?t?1}F[i]x^i)$$

由 $[n\ge k]{\sum }_{i=0}^{k}C[i]F[n?i]=0$ 知，${\sum }_{t=0}^k{F}_t(x)=0$，即
$$\sum _{t=0}^{k}C[t]x^t(F(x)?\sum _{i=0}^{k?t?1}F[i]x^i)=0$$
$$(\sum _{t=0}^{k}C[t]x^t)F(x)=\sum _{t=0}^{k?1}C[t]x^t\sum _{i=0}^{k?t?1}F[i]x^i$$
能夠發現左側出現了一次$C$的生成函數，設為$C(x)$。右側的余項，次數小于 $k$，設為$P(x)$。

則得到$C(x)F(x)=P(x)$，即$F(x)=\frac{P(x)}{C(x)}$。

分式分解

這里介紹的是作用類似的代替品。

考慮找出 $k,p$ 使得 $C(x)\mid (1?x^k{)}^p$，記$A(x)=\frac{(1?x^k{)}^p}{C(x)}$。

則$F(x)=\frac{A(x)P(x)}{(1?x^k{)}^p}$。$A(x)P(x)$ 和 $(1?x^k{)}^p$ 的卷積是容易被表示的。

總結

以上是生活随笔為你收集整理的生成函数化简技巧的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。