生成函数

· · 个人记录

洛必达法则：

若

\lim_{n\to0}f(x)=0 \lim_{n\to0}g(x)=0

则

\lim_{n\to0}\frac{f(x)}{g(x)}=\lim_{n\to0}\frac{f'(x)}{g'(x)}

求导算子： \frac{d}{dx} \frac{df}{dx} \frac{df}{dg}

泰勒公式

有一个复杂的函数f(x)。 我们希望找到一个多项式函数g(x)来在x=x_0附近尽可能近似f(x)。 应该怎么做?

首先f(x_0)=g(x_0)

但是切线的斜率也得相同啊：

f'(x_0)=g'(x_0)

类似的切线的斜率的切线的斜率也得相同:

f''(x_0)=g''(x_0) f'''(x_0)=g'''(x_0) f''''(x_0)=g''''(x_0) \dots

当然我们不能无限这样下去 求导到n阶

f^{(n)}(x_0)=g^{(n)}(x_0)

那么很明显，g(x)是一个n次多项式（f(a)的n阶求导不是0） 那么设

g(x)=\sum_{i=0}^n{a_ix^i}

哦不，这样不太方便，是这样子

g(x)=\sum_{i=0}^n{a_i(x-x_0)^i} g(x_0)=\sum_{i=0}^n{a_i(x_0-x_0)^i}=a_0

即

a_0=f(x_0)

考虑导数

g'(x)=\sum_{i=0}^{n-1}{(i+1)a_{i+1}(x-x_0)^i} g'(x_0)=\sum_{i=0}^{n-1}{(i+1)a_{i+1}(x_0-x_0)^i=a_1}

即

a_1=f'(x_0)

二阶导数

g''(x)=\sum_{i=0}^{n-2}{(i+2)(i+1)a_{i+2}(x-x_0)^i} g''(x_0)=\sum_{i=0}^{n-2}{(i+2)(i+1)a_{i+2}(x_0-x_0)^i=2a_2}

即

a_2=\frac{1}{2}f''(x_0)

一般的，有a_i=\frac{f^{(i)}(x_0)}{i!}

即

g(x)=\sum_{i=0}^{n}{\frac{f^{(i)}(x_0)}{i!}x^i}

这是泰勒展开。

生成函数

对于一个数列

a_0,a_1,a_2,a_3,...

我们可以用一个函数来表示它。

A(x)=\sum_{i=0}^{\infty}{a_ix^i}

这就是生成函数。

举几个例子

e^x$表示数列$1,1,\frac12,\frac16,\frac1{24},\dots,\frac1{n!},\dots \sin(x)$表示数列$0,1,0,-\frac16,0,\frac1{5!},\dots \cos(x)$表示数列$1,0,-\frac12,0,\frac1{4!},0,\dots \ln(1+x)$表示数列$0,1,-\frac12,\frac13,-\frac14,\dots (1+x)^a$表示数列$1,a,\frac{a(a-1)}2,\frac{a(a-1)(a-2)}6,\frac{a(a-1)(a-2)(a-3)}{4!},\frac{a(a-1)(a-2)(a-3)(a-4)}{5!}

最初的开始

对于数列

1,1,1,1,...

其生成函数

I(x)=\sum_{i=0}^{\infty}{x^i} xI(x)=\sum_{i=1}^{\infty}{x^i} I(x)-xI(x)=1 I(x)=\frac1{1-x}

即

\frac1{1-x}=\sum_{i=1}^{\infty}{x^i}

我们可以查看它的泰勒展开式，结果是一样的。

我们通常不只是把生成函数表示成无限幂级数的形式。

一些变换

设B(x)=3I(x)

即B(x)=\frac{3}{1-x}

它可以表示数列：

3,3,3,3,3,\dots

整体乘上了

设B(x)=I(2x)

即B(x)=\frac{1}{1-2x}

它可以表示数列：

1,2,4,8,16,\dots

这是一个等比数列

设B(x)=I(x^2)

即B(x)=\frac1{1-x^2}

它可以表示数列：

1,0,1,0,1,\dots

是不是有意思多了？

设B(x)=xI(x)

即B(x)=\frac{x}{1-x}

它可以表示数列：

0,1,1,1,1,\dots

其实相当于右移了一位。

设B(x)=I^2(x)

即B(x)=\frac{1}{(1-x)^2}

可以算出

B(x)=\sum_{i=0}^{\infty}{(i+1)x^i}

它可以表示数列：

1,2,3,4,5,\dots

新鲜！

那么，设B(x)=I^n(x) 即B(x)=\frac{1}{(1-x)^n}

展开又是什么数列呢？ 考虑x^k项。

它由多个x^a形式的项拼凑而成。

设第一个式子贡献x^{a_1},第二个式子贡献x^{a_2}，...第n个式子贡献x^{a_n}。

那么x^k项的系数即为

a_1+a_2+a_3+\dots+a_n=k(a_1,a_2,\dots,a_n\in N)

的解的个数。我们可以求得个数为

C_{n+k-1}^{n-1}

因此

B(x)=\sum_{i=0}^{\infty}{C_{n+i-1}^{n-1}x^i}

即

\frac{1}{(1-x)^n}=\sum_{i=0}^{\infty}{C_{n+i-1}^{n-1}x^i}

它代表数列

1,n,C_{n+1}^{n-1},C_{n+2}^{n-1},C_{n+3}^{n-1}\dots

好了，这下我们可以用生成函数表示更加复杂的东西了

生成函数的加法

设

A(x)=\sum_{i=0}^{\infty}{a_ix^i} B(x)=\sum_{i=0}^{\infty}{b_ix^i}

则

C(x)=A(x)+B(x)=\sum_{i=0}^{\infty}{(a_i+b_i)x^i}

我们可以拼凑出一些奇怪的东西。

数列

1,4,9,16,25,\dots

由于 n^2=2C_n^2+C_n^1 且 \frac{1}{(1-x)^n}=\sum_{i=0}^{\infty}{C_{n+i-1}^{n-1}x^i}

因此设 B(x)=2xI^2(x)+I(x)=\frac{2x}{(1-x)^3}+\frac1{(1-x)^2}

即 B(x)=\frac{1+x}{(1-x)^3}

我们甚至可以用类似的方法求出所有以多项式为通项公式的数列的生成函数。

当然，它的用处不止于此。

求解线性齐次递推式

考虑数列

f_0,f_1,f_2,f_3,\dots

其中

f_i=1&i\in\{0,1\}\\ f_i=f_{i-1}+f_{i-2}&i>1 \end{cases}

设

F(x)=\sum_{i=0}^{\infty}{f_ix^i} F(x)=f_0+f_1x+\sum_{i=2}^{\infty}{f_ix^i} F(x)=f_0+f_1x+\sum_{i=2}^{\infty}{(f_{i-1}+f_{i-2})x^i} F(x)=f_0+f_1x+\sum_{i=2}^{\infty}{f_{i-1}x^i}+\sum_{i=2}^{\infty}{f_{i-2}x^i} F(x)=f_0+f_1x-f_0x+f_0x+\sum_{i=1}^{\infty}{f_{i}x^{i+1}}+\sum_{i=0}^{\infty}{f_{i}x^{i+2}} F(x)=f_0+f_1x-f_0x+x\sum_{i=0}^{\infty}{f_{i}x^i}+x^2\sum_{i=0}^{\infty}{f_{i}x^i} F(x)=1+xF(x)+x^2F(x)

可解得

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

让我们强行把1-x-x^2分解一下。

考虑方程

1-x-x^2=0

解得

x_1=-\frac{1+\sqrt5}{2}\\ x_2=-\frac{1-\sqrt5}{2} \end{cases}

也就是

(1+\frac{2}{1-\sqrt5}x)(1+\frac{2}{1+\sqrt5}x) (1-\frac{1+\sqrt5}2x)(1-\frac{1-\sqrt5}2x)

那么

F(x)=\frac1{(1-\frac{1+\sqrt5}2x)(1-\frac{1-\sqrt5}2x)}

考虑设

F_1(x)=\frac1{1-\frac{1+\sqrt5}2x} F_2(x)=\frac1{1-\frac{1-\sqrt5}2x}

解方程

F(x)=aF_1(x)+bF_2(x)

即

a+b=1\\ \frac{1-\sqrt5}2a+\frac{1+\sqrt5}2b=0 \end{cases}

解得

a=\frac{5+\sqrt5}{10}\\ b=\frac{5-\sqrt5}{10} \end{cases}

最后，展开F_1(x)和F_2(x)

F_1(x)=I(\frac{1+\sqrt5}2x)=\sum_{i=0}^{\infty}{(\frac{1+\sqrt5}2x)^i}=\sum_{i=0}^{\infty}{(\frac{1+\sqrt5}2)^ix^i} F_2(x)=I(\frac{1-\sqrt5}2x)=\sum_{i=0}^{\infty}{(\frac{1-\sqrt5}2x)^i}=\sum_{i=0}^{\infty}{(\frac{1-\sqrt5}2)^ix^i} F(x)=\frac{5+\sqrt5}{10}F_1(x)+\frac{1+\sqrt5}2F_2(x) =\frac{5+\sqrt5}{10}\sum_{i=0}^{\infty}{(\frac{1+\sqrt5}2)^ix^i}+\frac{5-\sqrt5}{10}\sum_{i=0}^{\infty}{(\frac{1-\sqrt5}2)^ix^i} =\sum_{i=0}^{\infty}{(\frac{5+\sqrt5}{10}(\frac{1+\sqrt5}2)^i+\frac{5-\sqrt5}{10}(\frac{1-\sqrt5}2)^i)x^i}

由于\frac{5+\sqrt5}{10}=\frac1{\sqrt5}\frac{1+\sqrt5}2且\frac{5-\sqrt5}{10}=\frac1{\sqrt5}\frac{1-\sqrt5}2

F(x)=\sum_{i=0}^{\infty}{\frac1{\sqrt5}((\frac{1+\sqrt5}2)^{i+1}+(\frac{1-\sqrt5}2)^{i+1})x^i}

因此

f_i=\frac1{\sqrt5}((\frac{1+\sqrt5}2)^{i+1}+(\frac{1-\sqrt5}2)^{i+1})

这就是著名的斐波那契数列通项公式。

生成函数的乘法

设

A(x)=\sum_{i=0}^{\infty}{a_ix^i} B(x)=\sum_{i=0}^{\infty}{b_ix^i}

则

C(x)=A(x)+B(x)=\sum_{i=0}^{\infty}{(\sum_{j=0}^{i}{a_jb_{i-j}})x^i}

没错，我们同样可以用它来乱搞，怎么办呢？

生成函数乱入组合问题

将x^a系数看成一个大小为a的问题的方案数，就可以用生成函数乱搞组合问题了 举个例子：

有A,B,C,D四种水果，每种水果都有无限个，现在要求每种水果拿 若干个，要求 A 恰好拿出偶数个，B 恰好拿出 5 个倍数个，C 最多拿 4 个，D 最多拿一个，如果最后恰好拿出 N 个水果，有多少种方案。 使用生成函数求出对于每一个 N 的答案。

我们可以构造生成函数。

A(x)=\sum_{i=0}^{\infty}{x^{2i}=\frac1{1-x^2}}\\ B(x)=\sum_{i=0}^{\infty}{x^{5i}=\frac1{1-x^5}}\\ C(x)=\sum_{i=0}^{4}{x^i=\frac{1-x^5}{1-x}}\\ D(x)=1+x \end{cases}

四个函数的卷积G(x)=A(x)B(x)C(x)D(x)即为答案

G(x)=A(x)B(x)C(x)D(x)=\frac1{1-x^2}\frac1{1-x^5}\frac{1-x^5}{1-x}(1+x)=\frac1{(1-x)^2} =\sum_{i=0}^{\infty}{(i+1)x^i}

因此输出N+1即可

求解非线性递推式

一个正 n 边形，顶点标号 1 ～ n，现在画 n ? 3 条不相交的对角线将 它划分为一些三角形，有多少种方案。

方案数即为Catalan数，即数列：

c_0,c_1,c_2,c_3,c_4,c_5,...

其中c_n为n+2边形的情况，特别地，c_0=1。 对于一个n边形，找到一个顶点，枚举左边的第一条边，可以把它化为2边形和(n-3)边形的情况，枚举左边的第二条边，可以把它化为3角形和(n-4)边形的情况……

我们可以以此列出递推式

c_i=1&i=1\\ c_i=\sum_{j=0}^{n-1}{c_jc_{n-j-1}}&i>1 \end{cases}

设出生成函数

C(x)=\sum_{i=0}^{\infty}{c_ix^i}

推式子

C(x)=c_0+\sum_{i=1}^{\infty}{c_ix^i}=c_0+x\sum_{i=0}^{\infty}{c_{i+1}x^i} =c_0+x\sum_{i=0}^{\infty}{(\sum_{j=0}^i{c_jc_{i-j}})x^i} 让我们看看： $$C^2(x)=C(x)C(x)=\sum_{i=0}^{\infty}{(\sum_{j=0}^i{c_jc_{i-j}})x^i}$$ 这不就巧了吗。 $$C(x)=c_0+xC^2(x)$$ 即 $$xC^2(x)-C(x)+1=0$$ 解得 $$\begin{cases} C_1(x)=\frac{1+\sqrt{1-4x}}{2x}\\ C_2(x)=\frac{1-\sqrt{1-4x}}{2x} \end{cases}$$ 然后问题来了，你选哪个呢？ 我们用这种神奇的方法排除掉一个函数。 首先显然有： $$\lim_{x\to0}{C(x)}=c_0=1$$ 另外我们可以（用洛必达法则）得到这两个式子。 $$\lim_{x\to0}{C_1(x)}=\infty$$ $$\lim_{x\to0}{C_2(x)}=1$$ 因此$C(x)=C_2(x)=\frac{1-\sqrt{1-4x}}{2x}$， 就是这么简单粗暴。 然后问题来了，这东西怎么展开呢。 设(广义组合数） $$C_n^k=\frac1{k!}\prod_{i=0}^{k-1}{(n-i)}(n\in R,k\in N)$$ $$C_{0.5}(x)=\sqrt{1-4x}=(1-4x)^{\frac12}=\sum_{i=0}^{\infty}{C_{\frac12}^i}(-4x)^i$$ $$=\sum_{i=0}^{\infty}{\frac1{i!}\prod_{j=0}^{i-1}{(\frac12-j)}}(-4x)^i=\sum_{i=0}^{\infty}{(\frac{(-4)^i}{i!}\prod_{j=0}^{i-1}{(-(j-\frac12)))x^i}}$$ $$=\sum_{i=0}^{\infty}{(\frac{(-4)^i(-1)^i}{i!}\prod_{j=0}^{i-1}{(j-\frac12))x^i}}=\sum_{i=0}^{\infty}{(\frac{4^i}{i!}\prod_{j=0}^{i-1}{(j-\frac12))x^i}}$$ $$=\sum_{i=0}^{\infty}{(\frac{2^i}{i!}\prod_{j=0}^{i-1}{(2j-1))x^i}}=-1+\sum_{i=1}^{\infty}{(\frac{2^i}{i!}\prod_{j=0}^{i-1}{(2j-1))x^i}}$$ $$=-1-\sum_{i=1}^{\infty}{(\frac{2^i}{i!}\prod_{j=1}^{i-1}{(2j-1))x^i}}$$ 那么(前方高能）$C(x)=\frac{1-C_{0.5}(x)}{2x}$： $$C(x)=\frac1{2x}(\sum_{i=1}^{\infty}{(\frac{2^i}{i!}\prod_{j=1}^{i-1}{(2j-1))x^i}})=\frac1{2}(\sum_{i=0}^{\infty}{(\frac{2^{i+1}}{(i+1)!}\prod_{j=1}^{i}{(2j-1))}x^i})$$ $$=\frac1{2}(\sum_{i=0}^{\infty}{(\frac{2^{i+1}}{(i+1)!}\frac{(2i)!}{\prod_{j=1}^{i}{2j}})x^i})=\sum_{i=0}^{\infty}{(\frac{2^i}{(i+1)i!}\frac{(2i)!}{2^ii!})x^i}$$ $$=\sum_{i=0}^{\infty}{(\frac{2^i}{(i+1)i!}\frac{(2i)!}{2^ii!})x^i}=\sum_{i=0}^{\infty}{\frac{(2i)!}{(i+1)(i!)^2}x^i}=\sum_{i=0}^{\infty}{\frac{C_{2i}^{i}}{i+1}x^i}$$ 因此: $$c_i=\frac{C_{2i}^{i}}{i+1}$$ 这就是著名的Catalan数的通项公式。 ------------ ## 指数型生成函数 之前介绍的都是正常的生成函数，求解一般的问题。 接下来介绍的是指数型生成函数。求解~~奇葩~~有标号的问题，比如排列。 对于一个数列 $$a_0,a_1,a_2,a_3,a_4,a_5,\dots$$ 它正常的生成函数为： $$A(x)=\sum_{i=0}^{\infty}{a_ix^i}$$ 它的指数型生成函数为： $$A_e(x)=\sum_{i=0}^{\infty}{\frac{a_i}{i!}x^i}$$ ------------ ### 一些乱搞 ------------ 关于全排列数的指数型生成函数。 $$A_e(x)=\sum_{i=0}^{\infty}{\frac{i!}{i!}x^i}=\sum_{i=0}^{\infty}{x^i}=\frac1{1-x}$$ 和圆排列数的指数型生成函数。特别地令$c_0=0 C_e(x)=\sum_{i=1}^{\infty}{\frac{(i-1)!}{i!}x^i}=\sum_{i=0}^{\infty}{\frac1{i}x^i}

考虑\ln(1+x)表示数列 0,1,-\frac12,\frac13,-\frac14,\dots

C_e(x)=-\ln(1-x)=\ln(\frac1{1-x})

有

P_e(x)=e^{C_e(x)}

巧合吗？巧合就不会领出来讲了。

我们考虑一个排列。

1,4,5,3,6,2

我们可以吧它当做一个边集。

1\to1,2\to4,3\to5,4\to3,5\to6,6\to2

它可以拆分成两个圆排列

1 2,4,3,5,6

即看作环

1\to1 2\to4\to3\to5\to6\to2

我们可以很容易得到，每一个排列都对应着一些圆排列。

因此我们或许可以用圆排列的生成函数来表示全排列数的生成函数。

怎么做呢？分类讨论。

一个长为n的序列被拆成1个圆排列，2个圆排列，3个圆排列，...的生成函数加起来，便是全排列数的生成函数。

被拆成一个圆排列的生成函数自然是C_{e1}(x)=C_e(x)

被拆成两个圆排列数：对于一个长度为n的序列来说