母函数总结
母函数
定义 对给定序列\(\{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)\}\)只作为标志用，称为标志函数。
派生1：普通型母函数
当标志函数为\(\{x^{0,1,2,\cdots}\}\)时，即母函数为\(F(x)=\sum_{i=0}^{+\infty}a_ix^i\)，称这类母函数为普通型母函数，可记作\(G(x)\)。
定理1：
设从\(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}
\]
派生2：指数型母函数
当标志函数为\(\{\dfrac{x^i}{i!}\ |\ i=0,1,2,\cdots\}\)时，即母函数为\(F(x)=\sum_{i=0}^{+\infty} a_i(\dfrac{x^i}{i!})\)，称此类母函数为指数型母函数，可记作\(G_e(x)\)。
定理2：
从多重集\(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^k\ (k\in\Z ,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+23^n+1)\frac{x^n}{n!}
\end{aligned}
$$
故\(a_n=\frac{1}{4}(5^n+2*3^n+1)\)。
附录：
推荐的文档 组合数学–母函数与递推 朱全民