生成函数1（基础理论）

· · 个人记录

前言：这篇博客只是简单地介绍一下生成函数的基本知识

前置芝士：《组合数学》第二、五章 \quad微积分基础

注意：生成函数都是在一个形式幂级数上操纵的，所以可以不用考虑收敛的问题

牛顿二项式定理 证明

牛顿二项式定理：\displaystyle (x+y)^a=\sum_{k=0}^{\infty}\binom{a}{k}x^ay^{a-k}\quad\quad 其中 x,y,a\in \mathbb{R},|\dfrac{x}{y}|<1

一些简单的变形：\displaystyle (1+z)^a=\sum_{k=0}^{\infty}\binom{a}{k}z^k

令a=-n，那么有：\displaystyle \binom{a}{k}=\binom{-n}{k}=\frac{-n(-n-1)...(-n-k+1)}{k!}=(-1)^k\frac{n(n+1)...(n+k-1)}{k!}=(-1)^k\binom{n+k-1}{k}

又因为：\displaystyle (1+z)^{-n}=\frac{1}{(1+z)^n}

\displaystyle \frac{1}{(1+z)^n}=\sum_{k=0}^{\infty}(-1)^k\binom{n+k-1}{k}z^k \frac{1}{1+z}=\sum_{k=0}^{\infty}(-1)^kz^k

用-z替换z得到：

\displaystyle \frac{1}{(1-z)^n}=\sum_{k=0}^{\infty}\binom{n+k-1}{k}z^k \frac{1}{1-z}=\sum_{k=0}^{\infty}z^k

普通生成函数（OGF）

设h_0,h_1,h_2,...,h_n为无穷数列，它的普通生成函数为无穷级数：

g(x)=h_0+h_1x+h_2x^2+...+h_nx^n+...

一些例子：

1,1,1,...$的OGF：$\displaystyle g(x)=1+x+x^2+...+x^n+...=\frac{1}{1-x} \displaystyle \binom{m}{0},\binom{m}{1},...,\binom{m}{m}$的OGF：$\displaystyle g(x)=\sum_{i=0}^{m}\binom{m}{i}x^i=(1+x)^m

OGF的运算：

\displaystyle (\sum_{n=0}^{\infty}a_nx^n)\pm(\sum_{n=0}^{\infty}b_nx^n)=\sum_{n=0}^{\infty}(a_n\pm b_n)x^n \displaystyle (\sum_{n=0}^{\infty}a_nx^n)(\sum_{n=0}^{\infty}b_nx^n)=\sum_{n=0}^{\infty}(\sum_{i=0}^{n}a_ib_{n-i})x^n \displaystyle \frac{d}{dx}(\sum_{n=0}^{\infty}a_nx^n)=\sum_{n=0}^{\infty}(n+1)a_{n+1}x^n
\displaystyle \frac{d}{dx}(a_nx^n)=a_nnx^{n-1}
\displaystyle \int (\sum_{n=0}^{\infty}a_nx^n)dx=\sum_{n=1}^{\infty}a_{n-1}\frac{x_n}{n}+C

注意这里求的是不定积分，还有一个常数项的问题

\displaystyle \int (a_nx^n)dx=a_n\frac{x_{n+1}}{n}

积分和求导通常是用来偏移项的

一个具体的例子：通过OGF解决计数问题

确定苹果、香蕉、橘子和梨的n组合的个数，其中：苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，梨的个数是0/1

设h_n表示n组合数的方案，令数列h的OGF为g(x)，考虑为每一种水果引入一个因子

\displaystyle g(x)=(1+x^2+x^4+...)(1+x^5+x^{10}+...)(1+x+x^2+x^3+x^4)(1+x) \displaystyle =\frac{1}{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}(1+x)=\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}\binom{n+1}{n}x^n=\sum_{n=0}^{\infty}(n+1)x^n

所以h_n=n+1，这样就通过纯代数的方法解决了一个组合问题

指数生成函数（EGF）

定义无穷数列h_0,h_1,...,h_n的指数生成函数为：

\displaystyle g(x)=h_0+h_1x+h_2\frac{x^2}{2!}+...h_n\frac{x^n}{n!}+...

注意这些单项式出现在泰勒级数中：

\displaystyle e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}=1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}+...

这也是指数生成函数被称为EGF的原因，这个式子也非常重要

另一个很有启发性的定义：

考虑这样一个奇怪的卷积\displaystyle h_n=\sum_{i=0}^{n}\binom{n}{i}f_ig_{n-i}

直接把\binom{n}{i}展开，并且把n!移到左边，得到：

\displaystyle \frac{h_n}{n!}=\sum_{i=0}^{n}\frac{f_i}{i!}\times \frac{g_{n-i}}{(n-i)!}

那么就能够发现h的EGF正是f的EGF与g的EGF的卷积

EGF的运算：

\displaystyle (\sum_{n=0}^{\infty}a_n\frac{x^n}{n!})(\sum_{n=0}^{\infty}b_n\frac{x^n}{n!})=\sum_{n=0}^{\infty}(\sum_{i=0}^{n}\binom{n}{i}a_ib_{n-i})x^n \displaystyle \frac{x}{dx}(\sum_{n=0}^{\infty}a_n\frac{x^n}{n!})=\sum_{n=0}^{\infty}a_{n+1}\frac{x^{n}}{n!}
\displaystyle \frac{x}{dx}(a_n\frac{x^n}{n!})=a_n\frac{x_{n-1}}{(n-1)!}
\displaystyle \int (\sum_{n=0}^{\infty}a_n\frac{x^n}{n!})dx=\sum_{n=1}^{\infty}a_{n-1}\frac{x^n}{n!}+C

一些例子：

1,a^2,a^3,...,a^n...$的指数生成函数为：$\displaystyle \sum_{i=0}^{\infty}a^n\frac{x^n}{n!}=\sum_{i=0}^{n}\frac{(ax)^n}{n!}=e^{ax}
  • k^n$表示有$k$种不同类型的对象且每一种对象都有无穷重数的多重集合的$n$排列数，因此这个计数数列的指数生成函数就是$e^{kx}
P(n,0),P(n,1),P(n,2),...,P(n,n)$的指数生成函数为：$\displaystyle \sum_{i=0}^{n}P(n,i)\frac{x^i}{i!}=\sum_{i=0}^{n}\frac{n!}{(n-i)!i!}x^i=(1+x)^n
  • 注意到这和\displaystyle \binom{n}{0},\binom{n}{1},...,\binom{n}{n}的普通生成函数一样

定理：设S是多重集合\{n_1\times a_1,n_2\times a_2,...,n_k\times a_k\}，设h_n是S的n排列数，那么h的指数生成函数为：

g(x)=f_{n_1}(x)f_{n_2}(x)...f_{n_k}(x) f_{n_i}(x)=1+x+\frac{x^2}{2!}+...+\frac{x^n}{n_i!}

证明：

把所有的f_{n_i}展开，得到g(x)每一项的形式：\displaystyle \frac{x^{m_1}}{m_1!}\frac{x^{m_2}}{m_2!}...\frac{x^{m_k}}{m_k!}=\frac{x^{m_1+m_2+...+m_k}}{m_1!m_2!...m_k!}

其中0\leq m_i\leq n_i\quad n=m_1+m_2+...+m_k

那么\displaystyle=\frac{x^n}{m_1!m_2!...m_k!}=\frac{n!}{m_1!m_2!...m_k!}\frac{x^n}{n!}

也就是\displaystyle h_n=\frac{n!}{m_1!m_2!...m_k!}

同时根据多重集合的排列公式可知：\displaystyle \frac{n!}{m_1!m_2!...m_k!}同时也是满足m_1+m_2+...+m_k的多重集合的n排列数。所以两者等价，定理得证

一个具体的例子：通过EGF解决计数问题

用红、白和蓝三种颜色给一个1\times n的棋盘染色，要求染成红色的方格数是偶数，确定给这个棋盘染色的方案数

设h_n表示这样的着色数，则h_n等于有三种颜色的多重集合的排列数，每一种颜色的重数是无穷，且要求红色出现的次数是偶数。为每一种颜色构造一个因子

\displaystyle g(x)=(1+\frac{x^2}{2!}+\frac{x^4}{4!}+...)(1+\frac{x}{1!}+\frac{x^2}{2!}+...)^2=\frac{1}{2}(e^x+e^{-x})e^xe^x=\frac{1}{2}(e^{3x}+e^x) \displaystyle =\frac{1}{2}(\sum_{n=0}^{\infty}3^n\frac{x^n}{n!}+\sum_{n=0}^{\infty}\frac{x^n}{n!})=\sum_{n=0}^{\infty}\frac{3^n+1}{2}\frac{x^n}{n!}

所以就得到了：\displaystyle h_n=\frac{3^n+1}{2}

部分分式

这个知识本身和计数无关，但利用它能够把许多复杂的分数形式的函数，化简为一些较好求的函数之和

具体来说：把\dfrac{f(x)}{g(x)}化简为：\displaystyle \sum_{i}\frac{a_i}{h_i(x)}的形式

其中h_i(x)的次数要小于g(x),s，所以通常先将g(x)进行因式分解

举个例子：

利用部分分式分解式子：\dfrac{1}{x^2+2x-3}

将分母分解因式得到：(x+3)(x-1)

设\dfrac{1}{x^2+2x-3}=\dfrac{A}{x+3}+\dfrac{B}{x-1}

那么有A(x-1)+B(x+3)=1

令x=-3得到：\displaystyle A=-\frac{1}{4}；令x=1得到：\displaystyle B=\frac{1}{4}

所以\displaystyle \frac{1}{x^2+2x-3}=\frac{1}{4}(\frac{1}{x-1}-\frac{1}{x+3})

生成函数和数列

只介绍较为基础的（主要是我菜）用生成函数求解数列通项公式

关于特征根、特征多项式、求解一般的齐次/非齐次递推关系，等我回了再来更吧（咕咕咕）

非常常见的例子：f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}(n>1)，求其通项公式

为数列f（即斐波那契数列）构造普通型生成函数F

\displaystyle F(x)=f_0x^0+f_1x^1+f_2x^2+f_3x^3+... \displaystyle xF(x)=\quad \quad \,\,\,f_0x^1+f_1x^2+f_2x^3+... \displaystyle x^2F(x)=\quad \quad \quad \quad \quad \,f_0x^2+f_1x^3+...

根据f_n=f_{n-1}+f_{n-2}，可以发现第一行就等于后两行之和，再加上一个x

即F(x)=xF(x)+x^2F(x)+x，然后呢？直接解出这个方程

\displaystyle F(x)=\frac{x}{1-x-x^2}

考虑利用部分分式将F(x)化简，设1-x-x^2=(x-a)(x-b)

a,b$就是方程$1-x-x^2=0$的两个根，所以$a=\dfrac{-1+\sqrt{5}}{2},b=\dfrac{-1-\sqrt{5}}{2}

所以1-x-x^2=(x-\dfrac{-1+\sqrt{5}}{2})(x-\dfrac{-1-\sqrt{5}}{2})

然后呢？想想我们要干什么？要通过生成函数去表示出f的第n项，也就是要带有x^n，但F(x)最高不就只有2次项吗，怎么凭空变出来这些项呢？

注意F是我们构造出来的生成函数，根据\displaystyle \dfrac{1}{1-ax}=\sum_{n=0}^{\infty}a^nx^n

所以要把分母化成(1-ax)(1-bx)这种形式，实际上就是上面解出来的数的倒数

所以1-x-x^2=(1-\dfrac{1+\sqrt{5}}{2}x)(1-\dfrac{1-\sqrt{5}}{2}x)

类似上面，通过特殊值法就能够解出A=\dfrac{1}{\sqrt{5}}和B=-\dfrac{1}{\sqrt{5}}

这样就能得到\displaystyle f_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)

求出\displaystyle s_n=\sum_{i=0}^{n}a_n

设\{s_n\}的OGF为S，\{a_n\}的OGF为F

\displaystyle S(x)=\sum_{n=0}^{\infty}s_nx^n=\sum_{n=0}^{\infty}(\sum_{i=0}^{n}a_i)x^n=\sum_{i=0}^{\infty}a_i\sum_{n=i}^{\infty}x^n=\sum_{i=0}^{\infty}a_i\frac{x^i}{1-x}=\frac{1}{1-x}F(x)

求出s_n=a_{n}-a_{n-1}

同样设OGF，那么有：

\displaystyle S(x)=\sum_{n=0}^{\infty}(a_n-a_{n-1})x^n=\sum_{n=0}^{\infty}a_nx^n-\sum_{n=1}^{\infty}a_{n-1}x^n=\sum_{n=0}^{\infty}a_nx^n-x\sum_{n=0}^{\infty}a_nx^n=F(x)(1-x)