Chapter2
介绍不同类型常用于生成函数的级数
1.形式幂级数
-
定义：在形式幂级数中，\(x\)从来不指定一个数值，且对收敛和发散的问题不感兴趣，感兴趣的是系数序列\((a_0,a_1,\cdots,a_n,\cdots)\)，我们研究形式幂级数完全可以归结为讨论这些系数序列，且这些系数序列又可看作含有分量\(a_0,a_1,\cdots,a_n,\cdots\)的无穷矢量，系数\(a_0\)称为级数的常数系数。用近世代数的语言来讲，形式幂级数形成一个环，这个环对加法有单位元（用\(0\)表示），对乘法有单位元（用\(1\)表示），如果从某项以后，形式幂级数的所有系数全为零，它被称为形式多项式。
-
加法
\[\sum_{n}a_nx^n+\sum_{n}b_nx^n=\sum_{n}(a_n+b_n)x^n \] -
乘法
\[\sum_{n}a_nx^n\sum_nb_nx^n=\sum_{n}c_nx^n\quad (c_n=\sum_{k}a_kb_{n-k}) \]
1.1 倒数
由乘法的定义可以定义一个幂级数的倒数，比如
\[(1-x)(1+x+x^2+x^3+\cdots)=c_0=1\\ c_n=a_0b_{n}+a_1b_{n-1}=1-1=0\quad (n\ge 1) \]称\((1-x)\)和\((1+x+x^2+x^3+\cdots)\)互为的倒数
- 定理：一个形式幂级数\(f=\sum_{n\ge 0}a_nx^n\)存在倒数当且仅当\(a_0\ne 0\)。并且可以得到它的倒数\(\frac{1}{f}=\sum_{n\ge 0}b_nx^n\)，其中\(b_0=-\frac{1}{a_0}\)，\(b_n=-\frac{1}{a_0}\sum_{k\ge 1}a_kb_{n-k}\quad (n\ge 1)\)。
1.2 逆
接下来定义幂级数\(f\)的逆：称幂级数\(g\)是\(f\)的逆，则有
\[f(g(x))=g(f(x))=x\\ f(g(x))=\sum_{n}a_ng(x)^n=\sum_{n}a_n(g_0+g_1x+g_2x^2+\cdots)^n \]注意到，如果\(g_0=0\)，那么计算\(x^n\)的系数的时候，只需要取\(g(x)\)的前\(n-1\)项自乘\(n\)次取\([x^n]g(x)^n\)和\(a_n\)相乘即可。如果\(g_0\ne0\)，那么\(g(x)\)就需要自乘无限多次，因为每个\(g_0\)都可以都可以无限地和后面的\(g_n\)匹配
因此两个幂级数的组合\(f(g(x))\)有定义当且仅当\(g_0=0\)或\(f\)是一个多项式
- 定理：令两个幂级数\(f、g\)是满足\(f(g(x))=g(f(x))=x\)的，并且\(f(0)=0\)，那么\(f=f_1x+f_2x^2+\cdots\quad (f_1\ne 0)\)，并且\(g=g_1x+g_2x^2+\cdots\quad (g_1\ne 0)\)
1.3 微分(导数)
定义形式幂级数\(f=\sum_{n}a_nx^n\)的导数为：
\[f^{'}=\sum_{n}na_nx^{n-1} \]- 定理：如果\(f^{'}=0\)，那么\(f=a_0\)，其中\(a_0\)是一个常数
- 定理：如果\(f^{'}=f\)，那么\(f=ce^x\)
2.普通生成函数的计算(OGF)
如果一个级数是收敛的，如果记\(f\)是这个级数的函数表示形式，那么对函数的操作会映射到一个确定的序列操作，本节就是研究这种操作对应的关系。
-
定义\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)表示\(f=\sum_{n}a_nx^n\)
-
Rule1. 如果\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)，并且对整数\(n\gt 0\)，则
\[\left\{a_{n+h}\right\}_n^{\infty}{\overset{ops}{\longleftrightarrow} }\frac{f-a_0-\cdots-a_{h-1}x^h-1}{x^h} \]实际上这个规则是将数列左移\(h\)位
定义\((x\frac{d}{dx})\)为\(xD\)，那么有
\[f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\Longrightarrow(xDf){\overset{ops}{\longleftrightarrow} }\left\{na_n\right\}_0^{\infty} \]更一般地，有
\[(xD)^kf{\overset{ops}{\longleftrightarrow} }\left\{n^ka_n\right\}_0^{\infty} \]- Rule2. 如果\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)，并且\(P\)是一个多项式，那么\[P(xD)f{\overset{ops}{\longleftrightarrow} }\left\{P(n)a_n\right\}_{n\ge 0} \]例子 1：找到\(\sum_{n\ge 0}\frac{(n^2+4n+5)}{n!}\)的闭合公式
令\(P(x)=x^2+4x+5\)，\(f(x)=e^x\)，那么
\[P(xD)f=((xD)^2+4(xD)+5)e^x=x\frac{d}{dx}xe^x+4xe^x+5e^x\\ =(x^2+5x+5)e^x \]例子 2：求自然数前\(N\)项平方和的闭合式
首先有
\[\sum_{n=0}^Nx^n=\frac{x^{N+1}-1}{x-1} \]然后两边同时乘以\((xD)^2\)，并令\(x=1\)，得到
\[\sum_{n=1}^Nn^2=(xD)^2\left\{\frac{x^{N+1}-1}{x-1}\right\}\bigg|_{x=1}=\frac{N(N+1)(2N+1)}{6} \]-
Rule3. 如果\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)并且如果\(g{\overset{ops}{\longleftrightarrow} }\left\{b_n\right\}_0^{\infty}\)，则
\[fg{\overset{ops}{\longleftrightarrow} }\left\{\sum_{r=0}^na_rb_{n-r}\right\}_{n=0}^{\infty} \]推广到\(3\)个这样的相乘，有
\[fgh{\overset{ops}{\longleftrightarrow} }\left\{\sum_{r+s+t=n}^na_rb_sc_t\right\}_{n=0}^{\infty} \] -
Rule4. 如果\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)，并且有一个正整数\(k\)，则
\[f^k{\overset{ops}{\longleftrightarrow} }\left\{\sum_{n_1+n_2+\cdots+n_k=n}a_{n_1}a_{n_2}\cdots a_{n_3}\right\}_{n=0}^{\infty} \]上面就是卷积
例子：
- Rule5. 如果\(f{\overset{ops}{\longleftrightarrow} }\left\{a_n\right\}_0^{\infty}\)，则\[\frac{f}{1-x}{\overset{ops}{\longleftrightarrow} }\left\{\sum_{j=0}^na_j\right\}_{n\ge 0} \]求数列的前\(n\)项和,利用\(\frac{1}{1-x}{\overset{ops}{\longleftrightarrow} }\left\{1\right\}_{n=0}^{\infty}\)和卷积的性质很容证明
例子 1：自然数平方前\(n\)项和
\[\frac{1}{1-x}(xD)^2\frac{1}{1-x}{\overset{ops}{\longleftrightarrow} }\left\{\sum_{j=0}^nj^2\right\}_{n\ge 0} \]展开左边得到
\[\frac{1}{1-x}(xD)^2\frac{1}{1-x}=\frac{x(1+x)}{(1-x)^4} \]利用\(g=\sum_{n}\binom{n}{k}y^n=\frac{y^k}{(1-y)^{k+1}}\)来求\([x^n]\frac{1}{(1-x)^4}\)，取\(k=3\)，得到
\[\left[x^n\right]\left\{x^{-3}g\right\}=\left[x^{n+3}\right]g(x)=\binom{n+3}{3} \]考虑把\(\frac{x(1+x)}{(1-x)^4}=\frac{x}{(1-x)^4}+\frac{x^2}{(1-x)^4}\)分别求第\(n\)项系数，利用同样的方法
\[\left[x^n\right]\frac{x}{(1-x)^4}=[x^n]\left\{x^{-2}g\right\}=[x^{n+2}]g=\binom{n+2}{3}\\ \left[x^n\right]\frac{x^2}{(1-x)^4}=[x^n]\left\{x^{-1}g\right\}=[x^{n+1}]g=\binom{n+1}{3}\\ \]故
\[[x^n]\frac{x(1+x)}{(1-x)^4}=\binom{n+2}{3}+\binom{n+1}{3}=\frac{N(N+1)(2N+1)}{6} \]例子 2：调和级数
\[H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} \quad (n\ge 1) \]很容易想到
\[\frac{1}{1-x}(f=\sum_{n\ge 1}\frac{x^n}{n}){\overset{ops}{\longleftrightarrow} }\left\{H_n\right\}_{n\ge 1} \]考虑如何求\(f\)，注意到\(\frac{x^n}{n}=\int x^{n-1}\)，于是
\[f=\sum_{n\ge 1}\frac{x^n}{n}=\sum_{n\ge 0}\int x^{n}=\int \sum_{n\ge 0}x^n=\int \frac{1}{1-x}=\text{log}(\frac{1}{1-x}) \]所以
\[\sum_{n=1}^{\infty}H_nx^n=\frac{1}{1-x}\text{log}(\frac{1}{1-x}) \]例子 3：证明斐波那契数列满足
\[F_0+F_1+F_2+\cdots+F_n=F_{n+2}+1 \]左边
\[\left\{\sum_{j=0}^nF_j\right\}_{n\ge 0}{\overset{ops}{\longleftrightarrow} }\frac{1}{1-x}F=\frac{1}{1-x}\frac{x}{1-x-x^2} \]右边
\[\left\{F_{n+2}+1\right\}{\overset{ops}{\longleftrightarrow} }\frac{F-F_0-F_1x}{x^2}-\frac{1}{1-x}=\frac{F-x}{x^2}-\frac{1}{1-x} \]然后证明左右两边相等即可
2.3 指数型生成函数的计算(EGF)
-
定义\(f{\overset{egf}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 0}\)表示\(f\)是\(\{a_n\}_{n\ge 0}\)的指数型生成函数为：
\[f=\sum_{n\ge 0}\frac{a_n}{n!}x^n \] -
Rule1. 如果\(f{\overset{egf}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 0}\)，则
\[\left\{a_{n+h}\right\}_{n\ge 0}{\overset{egf}{\longleftrightarrow} }D^hf \] -
Rule2. 如果\(f{\overset{egf}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 0}\)，并且\(P\)是一个多项式，则
\[P(xD)f{\overset{egf}{\longleftrightarrow} }=\left\{P(n)a_n\right\}_{n\ge 0} \] -
Rule3. 如果\(f{\overset{egf}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 0}\),并且如果\(g{\overset{egf}{\longleftrightarrow} }\left\{b_n\right\}_{n\ge 0}\)，那么
\[fg{\longleftrightarrow}\left\{\sum_{r}\binom{n}{r}a_rb_{n-r}\right\}_{n\ge 0} \]例子 1：计算合法括号数为\(n\)的本质不同的字符串个数(不会存在不合法括号，长度为\(2n\))
考虑如何把这样的集合划分，首先开头一定要是
(，那么接下来考虑它的)可以在哪个位置和它匹配，并且只能出现在偶数位置，固定右括号的位置之后，假设位置为\(k\)，那么问题变成了在区间\([2,k-1]\)和区间\([k+1,2n]\)内的合法括号序列的个数，这个问题是独立的。因此可以枚举前一段的括号数量即可。令\(f(n)\)表示合法括号个数为\(n\)的本质不同的字符串的个数，则有
\[f(n)=\sum_{k=1}^{n}f(k-1)f(n-k)\quad (f(0)=1) \]现在考虑用生成函数来表达这个式子，令\(F(x)=\sum_{k}f(k)x^k\)
由递推式可以得到
\[F(x)-1=xF(x)^2 \]因为\(k-1+n-k=n-1\)，求的是第\(n-1\)项，需要乘个\(x\)左序列。然后就可以愉快的解出\(F(x)\)
实际上，这也是一个\(Catalan\)数
例子 2：求错位排列的方案数，记为\(D_n\)，并令\(D(x){\overset{egf}{\longleftrightarrow} }\left\{D_n\right\}_{n\ge 0}\)。
假设我们钦定\(k\)位的数还是在原位上，令其他位是错位的，方案数是\(\binom{n}{k}D_{n-k}\)，注意到这样的划分是无重无漏的，于是可以得到
\[n!=\sum_{k}\binom{n}{k}D_{n-k}\quad (n\ge 0) \]两边同时取\(EGF\)，得到
\[\frac{1}{1-x}=e^xD(x)\\ \]其中
\[\frac{1}{1-x}=\sum_{n}\frac{n!}{n!}x^n{\overset{egf}{\longleftrightarrow} }\left\{n!\right\}_{n\ge 0} \]于是得到
\[D(x)=\frac{e^{-x}}{1-x}\\ \left[x^n\right]D(x)=n!(1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}) \] -
Rule4. 多个 EGF 卷积
\[fgh{\overset{egf}{\longleftrightarrow} }\left\{\sum_{r+s+t=n}\frac{n!}{r!s!t!}a_rb_sc_t\right\}_{n\ge 0} \]自身卷积
\[f^k{\overset{egf}{\longleftrightarrow} }\left\{\sum_{r_1+\cdots+r_k=n}\frac{n!}{r_1!r_2!\cdots r_n!}a_{r_1}a_{r_2}\cdots a_{r_k}\right\}_{n\ge 0} \]
2.4 幂级数的分析理论(看微积分就好了)
2.5 一些有用的普通型级数
\[\frac{1}{1-x}=\sum_{n\ge 0}x^n\\ \]\[\text{log}\frac{1}{1-x}=\sum_{n\ge 0}\frac{x^n}{n}\\ \]\[e^x=\sum_{n\ge 0}\frac{x^n}{n!}\\ \]\[\text{sin}(x)=\sum_{n\ge 0}(-1)^n\frac{x^{2n+1}}{(2n+1)!} \]\[\text{cos}(x)=\sum_{n\ge 0}(-1)^n\frac{x^{2n}}{(2n)!} \]\[(1+x)^{\alpha}=\sum_{k}\binom{a}{k}x^k \]\[\frac{1}{(1-x)^{k+1}}=\sum_{n}\binom{n+k}{n}x^n \]\[\frac{x}{e^x-1}=\sum_{n\ge 0}\frac{B_nx^n}{n!} \]\[\frac{1-\sqrt{1-4x}}{2x}=\sum_{n}\frac{1}{n+1}\binom{2n}{n}x^n \]2.6 狄利克雷级数
定义：记\(f(s){\overset{Dir}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 1}\)表示\(f(s)\)是\(\{a_n\}_{n\ge 1}\)的狄利克雷生成函数，满足
\[f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}\\ =a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+\frac{a_4}{4^s}+\cdots \]-
Rule1. 如果\(f(s){\overset{Dir}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 1}\)，并且\(g(s){\overset{Dir}{\longleftrightarrow} }\left\{b_n\right\}_{n\ge 1}\)，则
\[ f(s)g(s){\overset{Dir}{\longleftrightarrow} }\left\{\sum_{d|n}a_db_{\frac{n}{d}}\right\}_{n\ge 1} \] -
Rule2. 如果\(f(s){\overset{Dir}{\longleftrightarrow} }\left\{a_n\right\}_{n\ge 1}\)，并且\(k\)正整数，则
\[ f(s)^k=\sum_{n\ge 1}n^{-s}\left\{\sum_{n_1n_2\cdots n_k=n}a_{n_1}a_{n_2}\cdots a_{n_k}\right\} \]
定义黎曼函数为\(\zeta(s){\overset{Dir}{\longleftrightarrow} }\left\{1\right\}_{n\ge 1}\)
\[\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s} \]由Rule2，得到
\[[n^{-s}]\zeta^2(s)=\sum_{d|n}1\cdot 1=d(n) \]这里\(d(n)\)表示\(n\)的因子个数
进一步，\([n^{-s}]\zeta^k(s)\)表示数字\(n\)分解成\(k\)个有序因子乘积的方案数，如果不算平凡因子\(1\)，就是\([n^{-s}](\zeta(s)-1)^k\)
- 定理：令\(f\)是一个乘法数论函数，即对所有素数\(m、n\)，满足\(f(mn)=f(m)f(n)\)的函数，则\[\sum_{n=1}^{\infty}\frac{f(n)}{n^s}=\prod_{p}\left\{1+f(p)p^{-s}+f(p^2)p^{-2s}+f(p^3)p^{-3s}\cdots\right\} \]这里的\(p\)是所有的素数
现在把\(\zeta(s)\)换个方式表达
\[\zeta(s)=\prod_{p}\left\{1+p^{-s}+p^{-2s}+\cdots\right\}\\ =\frac{1}{1-p^{-s}}\\ =\frac{1}{\prod_{p}(1-p^{-s})} \]定义和素数的幂次有关的函数，称作莫比乌斯函数
\[\mu(p^a)= \begin{cases} +1,\quad \text{if}\quad a=0\text{;}\\ -1, \quad \text{if}\quad a=1;\\ 0,\quad \ \ \ \text{if} \quad a\ge 2; \end{cases} \tag{1} \]则有
\[\sum_{n\ge 1}\frac{\mu(n)}{n^s}=\prod_{p}\left\{1-p^{-s}\right\} \]因此
\[\frac{1}{\zeta(s)}=\sum_{n\ge 1}\frac{\mu(n)}{n^s} \]即\(\frac{1}{\zeta(s)}{\overset{Dir}{\longleftrightarrow} }\{\mu(n)\}_{n\ge 1}\)
现在进入莫比乌斯反演的推导
假设有两个序列\(\{a_n\}_{n\ge 1}\)和\(\{b_n\}_{n\ge 1}\)，满足
\[a_n=\sum_{d|n}b_d \]现在记它们的狄利克雷生成函数分别是\(A(s)\)和\(B(s)\)，则
\[A(s)=B(s)\zeta(s) \]因此
\[B(s)=\frac{A(s)}{\zeta(s)}\\ b_n=\sum_{d|n}a_d\mu(\frac{n}{d}) \]于是，这就是莫比乌斯反演
例子 1：求长度为\(n\)并且\(0\)和\(1\)个数都是素数的\(01\)串的个数
标签：right,frac,longleftrightarrow,gfology,sum,学习,ge,left From： https://www.cnblogs.com/Arashimu0x7f/p/16662213.html