【資工考研】離散：生成函數

Generating Function

1. $1+x+\cdots +x^n=\frac{1-x^{n+1}}{1-x},x\ne 1$
2. $1+x+x^2+\cdots =\frac{1}{1-x},\left|x\right|<1$
3. $1+2x+3x^2+\cdots =\frac{1}{(1-x{)}^2}$
4. $\sum _{r=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{-n}{r})x^r=\sum _{r=0}^{\mathrm{\infty }}(-1{)}^r(\genfrac{}{}{0ex}{}{n+r-1}{r})x^r=(1+x{)}^{-n}$
5. 若
   $A(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n,B(x)=\sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n,C(x)=A(x)B(x)=\sum _{n=0}^{\mathrm{\infty }}{c}_n{x}^n$ 則
   $c_n=\sum _{i=0}^n{a}_i{b}_{n-i}$

求係數問題

Find the coefficient of

$x^7$ in

$\frac{x^2-3x}{(1-x{)}^5}+3x^7+5$.

$$\begin{array}{rl}\frac{x^2-3x}{(1-x{)}^5}+3x^7+5& =(x^2-3x)\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{-5}{i})(-x{)}^i+3x^7+5\\ & =(x^2-3x)\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{4+i}{i})(x{)}^i+3x^7+5\end{array}$$

得

$x^7$ 的係數為

$(\genfrac{}{}{0ex}{}{9}{5})-3\cdot (\genfrac{}{}{0ex}{}{10}{6})+3$

---

$f(x)=\frac{4}{x^2-8x+15}$

$$\begin{array}{rl}\frac{4}{x^2-8x+15}& =\frac{2}{3-x}+\frac{-2}{5-x}\\ & =\frac{\frac{2}{3}}{1-\frac{x}{3}}+\frac{\frac{-2}{5}}{1-\frac{x}{5}}\\ & =\frac{2}{3}\sum _{i=0}^{\mathrm{\infty }}{\left(\frac{x}{3}\right)}^i-\frac{2}{5}\sum _{i=0}^{\mathrm{\infty }}{\left(\frac{x}{5}\right)}^i\end{array}$$

$x^n$ 的係數：

$2[3^{-(i+1)}-5^{-(i+1)}]$

生成函數的組合意義

$n$ 相異物可重複取

$r$ 件組合方法數

$G(x)=(1+x+x^2+\cdots {)}^n$ 中

$x^r$ 的係數即為所求

$G(x)={\left(\frac{1}{1-x}\right)}^n=\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+i-1}{i})x^i$

故所求即

$(\genfrac{}{}{0ex}{}{n+r-1}{r})$

$n$ 相異物不可重複取

$r$ 件組合方法數

$G(x)=(1+x{)}^n=\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n}{i})x^i$

$x^r$ 係數為

$(\genfrac{}{}{0ex}{}{n}{r})$ 即為所求

$r$ 相同物投入

$n$ 相異箱，不允許空箱的方法數

$G(x)=(x+x^2+\cdots {)}^n={\left(\frac{x}{1-x}\right)}^n=x^n\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+i-1}{i})x^i$

取

$i=r-n$ 得

$x^r$ 係數為

$(\genfrac{}{}{0ex}{}{r-1}{r-n})$ 即為所求

整數的無序分割

設分割整數

$n$ 時，數字

$i$ 出現了

$x_i$ 次，

$i=1,2,\cdots ,n,x_i\ge 0$
即

$\sum _{i=1}^{n}i\cdot x_i=n$

其整數解組數即為

$n$ 之分割數

$$\begin{array}{rl}{F}_n(x)& =(1+x+x^2+\cdots )(1+x^2+x^4+\cdots )(1+x^3+x^6+\cdots )\cdots (1+x^n+x^{2n}+\cdots )\\ & =\frac{1}{1-x}\cdot \frac{1}{1-x^2}\cdot \frac{1}{1-x^n}\end{array}$$

所求即

$F_n(x)$ 中

$x^n$ 之係數

Exponential Generating Function

1. $e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots$
2. $e^{-x}=1-\frac{x}{1!}+\frac{x^2}{2!}-\cdots$
3. $\frac{e^x+e^{-x}}{2}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots$
4. $\frac{e^x-e^{-x}}{2}=\frac{x}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots$

組合意義

$n$ 相異物可重複取

$r$ 件排列的方法數

$G(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots {)}^n$ 中

$\frac{x^r}{r!}$ 之係數

$G(x)=e^{nx}=\sum _{i=0}^{\mathrm{\infty }}\frac{(nx{)}^i}{i!}$

故所求為

$n^r$

$m$ 相異物放入

$n$ 相異箱，不允許空箱的方法數

$G(x)=(\frac{x}{1!}+\frac{x^2}{2!}+\cdots {)}^n=\sum _{i=0}^{\mathrm{\infty }}(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})\sum _{j=0}^{\mathrm{\infty }}\frac{(n-i{)}^j{x}^j}{j!}$

所求即

$\frac{x^m}{m!}$ 之係數：

$\sum _{i=0}^{\mathrm{\infty }}(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i{)}^m$

應用題

由

$0,1,2,3$ 組成長度為

$n$ 的字串中，含有偶數個

$0$ 的字串有幾個？

考慮

$G(x)=(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots ){(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots )}^3=\frac{1}{2}(e^{4x}+e^{2x})$

$\frac{x^n}{n!}$ 係數：

$\frac{4^n+2^n}{2}$ 即為所求