【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中)

【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中)


前言#

我们之前说了 k 阶常系数线性递推方程的解法,可以使用特征方程求解。今天我们就来学习以下有关于生成函数的内容,它是一种在组合数学和离散数学中非常有用的工具,用于处理序列和计数问题。它可以将序列转换成多项式,从而使得处理序列的操作变得更加方便。在解决非齐次线性递推关系(也称为线性递推方程)时,生成函数可以提供一种有效的方法。

生成函数#

概念#

生成函数本身不代表什么特殊意义,生成函数是无限的,对其求解是无意义的,它仅仅作为一个工具来使用。

生成函数是一个形式幂级数,通常用来表示一个数列的各项。生成函数的一般形式如下:

F(x)=a0+a1x+a2x2+a3x3+F(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots

其中,a0,a1,a2,a_0, a_1, a_2, \ldots 是数列的各项,xx 是一个变量。生成函数可以是有限的(当数列是有限项时)或无限的(当数列有无穷多项时)。同时我们也可以看到,函数中的自变量  xx  好像并没有什么意义,他的取值并不影响序列的表示,因此我们称这种函数为形式幂级数

那么这时候就有小伙伴要问了,既然生成函数本身是一个无限长的函数,那么我们要如何使用它呢?

其实很简单,我们前面说了,生成函数可以将序列转换成多项式,那么如果我们能够计算出一个数列的生成函数,我们就可以知道这个数列的通项——也就是说,当我们可以把前面一般形式中的 a0+a1x+a2x2+a3x3+a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots 表示出来,我们就完成了我们的目标,对于这个无限函数本身来说,这不是我们关心的内容。

应用#

  1. 序列的计数: 生成函数可以将序列的每一项与幂级数的相应项联系起来。通过操作生成函数,可以进行加法、乘法等操作,从而获得序列的某些性质,如总项数、平均值等。

  2. 组合计数: 生成函数在组合数学中应用广泛。例如,如果我们有若干种物品,每种物品有不同的数量,我们可以使用生成函数来计算不同方式选择这些物品的总数。

  3. 解决递推关系: 对于线性递推关系,生成函数可以转化为一个多项式方程,从而帮助我们求解递推关系中的项。形式幂级数在齐次递推关系中,生成函数的转化可以非常直接。对于非齐次递推关系,我们可以将问题转化为齐次递推关系的形式,然后使用特定的技巧来解决。

在常数性齐次递推中#

之前我们说了,在这种一般情况下,我们使用特征方程可以求出其通项,我们今天尝试使用生成函数解决此类问题。

我们要构建生成函数 H(x)H(x),使其满足递推关系。首先,将每一项 hnh_nxnx^n 相关联:

H(x)=h0+h1x+h2x2+h3x3+H(x) = h_0 + h_1 x + h_2 x^2 + h_3 x^3 + \ldots

然后考虑我们已知的递推关系:hn=5hn1+6hn2h_n = 5h_{n-1} + 6h_{n-2},可以写出下面三个函数。

H(x)=h0+h1x+h2x2+h3x3+h4x4+h5x5+5xH(x)=5h0x+5h1x2+5h2x3+5h3x4+5h4x5+6x2H(x)=6h0x2+6h1x3+6h2x4+6h3x5+\begin{aligned} H(x) &= h_0 + &h_1 x& + &h_2 x^2& + &h_3 x^3& + &h_4 x^4& + &h_5 x^5&+\ldots \\ 5xH(x) &= &5h_0x& + &5h_1 x^2& + &5h_2 x^3& + &5h_3 x^4& + &5h_4 x^5&+\ldots \\ 6x^2H(x) &= &&&6h_0x^2& + &6h_1 x^3& + &6h_2 x^4& + &6h_3 x^5&+\ldots \\ \end{aligned}

因为hn=5hn1+6hn2h_n = 5h_{n-1} + 6h_{n-2},所以我们很容易发现从第三位开始,它们相加都满足hnxn=5hn1xn+6hn2xnh_n x^n = 5h_{n-1} x^n + 6h_{n-2} x^n的样子,则可以得到生成函数如下:

H(x)=h05h0x+h1x+5xH(x)+6x2H(x)H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)

那么我们已经有了生成函数方程:

H(x)=h05h0x+h1x+5xH(x)+6x2H(x)H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)

接下来,我们可以整理这个方程,将 H(x)H(x) 的项整合在一起:

H(x)5xH(x)6x2H(x)=h05h0x+h1xH(x) - 5xH(x) - 6x^2H(x) = h_0 - 5h_0x + h_1x

H(x)H(x) 提取出来,得到:

(15x6x2)H(x)=h05h0x+h1x(1 - 5x - 6x^2)H(x) = h_0 - 5h_0x + h_1x

现在,我们可以将方程两边除以 (15x6x2)(1 - 5x - 6x^2),从而求解出最终的生成函数 H(x)H(x)

H(x)=h05h0x+h1x15x6x2H(x) = \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}

我们已经有了最终的生成函数 H(x)H(x),接下来的步骤是将其重新展开成幂级数形式,然后找到系数,以得到数列 {hn}\{h_n\} 的通解,让我们继续吧。

首先,我们要分解分母 15x6x21 - 5x - 6x^2,得到 (16x)(1+x)(1 - 6x)(1 + x)

然后,我们将分式进行部分分解,得到:

h05h0x+h1x15x6x2=A16x+B1+x\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = \frac{A}{1 - 6x} + \frac{B}{1 + x}

接下来,我们可以计算系数 AABB

A(1+x)+B(16x)=h05h0x+h1xA+Ax+B6Bx=h05h0x+h1x\begin{aligned} A(1 + x) + B(1 - 6x) &= h_0 - 5h_0x + h_1x\\ A + Ax + B - 6Bx &= h_0 - 5h_0x + h_1x\\ \end{aligned}

得到:A=h0+h17A = \frac{h_0 + h_1}{7}B=6h0h17B = \frac{6h_0 - h_1}{7}

然后将分式展开成幂级数的形式:

h05h0x+h1x15x6x2=(h0+h17)116x+(6h0h17)11+x\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = (\frac{h_0 + h_1}{7}) \cdot \frac{1}{1 - 6x} + (\frac{6h_0 - h_1}{7}) \cdot \frac{1}{1 + x}

使用几何级数的展开,几何级数的展开公式是:

11r=1+r+r2+r3+\frac{1}{1 - r} = 1 + r + r^2 + r^3 + \ldots

其中,rr 是一个实数,通常称为公比。这个级数在 r<1|r| < 1 的情况下是收敛的,即当公比的绝对值小于 1 时,级数的和会收敛到一个有限的值。

如果公比 rr 的绝对值大于等于 1,那么级数就会发散,没有有限的和。

对于这个公式,我们简单证明一下:

设 S=1+r+r2+r3+则 rS=r+r2+r3+r4+得 (1r)S=1综上所述S=11r=1+r+r2+r3+\begin{aligned} &设\ &S &= 1 + r + r^2 + r^3 + \ldots\\ &则\ &rS &= r + r^2 + r^3 + r^4 + \ldots\\ &得\ &(1-r)S&=1\\ &综上所述 &S=\frac{1}{1 - r} &= 1 + r + r^2 + r^3 + \ldots\\ \end{aligned}

在生成函数的推导中,几何级数展开经常用于将分式进行展开成幂级数形式。在这种情况下,我们通常需要确保公比 rr 的绝对值小于 1,以确保级数收敛。

还有 1+r1 + r 的情况如下:

11+r=1r+r2r3+\frac{1}{1 + r} = 1 - r + r^2 - r^3 + \ldots

那么我们把原式进行几何数级展开,我们可以得到:

(h0+h17)(1+6x+36x2+216x3+)+(6h0h17)(1x+x2x3+)(\frac{h_0 + h_1}{7}) \cdot (1 + 6x + 36x^2 + 216x^3 + \ldots) + (\frac{6h_0 - h_1}{7}) \cdot (1 - x + x^2 - x^3 + \ldots)

现在,我们将每一项展开并合并:

h0+h17+h0+h17(6x)+h0+h17(36x2)++6h0h17+6h0h17(x)+6h0h17(x2)+\frac{h_0 + h_1}{7} + \frac{h_0 + h_1}{7} \cdot (6x) + \frac{h_0 + h_1}{7} \cdot (36x^2) + \ldots + \frac{6h_0 - h_1}{7} + \frac{6h_0 - h_1}{7} \cdot (-x) + \frac{6h_0 - h_1}{7} \cdot (x^2) + \ldots

将各项整合:

h0+h17+6h0+6h17x+36h0+36h17x2++6h0h176h0h17x+6h0h17x2+\frac{h_0 + h_1}{7} + \frac{6h_0 + 6h_1}{7}x + \frac{36h_0 + 36h_1}{7}x^2 + \ldots + \frac{6h_0 - h_1}{7} - \frac{6h_0 - h_1}{7}x + \frac{6h_0 - h_1}{7}x^2 + \ldots

将各项系数与幂次结合,得到合并后的幂级数形式:

h0+h1x+(6h0+5h1)x2+(30h0+31h1)x3h_0 + h_1x + \left(6h_0 + 5h_1\right)x^2 + \left(30h_0 + 31h_1\right)x^3\ldots

那么它最后的通项公式如下:

hn=(h0+h17)6n+(6h0h17)(1)nh_n = (\frac{h_0 + h_1}{7}) \cdot 6^n + (\frac{6h_0 - h_1}{7}) \cdot (-1)^n

所以我们实际上是进行了一次展开->合并->展开的过程,刚开始我们定义了一个生成函数,但是由于都是未知项,我们无法直接求得确切值。所以我们通过合并成h05h0x+h1x15x6x2\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}的形式,把原先无穷个未知项变成了已知的h0h_0h1h_1。最后我们再重新展开,就得到了一个可用于求解的幂级数形式。

在常数性非齐次递推中#

终于上正片了,在一般情况下,递