组合数学 第四章8母函数和递推关系应用举例

递推关系与母函数法1.2 递推关系Hanoi塔问题：这是组合数学中的著名问题。

n个圆盘依其半径大小，从下而上套在柱A上，如图1.1所示。

每次只允许取一个转移到柱B或柱C上，而且不允许大盘放在小盘上方。

若要求把柱A上的n个盘转移到柱C上，请设计一种方法，并估计要移动几个盘次，现在只有A，B，C三根柱子可供使用。

设a,b,c是3个塔座。

开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

各圆盘从小到大编号为1,2,…,n,现要求将塔座a 上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

图1.1Hanoi塔是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。

这一问题有典型的意义，第一步先解决算法问题，即如何完成n个盘的搬动，进一步还要对算法作出复杂性分析，即对要作多少盘次的搬动进行估计。

算法设计：n=时，第一步先把最上面一个圆盘套在柱B上；第二步把第二个圆盘转2移到柱C上；最后再把柱B上的一个圆盘转移到柱C上，到此转移完毕。

假定1n-个盘子的转移算法已经确定。

对于一般n个圆盘的问题，先把上面的1n-个圆盘转称到柱B上，再把最后一上圆盘转移到柱C上，然后把柱B上的1n-个圆盘转移到柱C上，转移完毕。

上述的算法是递归的连用。

2n=时，第一步便利用n=时已给出了算法；3算法把上面两个圆盘移到柱B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上的两个圆盘转移到柱C上，4,5,,n= 以此类推。

图1.1形象地给出4n=的转移过程。

void hanoi (int n, int a, int b, int c) {if (n > 0) {hanoi (n-1, a, c, b); move (a,b);hanoi (n-1, c, b, a); } }算法分析：令n h 表示n 个圆盘所需要的转移盘次。

母函数的概念和使用
母函数是组合数学中的一种重要工具，用于描述序列的生成函数。

它可以将序列转化为形式简单的多项式，从而方便地进行计算和推导。

形式上，对于序列$\{a_n\}$，它的母函数可以定义为：
$A(x)=\sum_{n=0}^{\infty}a_nx^n=a_0+a_1x+a_2x^2+...$
母函数$A(x)$通常被视为$x$的函数，可以进行各种计算操作，比如加法、乘法、求导等。

母函数的使用有以下几个方面：
1. 求序列的常用操作：对于给定的序列，可以通过母函数求导、乘法、加法等操作得到新的序列。

例如，序列的微分对应于母函数的求导，序列的乘法对应于母函数的乘法，序列的加法对应于母函数的加法。

2. 求序列的递推关系：通过构造序列的母函数，可以得到序列的递推关系。

递推关系描述了序列相邻项之间的关系，是解决组合计数问题的关键。

通过求解递推关系，可以得到序列的通项公式，从而得到更深入的结论。

3. 求序列的生成函数：母函数可以将序列转化为一个形式简单的多项式。

通过对母函数进行逆变换，可以得到序列的生成函数，从而用多项式的形式来表示序列。

生成函数是分析序列性
质的一种强有力的工具，可以进行各种计算和推导。

母函数在组合计数、离散数学和概率等领域中具有广泛的应用，可以解决各种组合计数问题，如排列组合、图论、走迷宫等问题。

同时，母函数也是解决一些难题的关键，在一些具有复杂递推关系的序列中起到了重要作用。

母函数（⽣成函数）介绍母函数是组合数学中相当重要的⼀个知识点，可以⽤来解决⼀些排列组合问题，还有所有的常系数线性齐次递推问题。

如果系数不是常数，需要根据具体情况进⾏处理。

具体的内容可以看组合数学相关书籍或者，由于⼤佬总是想当然地把别⼈当成⼤佬，⼀些内容对（像我这种）蒟蒻来说不是很友好，在这⾥讲⼀下母函数的基础。

（研究母函数时，钦定|x|<1）,这样，由等⽐数列求和公式有：11−x=∑∞i=0x i=1+x+ (x)11−kx=∑∞i=0k i x i=1+kx+...+k∞x∞1.普通型母函数。

假设有⼀个数列a,那么它的母函数其实就是⼀个关于x的多项式，x n的系数为a n，对于已知通项的数列，其母函数可以直接写出来。

⽽对于未知的数列，主要分为两类：递推型和组合型。

递推型就是利⽤错位相消，举个栗⼦：a n=3a n−1+10a n−2,a0=1,a1=2移项，得a n−3a n−1−10a n−2=0，设a n的母函数为G(x)G(x)=a0+a1x+a2x2+a3x3...−3xG(x)=−3a0x+(−3)a1x2+(−3)a2x3...−10x2G(x)=−10a0x2+(−10)a1x3三⾏相加，可以发现等式右侧除了第⼀⾏的第1,2项和第⼆⾏的第1项外全消掉了。

所以我们可以得到(1−3x−10x2)G(x)=a0+a1x−3a0x=1−x，即G(x)=1−x1−3x−10x2，⽣成函数就求出来了，那如果我们还要求an的通项呢？对于这种东西，我们可以把他化成k1x−A+k2x−B这种形式，其中A和B由分母的因式分解唯⼀确定，然后k1,k2可由待定系数法解得。

然后对于kx−A,总可以化成k′∗11−Nx，就是k′∑∞i=0N i x i，找出x k的系数就是a n，如果母函数拆开成多个该类分式的话各部分相加就好。

具体计算就不算了。

PS:⼀部分⾮齐次线性递推其实也可以这样解，⽐如a n−3a n−1−10a n−2=f(n)，按照上述⽅法错项后会剩下⼀个等⽐数列和前⼏项余项。

ACM 暑期集训 组合数学（4） 递推 递归 母函数1 递推关系序列{a n }=a 0，a 1，…，a n ，…，把 a n 与某些a i (i <n )联系起来的等式叫做关于序列{a n }的递推方程。

当给定递推方程和适当的初值就唯一确定了序列。

递推关系分类： （1）按常量部分：齐次递推关系：指常量＝0，如F(n)=F(n-1)+F(n-2) 非齐次递推关系：指常量≠0，如F(n)=2*F(n-1)+1 （2）按运算关系：线性关系，如上面的两个；非线性关系，如F(n)=F(n-1)*F(n-2)。

（3）按系数：常系数递推关系，如（1）中的两个；变系数递推关系，如D(n)=(n-1)(D(n-1)+D(n-2)。

（4）按数列的多少一元递推关系，只涉及一个数列，上面的均为一元； 多元递推关系，涉及多个数列，如⎩⎨⎧+=+=----111177n n nn n n a b b b a a Fibonacci 数列为1,1,2,3,5,8,13,.....long long data[100]; data[1]=1; data[2]=1;for(int i=3;i<=50;i++) data[i]=data[i-1]+data[i-2]; while(cin>>n) cout<<data[n]<<endl;例1：直线割平面问题。

在一个无限的平面上有N 条直线，试问这些直线最多能将平面分割成多少区域？F(1) = 2; F(2) = 4; F(3) = 7; F(n)=F(n-1)+n; (n>1)int recurrence(int n) //递推 {f[1]=2;for(i=2;i<=n;i++) f[n]=f[n-1]+n; return f[n]; }int recursion(int n) 递归： {if(n==1) return 2;//递归终止条件 else return recursion(n-1)+n; }更快的方法是求出通项：F(n)=n^(n+1)/2+1例2：HDOJ2050 折线割平面问题在一个无限的平面上有N 条折线，试问这些折线最多能将平面分割成多少区域？F(n)=F(n-1)+4n-3; F(n)=2*n^2-n+1;例3：椭圆割平面问题。

母函数与求解递推关系组合数学⽤的最多的⼯具要算母函数，究竟什么是母函数呢，先看(1+a1x)(1+a2x)⋯(1+a n x)=1+(a1+a2+⋯a n)x+(a1a2+a1a3+⋯a n−1a n)x2+⋯+a1a2⋯a n x n..x1项系数：a1+a2+⋯a n;x2项系数：a1a2+a1a3+⋯a n−1a n；⋯x n项系数：a1a2⋯a n即x k项系数：a1,a2,⋯,a n取k个组合的全体之和，k=1,2,⋯,n.令a1=a2=⋯=a n=1，即得(1+x)n=1+C(n,1)x+C(n,2)x2+⋯+C(n,n)x n另⼀⽅⾯(1+x)m(1+x)n=(1+x)m+n故$$(1+x)m(1+x)n=C(m,0)+C(m,1)+⋯+C(m,m)x m×C(n,0)+C(n,1)x+⋯+C(n,n)x n=C(m+n,0)+C(m+n,1)+⋯+C(m+n,m+n)x m+n$$⽐较上⾯等式得常系数，C(m,0)C(n,k)+C(m,1)C(n,k−1)+⋯+C(m,k)C(n,0)=C(m+n,k),k=0,1,2,⋯,minm,n这样就证明了这个等式，当然也可⽤组合意义证明。

可见 (1+x)n=1+C(n,1)x+C(n,2)x2+⋯+C(n,n)x n在研究序列C(n,0),C(n,1),⋯,C(n,n)时起作⽤.为此引进母函数得概念.定义对于序列C0,C1,C2⋯构造⼀函数G(x)=C0+C1x+C2X2+⋯称G(x)为序列C0,C1,C2⋯的母函数.例如(1+x)n称为序列C(n,0),C(n,1),⋯,C(n,n)的母函数，序列长度可能是有限的，也可能是⽆限的。

若已知序列可求得母函数，反之若求得母函数，序列也随之确定，因此，序列和对应的母函数是⼀⼀对应的。

现利⽤母函数求递推关系的解，⽤汉诺塔做例⼦.H(n)=2H(n−1)+1,H(1)=1补充定义H0=0，并作如下步骤的形式化演算：x:H1=2H0+1x2:H2=2H1+1x3:H3=2H2+1+⋯G(x)=2x[H0+H1x+H2x2+⋯]+[x+x2+x3+⋯]等式两边分别为H0+H1x+H2x2+⋯=2x∞∑k=0H k x k+∞∑k=1x kx+x2+x3+⋯=x[1+x+x2+⋯]=x 1−x所以得G(x)=2xG(x)+x 1−xG(x)=x(1−x)(1−2x)序列H k的母函数已求得，后⾯是设法从G(x)求序列H k.令Processing math: 100%x(1−x)(1−2x)=A1−2x+B1−x解⽅程得A=1,B=−1所以G(x)=11−2x−11−x=(1+2x+22x2+⋯)−(1+x+x2+⋯)因此H n=2n−1,n=1,2,⋯上⾯利⽤母函数求递推关系的序列，构建序列和母函数有座桥：11−x=1+x+x2+⋯。

运用母函数解决问题母函数是组合数学中一个重要的工具，它能够帮助我们解决一些复杂的组合问题。

在本文中，我们将探讨如何运用母函数来解决一些常见的组合问题。

母函数是一个形式幂级数，它可以表示一类组合对象的生成函数。

对于一个给定的组合对象，我们可以用母函数来表示其不同的可能性。

通过对母函数进行运算，我们可以得到这个组合对象的各个性质。

首先，让我们来看一个简单的例子。

假设我们有三种不同的硬币，分别是1元、2元和5元硬币。

我们想知道用这些硬币凑出10元有多少种方式。

我们可以定义硬币的母函数为：$C(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^5+x^{10}+...)$。

这个母函数表示了每种硬币的不同数量的组合方式。

我们可以将这个母函数进行展开：$C(x)=\frac{1}{(1-x)} \cdot\frac{1}{(1-x^2)} \cdot \frac{1}{(1-x^5)}$。

这个展开式告诉我们，用这三种硬币凑出10元的组合方式总数等于展开式中$x^{10}$的系数。

我们可以通过展开式中$x^{10}$的系数来求解这个问题。

在求解中，我们可以使用迭代法、递归法或其他数学方法来简化计算过程。

最终，我们可以得到用这三种硬币凑出10元的组合方式总数。

这个例子展示了母函数在组合问题中的应用。

通过定义一个合适的母函数，并运用适当的运算方法，我们可以解决一些复杂的组合问题。

除了求解组合问题，母函数还可以用于计算组合对象的期望值、方差等。

例如，我们可以通过求解母函数的导数来计算组合对象的期望值。

这些应用使得母函数成为了一个非常强大的解决组合问题的工具。

在实际应用中，我们还可以将母函数与其他数学方法结合起来，进一步拓展其应用领域。

例如，我们可以将母函数与递推关系、生成函数等结合，以解决更加复杂的组合问题。

总结起来，母函数是一种非常有用的工具，它能够帮助我们解决各种组合问题。