2. 递推关系与母函数

joker ... 2022-4-7 大约 27 分钟

# 2. 递推关系与母函数

找出问题通解的表示式十分困难？？

所以第二章引入了母函数的概念

# 2.1 母函数的概念

什么是母函数？？母函数的作用的什么？？

组合数学的主要内容是计数，用的最多的计数工具要算母函数

母函数，是组合数学中尤其是计数方面的一个重要理论和工具，运用这种数学方法往往对程序效率与速度有很大改进

母函数方法不仅在概率论的计算中有重要地位，而且已成为组合数学中一种重要方法。

# 2.1.1 定义

对于序列 $C_0,C_1,C_2,\cdots$ 构造一函数

G(x)=C_0+C_1x+C_2x^2+\cdots

称 $G(x)$ 为序列 $C_0,C_1,C_2,\cdots$ 的母函数

例子

(1+x)^n=C(n,0)+C(n,1)x+\cdots+C(n,n)x^n

$(1+x)^n$ 为序列 $C(n,0),C(n,1),\cdots,C(n,n)$ 的母函数，序列长度可能是有限的，也可能是无限的

# 2.1.2 提出的过程

伯努利提出了-->投掷m粒骰子，加起来点数总和等于n的可能方式的数目?

当时是怎么解决的呢？？？

先来个简单的，两个骰子投掷出n点，有多少种可能？？

投出一点是骰子为 $x$

投出两点的骰子为 $x^2$

投出六点的骰子为 $x^6$

两者相乘，其中系数就是投掷出的可能的办法

$x^6$ 的系数为5，表示两个骰子投掷出6点的方法可能方法有5种

那么投掷m粒骰子，加起来点数总和等于n的可能方式的数目?

解决方案为:

$G(x)=(x+x^2+x^3+x^4+x^5+x^6)^m$ 展开式中 $x^n$ 的系数

问题一

计算 $p=23^{\frac{1}{3}}41^{\frac{1}{8}}$ 很困难

要做对数映射

$p=23^{\frac{1}{3}}41^{\frac{1}{8}}\to \lg p=\frac{1}{3}\lg(23)+\frac{1}{8}\lg(41)$

和母函数一样。都是做了映射。把计算骰子的个数的问题，变成多项式系数的问题

函数 $f(x)=\sum_{n=0}^\infty a_nx^n$ .其中重要的就是 $x^n$

母函数 $G(x)=\sum_{n=0}^\infty a_nx^n$ ,其中重要的是 $a_n$

# 2.1.3 能做什么

$\frac{1}{1-2x}$ 如果用 $x^k$ 的泰勒展开得出前面的系数为 $2^k$

$\frac{2-3x}{(1-x)(1-2x)}=\frac{1}{1-x}+\frac{1}{1-2x}\\ =\sum_{k=0}^\infty x^k+\sum_{k=0}^\infty2^kx^k\\ =\sum_{k=0}^\infty(1+2^k)x^k$

我们可以说

$\frac{2-3x}{(1-x)(1-2x)}$ 是序列 $f(x)=2^k+1$ 的母函数

# 2.2 母函数的性质

假定序列 $\{a_k\}$ 的母函数为 $A(x)=a_0+a_1x+a_2x+\cdots$

序列 $\{b_k\}$ 的母函数为 $B(x)=b_0+b_1x+b_2x+\cdots$

# 2.3 整数的拆分

例一

我们可以直接使用母函数来做出解释

G(x)=(1+x)(1+x^2)(1+x^3)(1+x^4) \\ =1+x+x^2=2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}

例如右端有 $2x^5$ 项，即称出5克的方案有2种

例二

整数n拆分成 $1,2,3,\cdots,m$ 的和，允许重复，求其母函数

(1-x)^{-1}=(1+x+x^2+\cdots) \\ G_1(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots) \\ =\frac{1}{1-x}\frac{1}{1-x^2}\cdots \frac{1}{1-x^m} \\ =\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}

其中 $(1+x+x^2+x^3+\cdots)$ ，表示，允许重复，1，可以使用1次， $x^2$ 表示1使用了2次, $x^3$ 表示1使用了3次.

$(1+x^m+x^{2m})$ ，其中 $x^m$ 表示m使用了1次， $x^{2m}$ 表示m使用了2次

若将正整数n分解为 $1,2,3,\cdots$ 之和，允许重复，其方案数 $\{a_n\}$ 序列的母函数为

G(x)=\prod_{i=1}^\infty(1-x^i)^{-1} \\ =\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}\cdots

# 定理

正整数n拆分成 $1,2,3,\cdots$ 不允许重复分拆分数 $p(n)$ ，和正整数n拆分成 $1,3,5,\cdots$ 奇数和，但允许重复的拆分数 $q(n)$ 相等，即 $p(n)=q(n)$

例子

$p(3)=3$
n拆分成重复数不超过2的数之和的拆分数，等于拆分成不被3除尽的数之和的拆分数
整数n拆分成最多不超过m个数的和拆分数和n拆分成最大不超过m的拆分数相等

# 2.4 Ferrers图像

# 2.4.1 定义

Ferrers图像也可母函数一样是研究拆分的一种工具，

假定我们将n拆分成 $n=n_1+n_2+\cdots+n_k$ ,其中 $n_1\ge n_2\ge n_3\ge\cdots\ge n_{k-1}\ge n_k$

将n个点排列成从上到下非增的行，第一行 $n_1$ 的点，第2行 $n_2$ 个点，这样的图像称为Ferrers图像

# 2.4.2 性质

每一层至少有一个点
Ferrers图像的行和列互换，即以对角线为轴旋转180度。使第一行换成第一列，第2行换成第2列，第k行换成第k列。结果仍然是Ferrers图像。后一个Ferrers图像称为前一个Ferrers图像的共轭图像
整数n拆分成互不相同的若干奇数的和的拆分数

和n拆分成自共轭的Ferrers图像的拆分数相等。

自共轭图像

图像翻转过后依旧是图像本身

# 2.5 递推关系

# 2.5.1 汉诺塔问题

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

解析

假设挪动n个盘子的复杂度为 $h(n)$

我们可以推断出递推关系 $h(n)=2h(n-1)+1,h(1)=1$

例子

（1）n == 1

　　　　　　第1次 1号盘 A---->C sum = 1 次

(2) n == 2

　　　　　　第1次 1号盘 A---->B

第2次 2号盘 A---->C

　　　　　　第3次 1号盘 B---->C sum = 3 次

（3）n == 3

第1次 1号盘 A---->C

第2次 2号盘 A---->B

第3次 1号盘 C---->B

第4次 3号盘 A---->C

第5次 1号盘 B---->A

第6次 2号盘 B---->C

第7次 1号盘 A---->C sum = 7 次

代码如下：

package demo;
/**
 * 目的：实现汉诺塔问题求解
 */
import java.util.Scanner;

public class TowersOfHanoi {
    static int m =0;//标记移动次数
    //实现移动的函数
    public static void move(int disks,char N,char M)
    {
        System.out.println("第" + (++m) +" 次移动 : " +" 把 "+ disks+" 号圆盘从 " + N +" ->移到->  " + M);
    }
    //递归实现汉诺塔的函数
    public static void hanoi(int n,char A,char B,char C)
    {
        if(n == 1)//圆盘只有一个时，只需将其从A塔移到C塔
            TowersOfHanoi.move(1, A, C);//将编b号为1的圆盘从A移到C
        else
        {//否则
            hanoi(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
            TowersOfHanoi.move(n, A, C);//把A塔上编号为n的圆盘移到C上
            hanoi(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
        }
    }
    public static void main(String[] args) {
        Scanner imput = new Scanner(System.in);
        char A = 'A';
        char B = 'B';
        char C = 'C';
        System.out.println("******************************************************************************************");
        System.out.println("这是汉诺塔问题（把A塔上编号从小号到大号的圆盘从A塔通过B辅助塔移动到C塔上去");
        System.out.println("******************************************************************************************");
        System.out.print("请输入圆盘的个数：");
        int disks = imput.nextInt();
        TowersOfHanoi.hanoi(disks, A, B, C);
        System.out.println(">>移动了" + m + "次，把A上的圆盘都移动到了C上");
        imput.close();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

如何和母函数联系起来呢？？？？？

H(x)=h(1)x+h(2)x^2+h(3)x^3+\cdots \\ H(x)-2xH(x)=h(1)x+[h(2)-2h(1)]x^2+[h(3)-2h(2)]x^3+\cdots \\ (1-2x)H(x)=x+x^2+x^3+\cdots=\frac{x}{1-x} \\ H(x)=\frac{x}{(1-2x)(1-x)}

如何从母函数中得到序列呢？？

H(x)=\frac{x}{(1-2x)(1-x)}=\frac{1}{1-2x}-\frac{1}{1-x} \\ =(1+2x+2^2x^2+2^3x^3+\cdots)-(1+x+x^2+\cdots) \\ =(2-1)x+(2^2-1)x^2+(2^3-1)x^3+\cdots \\ =\sum_{k=1}^\infty(2^k-1)x^k \\ h(k)=2^k-1

# 2.5.2 斐波那契数

# 1) 故事起源

不死神兔的繁衍生息——神奇的斐波那契数列

故事得从西元1202年说起，话说有一位意大利青年，名叫斐波那契。在他的一部著作中提出了一个有趣的问题：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子?

# 2) 斐波那契定义

递推表达式 $F_n=F_{n-1}+F_{n-2}$

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，

指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……

在数学上，斐波那契数列以如下被以递推的方法定义： $F(0)=0，F(1)=1, F(n)=F(n -1)+F(n - 2)(n\ge 2，n\in N)$ 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

# 3) 斐波那契性质

斐波那契恒等式

$F_0=1,F_1=1,F_n=F_{n-1}+F_{n-2}$

$F_1^2+F_2^2+\cdots+F_n^2=F_nF_{n-1}$

斐波那契数列的整除性与素数生成性

每3个数有且只有一个被2整除，
每4个数有且只有一个被3整除,
每5个数有且只有一个被5整除，
每6个数有且只有一个被8整除,
每7个数有且只有一个被13整除，
每8个数有且只有一个被21整除,
每9个数有且只有一个被34整除，
.......

斐波那契数列与杨辉三角的关系

从图上我们可以看到将杨辉三角中的斜向的一列数求和，得到一组新的数，而这一组新的数正好是斐波那契数列。至于其中是否有更深层的本质联系，笔者还未研究，这是一个值得讨论的问题。

1）花瓣数中的斐波那契数

大多数植物的花，其花瓣数都恰是斐波那契数。例如，兰花、茉利花、百合花有3个花瓣，毛茛属的植物有5个花瓣，翠雀属植物有8个花瓣，万寿菊属植物有13个花瓣，紫菀属植物有21个花瓣，雏菊属植物有34、55或89个花瓣。

2)广泛存在的斐波那契螺旋线

3）树杈的数目

4）向日葵花盘内葵花子排列的螺线数和黄金分割角

向日葵花盘内，种子是按对数螺线排列的，有顺时针转和逆时针转的两组对数螺线。两组螺线的条数往往成相继的两个斐波那契数[7]，一般是34和55，大向日葵是89和144，还曾发现过一个更大的向日葵有144和233条螺线，它们都是相继的两个斐波那契数。研究证明[8]，为了使花盘中的葵花籽数量达到最多，大自然为向日葵选择了最佳的黄金数字。花盘中央的螺旋角度恰好是137.5度，十分精确，只有0.1度的变化。

总结

斐波那契数列的神奇之处，在其它方面还有很多的例子和应用。比如，在股市分析，生物进化研究，力学结构稳定性分析等广泛的领域都有重要应用，对它的研究以使其为我们更好的未来服务有着重要意义。

# 4) 斐波那契相关求解

母函数求解斐波那契

设G(x)=F_1x+F_2(x)+\cdots \\ G(x)-x^2-x=x(G(x)-x)+x^2G(x) \\ G(x)=\frac{x}{1-x-x^2} \\ G(x)=\frac{A}{1-\frac{1-\sqrt{5}}{2}x}+\frac{B}{1-\frac{1+\sqrt{5}}{2}x} \\ A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}} \\ G(x)=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n) \\ \frac{F_n}{F_{n-1}}=\frac{1+\sqrt{5}}{2}\sim1.618

# 5) 斐波那契优选法

参考资料

https://zhuanlan.zhihu.com/p/31831305

参考资料

https://blog.csdn.net/weixin_41788456/article/details/105221967

在生产、生活和科学试验中，有时人们为了达到最佳、高产、低耗等目的，需要对相关因素的最佳组合进行筛选，这就是优选问题。平常到蒸馒头放多少碱，高大到航空航天的合金材料组合，总之优选问题是大量存在。

华罗庚（1910.11.12—1985.6.12），江苏省常州市金坛市人，世界著名数学家，中国科学院院士，美国国家科学院外籍院士。20世纪60年代华老亲自组织推广优选法，使优选法在国内得到广泛应用，并取得了可喜成果。

单峰函数

从名字就可以知道，这是一个函数图像先上升然后再下降或者是先下降然后再上升的形状。

可以看到在单峰函数中有一个最低点或最高点，那就是我们要寻找的最优解。

这里在区间[a,b]上表示目标和因素之间对应关系的函数叫目标函数。很多实际问题中，我们可能只知道这是一个单峰函数，但对函数关系一无所知，这就需要我们不断去试验来找到最优点。在区间[a,b]上任意安排两次不同的试验点m,n，效果较好的点称为好点，效果较差的称为差点（如下图a处为差点，b处为好点）。

优选法之黄金分割法

对于这样的单峰函数，我们希望在试验中最快的找到最优点，当然不能一个个的去试验，由上图可看出最优点一定不再端点c到差点a之间，所以这部分可以舍掉不再做试验，也就是说端点值和差点值之间的区间都可以弃之不管。

因为我们对目标函数的关系不明，这使得选取差点，好点有时是需要运气的，但我们可以用黄金分割法带来好运。

还记得黄金分割点吗？不记得也无所谓，大概就是一个线段的0.618处，比如上图（这么粗狂的风格很有数学家的韵味），线段ab的0.618处我们选取 $x_2$ 点，对称的选取 $x_1$ 点，这样不管左看还是右看这两个点都是黄金分割点。这样我们第一次试验就可以选取这两个点试验，然后舍去差点和端点值的部分，然后再在剩下的区间上选取两个黄金分割点，依次重复刚才的试验，直到达到我们所要求的精度为止。一般这样重复8次试验精度就可以达到0.05以上，11次试验就可以保证精度0.01。

斐波那契迭代法

又可以称为斐波那契查找

有的时候我们的试验不能用乘以0.618来取的那么精确，比如在配置某种液体时，需要加入某个材料，经验表明大于130ml时肯定不好，我们的量杯只能称量到10ml的精度，这时该怎么办？

这时我们可以用斐波那契数列（兔子数列）1,1,2,3,5,8,13,21,34，…（也就是每一个数都等于其前面两个数之和），这个数列有个很有趣的地方，如果我们计算数列中的每一个数与后面的数的比，这个比值会越来越趋于0.618。那我们回到刚才的问题，试验范围在0~130之间，每一份是10ml，相当于分成13个小格，这样就找数列里那个13，前面的两个数是5和8，则先试验加入50ml和80ml的情况，然后依次类推。

迭代公式

\begin{cases} \lambda_k=a_k+\frac{F_{n-k-1}}{F_{n-k+1}}(b_k-a_k),k=1,2,\cdots,n-1 \\ \mu_k=a_k+\frac{F_{n-k}}{F_{n-k+1}}(b_k-a_k),k=1,2,\cdots,n-1 \end{cases}

算法步骤

step1. 给定初始搜索区间 $[a_1,b_1]$ 和允许误差 $\varepsilon$ ,辨别系数 $\delta >0$ ，求解迭代次数n，使 $F_n\ge \frac{b_1-a_1}{\varepsilon}$

step2. 计算初始值

$\begin{cases}\lambda_1=a_1+\frac{F_{n-2}}{F_n}(b_1-a_1)\\ \mu_1=a_1+\frac{F_{n-1}}{F_n}(b_1-a_1)\\ f_\lambda=f(\lambda_1)\\ f_\mu=f(\mu_1)\end{cases}$

step3. 开始循环 $k=k+1$ ，转step4，若 $k>=n-2$ 则退出循环，转step7.

step4 判断 $f_\lambda<f_\mu$ ,是转step5,否转step6；

step5.令

a_{k+1}=a_k,b_{k+1}=\mu_k,\mu_{k+1}=\lambda_k,f_\mu=f_\lambda \\ \lambda_{k+1}=a_{k+1}+\frac{F_{n-k-2}}{F_{n-k}}(b_{k+1}-a_{k+1}) \\ f_\lambda=f(\lambda_{k+1})

step6.令

a_{k+1}=\lambda_k,b_{k+1}=b_k,\lambda_{k+1}=\mu_k,f_\lambda=f_\mu \\ \mu_{k+1}=a_{k+1}+\frac{F_{n-k-1}}{F_{n-k}}(b_{k+1}-a_{k+1}) \\ f_\mu=f(\mu_{k+1})

step7.令

\lambda_n=\lambda_{n-1},\mu_n=\lambda_{n-1}+\delta

判断 $f_{\lambda_n}<f_{\mu_n}$ 是，极小点所在的区间为 $[a_{n-1},\mu_n]$ ,否，极小点所在的区间为 $\lambda_n,b_{n-1}$ 极值点为： $f_{min}=\frac{(f_{a_n}+f_{b_n})}{2}$

例子

求解函数 $f(x)=x^2-x+2$ 在区间 $[-1,3]$ 上的极小点，要求求解的区间不大于原始区间长度的0.0008倍。

代码如下

#include <iostream>
#include <vector>
#include <iomanip> 
using namespace std;
double fx(double x)
{
	double fx;
	fx = pow(x, 2) - x + 2;
	return fx;
}
int main()
{
	double epsilon = 0.08, f_min;
	vector<double>fn(2);
	fn[0] = 1; fn[1] = 1;
	int i;
	double a_fib = -1.0, b_fib = 3.0, f_lambda = 0, f_mu = 0;
	for (i = 2; fn[i - 1] < 1.0 / epsilon; i++)
	{
		fn.push_back(fn[i - 2] + fn[i - 1]);
	}
	int n_fib = i - 1;
	cout <<"n取值：    "<< n_fib <<endl << endl;
	double lambda = a_fib + (fn[n_fib - 2] / fn[n_fib])*(b_fib - a_fib), mu = a_fib + (fn[n_fib -1] / fn[n_fib])*(b_fib - a_fib);
	f_lambda = fx(lambda);
	f_mu = fx(mu);
	cout << "区间迭代：  " <<  endl;
	for (int i = 0; i < n_fib-2; i++)
	{
		if ( f_lambda<f_mu)
		{
			a_fib = a_fib, b_fib = mu, mu = lambda, f_mu = f_lambda;
			lambda = a_fib + (fn[n_fib - i - 3] / fn[n_fib-1 - i])*(b_fib - a_fib);
			f_lambda = fx(lambda);
		}
		else
		{
			a_fib = lambda, b_fib = b_fib, lambda = mu, f_lambda = f_mu;
			mu = a_fib + (fn[n_fib - i - 2] / fn[n_fib -1-i])*(b_fib - a_fib);
			f_mu = fx(mu);
		}
		cout << fixed << setw(12) << setprecision(5) << a_fib << fixed << setw(12) << setprecision(5) << lambda << fixed << setw(12) << setprecision(5) << mu << fixed << setw(12) << setprecision(5) << b_fib << endl;
	}
	mu = lambda + 0.001;
	f_mu = fx(mu);
	if (f_lambda < f_mu)
	{
		a_fib = a_fib, b_fib = mu,f_min=0.5*(fx(a_fib)+fx(b_fib));
	}
	else 
	{
		a_fib = lambda, b_fib = b_fib, f_min = 0.5*(fx(a_fib) + fx(b_fib));
 
	}
	cout << endl << "极小值区间：" << fixed << setw(9) << setprecision(5) << a_fib << fixed << setw(12) << setprecision(5) << b_fib << endl;
	cout << "极小值：  " << fixed << setw(12) << setprecision(5) << f_min << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# 2.5.3 例三

求n为十进制中出现偶数个5的数的个数？？

令 $a_n$ 为n位十进制中出现偶数个5的数的个数， $b_n$ 为n位十进制中出现奇数个5的数的个数

$a_n=9a_{n-1}+b_{n-1}$

$b_n=9b_{n-1}+a_{n-1}$

$a_1=8,b_1=1$

解法如下图

$a_k=\frac{7}{2}8^{k-1}+\frac{9}{2}10^{k-1}$

# 2.5.5 小结

从 $G(x)$ 得到序列 $\{a_n\}$ 。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。

# 2.6 线性常系数齐次递推关系

# 2.6.1 概念

# 1) 递推关系

a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=0 \\ a_0=d_0,a_1=d_1,\cdots,a_{k-1}=d_{k-1}

若 $c_1,c_2,\cdots,c_k,d_0,d_1,\cdots,d_{k-1}$ ,都是常数，则称为 $k$ 阶的线性常系数齐次递推关系

例子

$F_n=F_{n-1}+F_{n-2}$ 便是二阶线性常系数齐次递推关系

$a_n=2a_{n-1}+1$ 是一阶线性常系数递推关系，但不是齐次的

# 2) 特征多项式

$a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=0$ 线性常系数齐次递推关系可以推出 $C(x)=x^k+c_1x^{k-1}+\cdots+c_{k-1}x+c_k$

$C(x)$ 为常系数齐次递推关系的特征多项式

当 $C(x)=0$ 为特征方程。

设由递推关系确定的的母函数 $G(x)$

$G(x)=a_0+a_1x+a_2x^2+\cdots$

# 2.6.2 根据母函数求解递推关系

x^k:a_k+c_1a_{k-1}+c_2a_{k-2}+\cdots+c_{k-1}a_1+c_ka_0=0 \\ x^{k+1}:a_{k+1}+c_1a_{k}+c_2a_{k-1}+\cdots+c_{k-1}a_2+c_ka_1=0 \\ \vdots \\ \Rightarrow (1+c_1x+c_2x^2+\cdots+c_kx^k)G(x)=\sum_{h=1}^{k-1}[c_hx^h(\sum_{j=0}^{k-1-h}a_jx^j)] \\ 令P(x)=\sum_{h=1}^{k-1}[c_hx^h(\sum_{j=0}^{k-1-h}a_jx^j)] \\ \Rightarrow G(x)=\frac{P(x)}{(1-a_1x)(1-a_2x)\cdots(1-a_kx)}

通用的 $C(x)$ 然后我们分情况讨论

情况一、假设特征多项式 $C(x)$ 无重根,有k个不同的实数解
$C(x)=(x-a_1)(x-a_2)\cdots(x-a_k) \\ G(x)=\frac{l_1}{1-\alpha_1x}+\frac{l_2}{1-\alpha_2x}+\cdots+\frac{l_k}{1-\alpha_kx} \\ =\sum_{i=1}^k\frac{l_i}{1-\alpha_ix},其中 a_n=\sum_{i=1}^kl_i\alpha_i^n$
例子--> 斐波那契数列
特征多项式 $C(x)$ 有重根。递推关系的解对应的项为 $(A_0+A_1n+\cdots+A_{k-1}n^k)\beta^n$

总结如下

$a_n+ba_{n-1}+ca_{n-2}=0,c\ne 0$

有两不同根， $r_{1,2}=\frac{-b\pm \sqrt{b^2-4ac}}{2}$ ,通解为 $a_n=Ar_1^n+Br_2^n$
有2同根 $r=r_1=r_2=-\frac{b}{2}$ ,通解为 $a_n=(A+Bn)r^n$
有一对共轭复根 $a_n=A\rho^n cosn\theta+B\rho^nsinn\theta$

例子

求解 $S_n=\sum_{k=0}^nk^2$

S_n-S_{n-1}=n^2,S_{n-1}-S_{n-2}=(n-1)^2 \\ S_n-2S_{n-1}+S_{n-2}=2n-1 \\ S_{n-1}-2S_{n-2}+S_{n-3}=2(n-1)-1 \\ \Rightarrow S_{n-1}-3S_{n-2}+3S_{n-3}-S_{n-4}=2 \\ \Rightarrow S_n-4S_{n-1}+6S_{n-2}-4S_{n-3}+S_{n-4}=0 \\ S_0=0,S_1=1,S_2=5,S_3=14 \\ \Rightarrow r^4-4r^3+6r^2-4r+1=(r-1)^4=0 \\ \Rightarrow S_n=(A+Bn+Cn^2+Dn^3)(1)^n \\

# 2.7 指数型母函数

原来的母函数主要解决的问题是组合

指数型母函数主要解决的问题是排列

# 2.7.1 概念

前期准备

设 $n$ 个元素 $a_1,a_2,\cdots a_n$ 互不相同，得到的全排列 $n!$ 。如果 $a_1$ 重复了 $n_1$ 次。则得到的真正的排列数为 $\frac{n!}{n_1!}$ 。

问题

8个元素中 $a_1$ 被重复3次， $a_2$ 被重复2次， $a_3$ 重复了3次。从中取 $r$ 个 $r\le 8$ 组，设 $C_r$ 母函数

$G(x)=(1+x+x^2+x^3)(1+x+x^2)(1+x+x^2+x^3)$

这样子算的话，肯定会有重复的出现。

$G_e(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x}{1!}+\frac{x^2}{2!})(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})$

定义

对于序列 $a_0,a_1,a_2,\cdots$ ,定义

$G_e(x)=a_0+\frac{a_1}{1!}x^2+\frac{a_2}{2!}x^3+\cdots$

为序列 $\{a_j\}$ 的指数型母函数

例子

对于序列 $\{1,1,\cdots,1,\cdots\}$

$G_e(x)=a_0+\frac{1}{1!}x^2+\frac{1}{2!}x^3+\cdots=\sum_{j=0}^\infty\frac{x^j}{j!}=e^x$

对于序列 $\{0!,1!,2!,3!,\cdots\}$

$G_e(x)=a_0+\frac{1!}{1!}x^2+\frac{2!}{2!}x^3+\cdots=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$

# 2.7.2 应用

处理多重排列问题

使用1,2,3,4填充这5个框。不过有下列条件限制

1出现不超过两次，不能不出现
2出现不超过一次
3初心可达3次，可以不出现
4出现为偶数

解: $G_e(x)=(\frac{x}{1!}+\frac{x^2}{2!})(1+x)(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x^2}{2!}+\frac{x^4}{4!})$

例二

求1,3,5,7,9五个数字组成的n位数的个数，要求其中3,7出现的次数为偶数，其他1,5,9出现次数不加限制

G_e(x)=(1+\frac{x^2}{2!}+\frac{x^4}{4!})^2(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)^3 \\ (1+\frac{x^2}{2!}+\frac{x^4}{4!})=\frac{1}{2}(e^x+e^{-x}) \\ G_e(x)=\frac{1}{4}(e^x+e^{-x})^2e^{3x} \\ =\frac{1}{4}(\sum_{n=0}^\infty\frac{5^n}{n!}x^n+2\sum_{n=0}^\infty\frac{3^n}{n!}x^n+\sum_{n=0}^\infty\frac{x^n}{n!}) \\ =\frac{1}{4}\sum_{n=0}^\infty(5^n+2\cdot 3^n+1)\frac{x^n}{n!}

# 2.7.3 错排问题

最早由尼古拉伯努利和欧拉研究，因此历史上也称为伯努利-欧拉装错信封问题。

问题描述

n个有序的元素应有 $n!$ 个不同的排列，若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排，有的叫重排

递推公式

$D_n=(n-1)(D_{n-1}+D_{n-2})，D_1=0,D_2=1,D_0=1$

# 2.8 非线性递推关系

之前的问题都是线性常系数齐次递推问题

现在是非齐次递推关系

# 2.8.1 Stirling数

多重集(1,1,2,2,...,k,k)的排列
要求两个重复数字之间的数字都要大于该数

# 第一类Stirling数

n个人跳集体舞，分成m个圆环的方法数目

$s(n,0)=0,s(1,1)=1$

递推关系

$s(n+1,m)=s(n,m-1)+ns(n,m)$

# 第二类Stirling数

# 2.8.2 卡特兰数

参考资料

https://blog.csdn.net/qq_30115697/article/details/88906534

参考资料2

https://zhuanlan.zhihu.com/p/97619085

# 1) 卡特兰数概念

卡特兰数（英语：Catalan number），又称卡塔兰数、明安图数，是组合数学中一种常出现于各种计数问题中的数列。

其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,

卡特兰数 $C_n$ 满足以下递推关系

$C_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0$
$(n-3)C_n=\frac{n}{2}(C_3C_{n-1}+C_4C_{n-2}+C_5C_{n-3}+\cdots+C_{n-2}C_4+C_{n-1}C_3)$

# 2) 直接表达式

$C_n=\frac{1}{n+1}C_{2n}^n$

# 3) 卡特兰数经典应用

# 进出栈序列

这是一道 最经典 的入门级卡特兰数题目，如果能把这题看懂，相信后面的题目也能迎刃而解。

题目描述

n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列。

思路

我们将进栈表示为 +1，出栈表示为 -1，则 1 3 2 的出栈序列可以表示为：+1 -1 +1 +1 -1 -1。

根据栈本身的特点，每次出栈的时候，必定之前有元素入栈，即对于每个 -1 前面都有一个 +1 相对应。因此，出栈序列的 所有前缀和 必然大于等于 0，并且 +1 的数量等于 -1 的数量。

接下来让我们观察一下 n = 3 的一种出栈序列：+1 -1 -1 +1 -1 +1。序列前三项和小于 0，显然这是个非法的序列。

如果将 第一个 前缀和小于 0 的前缀，即前三项元素都进行取反，就会得到：-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。

因为这个小于 0 的前缀和必然是 -1，且 -1 比 +1 多一个，取反后，-1 比 +1 少一个，则 +1 变为 n + 1 个，且 -1 变为 n - 1 个。进一步推广，对于 n 元素的每种非法出栈序列，都会对应一个含有 n + 1 个 +1 以及 n - 1个 -1 的序列。

如何证明这两种序列是一一对应的？

假设非法序列为 A，对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀"，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到"第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。

每个 B 都有 $n + 1$ 个 +1 以及 n - 1 个 -1，因此 B 的数量为 $C_{2n}^{n+1}$ ,相当于在长度为 2n 的序列中找到 $n + 1$ 个位置存放 +1。相应的，非法序列的数量也就等于 $C_{2n}^{n+1}$

出栈序列的总数量共有 $C_{2n}^n$ ，因此，合法的出栈序列的数量为 $C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^n}{n+1}$ 。

此时我们就得到了卡特兰数的通项 $\frac{C_{2n}^n}{n+1}$ ，至于具体如何计算结果将会在后面进行介绍。

# 括号序列

题目描述

n 对括号，则有多少种 “括号匹配” 的括号序列

思路

左括号看成 +1，右括号看成 -1，那么就和上题的进出栈一样，共有 $\frac{C_{2n}^n}{n+1}$

# 二叉树

题目描述

$n + 1$ 个叶子节点能够构成多少种形状不同的（国际）满二叉树

（国际）满二叉树定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

思路

使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。

由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，左右扩展将会形成匹配，即变成进出栈的题型。n + 1个叶子结点会有 2n 次扩展，构成 $\frac{C_{2n}^n}{n+1}$ 种形状不同的满二叉树。

# 电影购票

题目描述

电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。

则有多少种排队方式，可以让每个人都买到电影票。

思路

持有 50 coin的人每次购票时不需要找零，并且可以帮助后面持有 100 coin 的人找零；而对于持有 100 coin 的人每次购票时需要找零，但 100 coin 对后面的找零没有任何作用。

因此，相当于每个持有 100 coin 的人都需要和一个持有 50 coin 的人进行匹配。我们将持有 50 coin 的标记为 +1，持有 100 coin 的标记为 -1，此时又回到了进出栈问题。

不同的是，m 并一定等于 n，且排队序列是一种排列，需要考虑先后顺序，例如各自持有 50 coin 的甲和乙的前后关系会造成两种不同的排队序列。所以，将会有 $(C_{m+n}^m-C_{m+n}^{m+1})\times m!\times n!$ 。

第二项为什么是 $C_{m+n}^{m+1}$ 其实很简单，我们每次把第一个前缀小于0 的前缀取反后，会造成 +1 多了一个而 -1 少了一个。这里 +1 有 m 个，-1 有 n 个，取反后 +1 变成m + 1个，-1 变成n - 1个，总和不变。

# 4) 解题

洛谷

https://www.luogu.com.cn/problem/P1641

1. 排列与组合 3. 容斥原理与鸽巢原理

2. 递推关系与母函数

# 2. 递推关系与母函数

# 2.1 母函数的概念

# 2.1.1 定义

# 2.1.2 提出的过程

# 2.1.3 能做什么

# 2.2 母函数的性质

# 2.3 整数的拆分

# 定理

# 2.4 Ferrers图像

# 2.4.1 定义

# 2.4.2 性质

# 2.5 递推关系

# 2.5.1 汉诺塔问题

# 2.5.2 斐波那契数

# 1) 故事起源

# 2) 斐波那契定义

# 3) 斐波那契性质

# 4) 斐波那契相关求解

# 5) 斐波那契优选法

# 2.5.3 例三

# 2.5.5 小结

# 2.6 线性常系数齐次递推关系

# 2.6.1 概念

# 1) 递推关系

# 2) 特征多项式

# 2.6.2 根据母函数求解递推关系

# 2.7 指数型母函数

# 2.7.1 概念

# 2.7.2 应用

# 2.7.3 错排问题

# 2.8 非线性递推关系

# 2.8.1 Stirling数

# 第一类Stirling数

# 第二类Stirling数

# 2.8.2 卡特兰数

# 1) 卡特兰数概念

# 2) 直接表达式

# 3) 卡特兰数经典应用

# 进出栈序列

# 括号序列

# 二叉树

# 电影购票

# 4) 解题

详情