01.md

{{ book.discrete_mathematics.chapter4.4_1.title }}

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 $$