生成函數初探

對給定序列\(\{a_{0,1,2,\cdots}\}\) 構造一個函數\(F(x)=\sum_{i=0,1,2,\cdots}a_if_i(x)\)，稱\(F(x)\)為序列\(\{a_{0,1,2,\cdots}\}\)的生成函數。其中，序列\(\{f_{0,1,2,\cdots}(x)\}?\)只作為標志用，稱為標志函數。

普通型生成函數(OGF)

當標志函數為\(\{x^{0,1,2,\cdots}\}\)時，即生成函數為\(F(x)=\sum_{i=0}^{+\infty}a_ix^i\)，稱這類生成函數為普通型生成函數，可記作\(G(x)\)。

卷積

OGF: \(F(x),G(x)\) 的卷積\(F(x)*G(x)=\sum_{i=0}^{+\infty} (\sum_{j=0}^i a[j]*b[i-j]) x^i?\)。

定理

設從\(n\)元集合\(S=\{a_{1,2,\cdots,n}\}\)中取\(1,2,\cdots\)個元素組合，若限定元素\(a_i\)出現次數的集合為\(M_i\ (1\le i\le n)\)，則該組合數序列的生成函數為:
\[ \prod_{i=1}^n(\sum_{x\in M_i}x^m) \]

常用到的普通型生成函數有：
\[ \begin{aligned} &\frac{1}{1-x}&&=1+x+x^2+x^3+\cdots\\ &(\frac{1}{1-x})^2&&=1+2x+3x^2+4x^3+\cdots\\ &(\frac{1}{1-x})^n &&=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots \end{aligned} \]

例題

求\(n\)位十進制正數中出現偶數個\(5?\)的數的個數。

設\(a_i\)表示\(i\)位十進制正數中出現偶數個\(5\)的數的個數，\(b_i\)表示\(i\)位十進制正數中出現奇數個\(5\)的數的個數，不難得出：
\[ \left. \begin{aligned} a_n&=9a_{n-1}+b_{n-1}\\ b_n&=9b_{n-1}+a_{n-1}\\ a_1&=8\\ b_1&=1 \end{aligned} \right\}(0) \Rightarrow \left. \begin{aligned} a_n-9a_{n-1}-b_{n-1}=0\\ b_n-9b_{n-1}+a_{n-1}=0\\ \end{aligned} \right\} \]
設序列\(\{a_n\}\)，\(\{b_n\}\)的生成函數分別為：
\[ \begin{align} A(x)&=a_1+a_2x+a_3x^2+\cdots &&(1)\\ B(x)&=b_1+b_2x+b_3x^2+\cdots &&(2) \end{align} \]
由\(-9x*(1)-x*(2)+(1)\)得：
\[ (1-9x)A(x)-xB(x)=a_1=8\qquad(3) \]
再由\(-x*(1)-9x*(2)+(2)\)得：
\[ (1-9x)B(x)-xA(x)=b_1=1\qquad(4) \]
由\((3)\)、\((4)\)可得：
\[ \left. \begin{aligned} A(x)&=\frac{-71x+8}{(1-8x)(1-10x)}\\ B(x)&=\frac{1-x}{(1-8x)(1-10x)} \end{aligned} \right\} \]
更進一步的，
\[ \begin{aligned} A(x)=\frac{7/2}{1-8x}+\frac{9/2}{1-10x}=\frac{1}{2}*(7*\sum_{n=0}^{+\infty}(8x)^n+9*\sum_{n=0}^{+\infty}(10x)^n) \end{aligned} \]
即:
\[ a_x=\frac{7}{2}*8^{x-1}+\frac{9}{2}*10^{x-1} \]

指數型生成函數(EGF)

當標志函數為\(\{\dfrac{x^i}{i!}\ |\ i=0,1,2,\cdots\}\)時，即生成函數為\(F(x)=\sum_{i=0}^{+\infty} a_i(\dfrac{x^i}{i!})\)，稱此類生成函數為指數型生成函數，可記作\(G_e(x)\)。

卷積

EGF: \(F(x),G(x)\) 的卷積\(F(x)*G(x)=\sum_{i=0}^{+\infty} (\sum_{j=0}^i \begin{pmatrix}i\\j\end{pmatrix} a[j]*b[i-j]) \dfrac{x^i}{i!}\)。

定理

從多重集\(M=\{\infty*a_1,\infty*a_2,\infty*a_3,\cdots,\infty*a_n\}\)中選區\(1,2,3,\cdots\)個元素排列，若元素\(a_i\)出現的次數集合為\(M_i\ (1\le i\le n)\)，則該排列數序列的生成函數為：
\[ \prod_{i=1}^n(\sum_{m\in M_i}\dfrac{x^m}{m!}) \]
所謂多重集（multiset）之于集合（set），英文寫出來差不多就懂了。函數\(\dfrac{x^m}{m!}\)中，除以\(m!\)是因為排列中這\(m\)個相同元素的先后是不考慮的。

常見的指數型生成函數（\(e^x\)的Tylor展開式）：
\[ \begin{aligned} &e^x &&=\sum_{n=0}^{+\infty}\frac{x^n}{n!} &&=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \\ &e^{kx}\ (k\not=0)&&=\sum_{n=0}^{+\infty}\frac{(kx)^n}{n!} &&=1+kx+\frac{(kx)^2}{2!}+\frac{(kx)^3}{3!}+\cdots \\ &(e^x+e^{-x})/2 &&=\sum_{n=0}^{+\infty}\frac{x^{2n}}{(2n)!} &&=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}\cdots \\ &(e^x-e^{-x})/2 &&=\sum_{n=0}^{+\infty}\frac{x^{2n+1}}{(2n+1)!} &&=x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}\cdots \end{aligned} \]

例題

求由\(1,3,5,7,9\)這\(5\)個數字組成的\(n\)位數字的個數（每個數字出現次數可以為\(0\)，且\(3,7\)出現的次數為偶數）。

設滿足條件的\(r\)位數字的數目為\(a_r\)（特別地，規定\(a_0=1\)），則序列\(a_0,a_1,a_2,\cdots\)的生成函數為：
\[ G_e(x)=(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots)^2(1+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\cdots)^3 \\ \because\quad \left\{\begin{aligned} &(e^x+e^{-x})/2 &&=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\\ &e^x &&=1+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\cdots \end{aligned}\right.\\ \begin{aligned} \therefore\quad G_e(x) &=\frac{1}{4}(e^x+e^{-x})^2e^{3x}\\ &=\frac{1}{4}(e^{5x}+2e^{3x}+e^x)\\ &=\frac{1}{4}\sum_{n=0}^{+\infty}(5^n+2*3^n+1)*\frac{x^n}{n!} \end{aligned} \]
故\(a_n=\frac{1}{4}(5^n+2*3^n+1)\)。

與多項式的結合應用 洛谷5162

推薦的文檔 組合數學--生成函數與遞推 朱全民