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

## Generating Function

1. $1+x+\cdots +x^n = \frac{1-x^{n+1}}{1-x}, x\neq 1$
2. $1+x+x^2+\cdots = \frac{1}{1-x}, \left| x \right|\lt 1$
3. $1+2x+3x^2+\cdots = \frac{1}{(1-x)^2}$
4. $\sum\limits_{r=0}^{\infty}\binom{-n}{r}x^r = \sum\limits_{r=0}^{\infty}(-1)^r\binom{n+r-1}{r}x^r = (1+x)^{-n}$
5. 若 $A(x) = \sum\limits_{n=0}^{\infty}a_nx^n, B(x) = \sum\limits_{n=0}^{\infty}b_nx^n, C(x) = A(x)B(x) = \sum\limits_{n=0}^{\infty}c_nx^n$ 則 $c_n = \sum\limits_{i=0}^{n}a_ib_{n-i}$

### 求係數問題

> Find the coefficient of $x^7$ in $\frac{x^2-3x}{(1-x)^5}+3x^7+5$.

$$
\begin{equation}
\begin{split}
\frac{x^2-3x}{(1-x)^5}+3x^7+5 &= (x^2-3x)\sum\limits_{i=0}^{\infty}\binom{-5}{i}(-x)^i + 3x^7+5 \\
&=(x^2-3x)\sum\limits_{i=0}^{\infty}\binom{4+i}{i}(x)^i + 3x^7+5
\end{split}
\end{equation}
$$

得 $x^7$ 的係數為 $\binom{9}{5}-3\cdot \binom{10}{6} + 3$

***

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

$$
\begin{equation}
\begin{split}
\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\limits_{i=0}^{\infty}\left( \frac{x}{3} \right)^i - \frac{2}{5}\sum\limits_{i=0}^{\infty}\left( \frac{x}{5} \right)^i
\end{split}
\end{equation}
$$

$x^n$ 的係數： $2\lbrack 3^{-(i+1)}-5^{-(i+1)} \rbrack$

### 生成函數的組合意義

#### $n$ 相異物可重複取 $r$ 件組合方法數

$G(x)=(1+x+x^2+\cdots)^n$ 中 $x^r$ 的係數即為所求

$G(x) = \left( \frac{1}{1-x} \right)^n = \sum\limits_{i=0}^{\infty}\binom{n+i-1}{i}x^i$

故所求即 $\binom{n+r-1}{r}$

#### $n$ 相異物不可重複取 $r$ 件組合方法數

$G(x) = (1+x)^n = \sum\limits_{i=0}^{\infty}\binom{n}{i}x^i$

$x^r$ 係數為 $\binom{n}{r}$ 即為所求

#### $r$ 相同物投入 $n$ 相異箱，不允許空箱的方法數

$G(x) = (x+x^2+\cdots)^n = \left( \frac{x}{1-x} \right)^n = x^n \sum\limits_{i=0}^{\infty}\binom{n+i-1}{i}x^i$

取 $i = r-n$ 得 $x^r$ 係數為 $\binom{r-1}{r-n}$ 即為所求

### 整數的無序分割

設分割整數 $n$ 時，數字 $i$ 出現了 $x_i$ 次，$i=1,2,\cdots ,n, x_i\ge 0$
即 $\sum\limits_{i=1}^{n}i\cdot x_i = n$

其整數解組數即為 $n$ 之分割數

$$
\begin{equation}
\begin{split}
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{split}
\end{equation}
$$

所求即 $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\limits_{i=0}^{\infty}\frac{(nx)^i}{i!}$

故所求為 $n^r$

#### $m$ 相異物放入 $n$ 相異箱，不允許空箱的方法數

$G(x) = (\frac{x}{1!}+\frac{x^2}{2!}+\cdots)^n = \sum\limits_{i=0}^{\infty}(-1)^i\binom{n}{i}\sum\limits_{j=0}^{\infty}\frac{(n-i)^jx^j}{j!}$

所求即 $\frac{x^m}{m!}$ 之係數： $\sum\limits_{i=0}^{\infty}(-1)^i\binom{n}{i}(n-i)^m$

### 應用題

> 由 $0, 1, 2, 3$ 組成長度為 $n$ 的字串中，含有偶數個 $0$ 的字串有幾個？

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

$\frac{x^n}{n!}$ 係數：$\frac{4^n + 2^n}{2}$ 即為所求