首頁 自修課程 (大學) 離散數學

# 一般生成函數

# 定義

設一數列為:a0,a1,a2...,ana_0,a_1,a_2...,a_n
定義A(x)=a0+a1x+...+anxn+...=∑n=0∞anxnA(x) = a_0+a_1x+...+a_nx^n+... = \sum^{\infty}_{n=0}a_nx^n
稱為ana_n 的生成函數 generating function(GF)

# 公式

  1. (1+x)n=∑r=0n(nr)xr(1+x)^n= \sum^n_{r=0}\binom{n}{r}x^r: 二項式定理
  2. 1+x+x2+...=11−x1+x+x^2+...=\frac{1}{1-x}: 無窮等比級數
  3. 1+x+x2+...+xn=11−x−xn+11−x=1−xn+11−x1+x+x^2+...+x^n=\frac{1}{1-x}-\frac{x^{n+1}}{1-x} = \frac{1-x^{n+1}}{1-x}

# 例子

  1. (n0)+(n1)+...+(nn)=2n\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n} = 2^n
  2. 20(n0)+21(n1)+...+2n(nn)=3n2^0\binom{n}{0}+2^1\binom{n}{1}+...+2^n\binom{n}{n} = 3^n
  3. 1(n0)+2(n1)+...+n(nn)=n2n−11\binom{n}{0}+2\binom{n}{1}+...+n\binom{n}{n} = n2^{n-1}
  4. ∑r=0n(nr)xr=(1+x)n\sum^n_{r=0}\binom{n}{r}x^r = (1+x)^n
note

(nr)=n!r!(n−r)!=n(n−1)(n−2)...(n−r+1)r!,n∈R\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{n(n-1)(n-2)...(n-r+1)}{r!},n\in \mathbb{R}: 代數定義
eg.(123)=12×−12×−323!\binom{\frac{1}{2}}{3} = \frac{\frac{1}{2}\times\frac{-1}{2}\times\frac{-3}{2}}{3!}

  1. (−nr)=−n(−n−1)(−n−2)...(−n−r+1)r!=(−1)r×n(n+1)(n+2)...(n+r−1)r!=(−1)r×(n+r−1r)\binom{-n}{r} = \frac{-n(-n-1)(-n-2)...(-n-r+1)}{r!} = (-1)^r\times\frac{n(n+1)(n+2)...(n+r-1)}{r!} = (-1)^r\times\binom{n+r-1}{r}
  2. (1+x)−n=∑r=0∞(−nr)xr=∑r=0∞(−1)r(n+r−1r)xr(1+x)^{-n} = \sum^{\infty}_{r=0}\binom{-n}{r}x^r = \sum^{\infty}_{r=0}(-1)^r\binom{n+r-1}{r}x^r
  3. (1−x)−n=∑r=0∞(−1)r(n+r−1r)(−x)r=∑r=0∞(n+r−1r)xr(1-x)^{-n} = \sum^{\infty}_{r=0}(-1)^r\binom{n+r-1}{r}(-x)^r = \sum^{\infty}_{r=0}\binom{n+r-1}{r}x^r

# 整數分割

把一整數切分成若干正整數和的方法數

note

令PnP_n 表示整數分割數，例:P1=1,P2=2,P3=3,P4=5P_1 = 1,P_2 = 2,P_3=3,P_4=5
令P0=1P_0=1，PnP_n 相當於nn 個相同物放置在nn 個相同箱子，允許空箱的方法數
令p(x)=∑n=0∞pnxn=11−x×11−x2×11−x3p(x) = \sum^{\infty}_{n=0}p_nx^n=\frac{1}{1-x}\times \frac{1}{1-x^2}\times\frac{1}{1-x^3}，
則11−x×11−x2×11−x3\frac{1}{1-x}\times \frac{1}{1-x^2}\times\frac{1}{1-x^3}中xrx^r 係數為Pr,1≥r≥nP_r,1\ge r\ge n

更新於 閱讀次數 次

用實際行動犒賞爆肝的我😀

Zrn Ye LinePay

LinePay