4-1. 一般生成函數

Define Generating Function

$a_0$, $a_1$, $a_2$, ... 為一實數數列，定義 $A$($x$) = $a_0$ + $a_1 x$ + $a_2 x^2$ + ... = $\displaystyle\sum_{i=0}^{\infty} a_i x^i$ 為該數列的生成函數(generating function, GF)

生成函數: 表達數列的方法

Formula of Generating Function

• ($1$ + $x$)$^n$ = $\dbinom{n}{0}$ + $\dbinom{n}{1} x$ + $\dbinom{n}{2} x^2$ + ... + $\dbinom{n}{n} x^n$ = $\displaystyle\sum_{i=0}^n \dbinom{n}{i} x^i$

• $\dfrac{1}{1 - x}$ = $1$ + $x$ + $x^2$ + ... = $\displaystyle\sum_{i=0}^{\infty} x^i$

• $\dfrac{1 - x^{n + 1}}{1 - x}$ = $1$ + $x$ + $x^2$ + ... + $x^n$ = $\displaystyle\sum_{i=0}^{n} x^i$

Extended Binomial Coefficient

$n \in R$，$r \in N$，定義 $\dbinom{n}{r}$ = $\dfrac{ n(n - 1)...(n - r + 1)}{r!}$，稱為廣義二項式係數(extended binomial coefficient)

• $\dbinom{-n}{r}$ = ($-1$)$^r \dbinom{n + r - 1}{r}$

• ($1$ + $x$)$^{-n}$ = $\displaystyle\sum_{r=0}^{\infty} \dbinom{-n}{r} x^r$ = $\displaystyle\sum_{r=0}^{\infty}$($-1$)$^r \dbinom{n + r - 1}{r} x^r$

  $\Rightarrow$ ($1$ - $x$)$^{-n}$ = $\displaystyle\sum_{r=0}^{\infty}$($-1$)$^r \dbinom{n + r - 1}{r}$($-x$)$^r$ = $\displaystyle\sum_{r=0}^{\infty} \dbinom{n + r - 1}{r} x^r$

  ($1 \pm x$)$^{-n}$ = $\dfrac{1}{(1 \pm x)^n}$ = ($\dfrac{1}{1 \pm x}$)$^n$