考研相關文章參考資料為 wjungle 大神提供的筆記

L4 生成函數

L4-1 一般生成函數

定義

對數列 a0,a1,a2,…a_0,a_1,a_2,\ldots，定義

A(x)=a0+a1x+a2x2+⋯=∑n=0∞anxnA(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n

稱 A(x)A(x) 為數列 (an)(a_n) 的 generating function (生成函數)。

Note
  • (1+x)n=∑r=0n(nr)xr(1+x)^n=\displaystyle\sum_{r=0}^{n}\binom nrx^r
  • 1+x+x2+⋯=11−x=∑n=0∞xn1+x+x^2+\cdots=\displaystyle\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n
    • 為數列 1,1,1,…1,1,1,\ldots 的 GF
  • 1+x+x2+⋯+xn=1−xn+11−x1+x+x^2+\cdots+x^n=\displaystyle\frac{1-x^{n+1}}{1-x}
    • 為數列 1,1,…,1,0,0,…1,1,\ldots,1,0,0,\ldots 的 GF
Note
  • (nr)=n(n−1)⋯(n−r+1)r!\binom nr=\frac{n(n-1)\cdots(n-r+1)}{r!}
  • (−nr)=(−1)r(n+r−1r)\displaystyle\binom{-n}{r}=(-1)^r\binom{n+r-1}{r}
  • (1+x)−n=∑r=0∞(−1)r(n+r−1r)xr\displaystyle(1+x)^{-n}=\sum_{r=0}^{\infty}(-1)^r\binom{n+r-1}{r}x^r
  • 1(1−x)n=∑r=0∞(n+r−1r)xr\displaystyle\frac{1}{(1-x)^n}=\sum_{r=0}^{\infty}\binom{n+r-1}{r}x^r
範例

rr 個相同球放至 nn 個相異箱子。

  • 允許空箱

    • 一個箱子的 GF: 1+x+x2+⋯+xr1+x+x^2+\cdots+x^r

    • 總 GF: Ar(x)=(1+x+⋯+xr)nA_r(x)=(1+x+\cdots+x^r)^n

    • 取 xrx^r 係數: (11−x)n=∑k=0∞(n+k−1k)xk\displaystyle\left(\frac1{1-x}\right)^n=\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^k 計算。

    • 方法數: (n+r−1r)\displaystyle\binom{n+r-1}{r}

  • 不允許空箱

    • 一個箱子的 GF: x+x2+⋯+xrx+x^2+\cdots+x^r

    • 總 GF: Br(x)=(x+x2+⋯+xr)nB_r(x)=(x+x^2+\cdots+x^r)^n

    • 取 xrx^r 係數時: (x1−x)n=xn∑k=0∞(n+k−1k)xk\displaystyle\left(\frac{x}{1-x}\right)^n=x^n\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^k 計算。

    • 方法數: (r−1r−n)=(r−1n−1)\displaystyle\binom{r-1}{r-n}=\binom{r-1}{n-1}；若 r<nr<n 則為 00

L4-2 整數分割

Note

令 PnP_n 表示 nn 的整數分割數: P0=1,P1=1,P2=2,P3=3,P4=5P_0=1,\quad P_1=1,\quad P_2=2,\quad P_3=3,\quad P_4=5

PnP_n 相當於將 nn 個相同球放至 nn 個相同箱子，允許空箱的方法數。

P(x)=∑n=0∞Pnxn=11−x⋅11−x2⋅11−x3⋯=∏k=1∞11−xk P(x)=\sum_{n=0}^{\infty}P_nx^n =\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^3}\cdots =\prod_{k=1}^{\infty}\frac{1}{1-x^k}

第 kk 個因子 11−xk=1+xk+x2k+⋯\frac1{1-x^k}=1+x^k+x^{2k}+\cdots，表示整數 kk 可出現 0,1,2,…0,1,2,\ldots 次；因此 xnx^n 的係數即為 PnP_n。

  • 針對 PnP_n 僅需要計算前 nn 項的相乘之係數
  • 奇數分割: Po(x)=11−x⋅11−x3⋅11−x5⋯P_o(x)=\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdots
  • 偶數分割: Pe(x)=11−x2⋅11−x4⋅11−x6⋯P_e(x)=\frac{1}{1-x^2}\cdot\frac{1}{1-x^4}\cdot\frac{1}{1-x^6}\cdots
  • 相異分割: Pd(x)=(1+x)(1+x2)(1+x3)⋯P_d(x)=(1+x)(1+x^2)(1+x^3)\cdots

L4-3 指數生成函數

定義

對數列 a0,a1,a2,…a_0,a_1,a_2,\ldots，定義

A(x)=∑n=0∞anxnn!A(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}

稱 A(x)A(x) 為數列 (an)(a_n) 的 exponential generating function (指數生成函數，EGF)。

Note
  • ex=∑n=0∞xnn!=1+x1!+x22!+x33!+⋯\displaystyle e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots
  • e−x=1−x1!+x22!−x33!+⋯\displaystyle e^{-x}=1-\frac{x}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots
  • 1+x22!+x44!+⋯=ex+e−x2\displaystyle 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots=\frac{e^x+e^{-x}}{2}
  • x1!+x33!+x55!+⋯=ex−e−x2\displaystyle \frac{x}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots=\frac{e^x-e^{-x}}{2}

L4-4 求和算子

Note

設 A(x)=∑n=0∞anxn=a0+a1x+a2x2+⋯A(x)=\sum_{n=0}^{\infty}a_nx^n=a_0+a_1x+a_2x^2+\cdots

令 Sn=a0+a1+⋯+anS_n=a_0+a_1+\cdots+a_n 為 ana_n 的 partial sum，則
S(x)=11−xA(x)S(x)=\frac{1}{1-x}A(x) 為數列 SnS_n 的 GF

稱 11−x\frac{1}{1-x} 為 sum operator。

範例