降维打击面试题系列：生成函数（三）常见数列与生成函数

通过斐波那契数列，我们掌握了一些基本的生成函数使用技巧。

现在我们来了解一些常见的数列的生成函数。

常数数列

首先我们来看最简单的常数数列。比如，全是1，表示如下：

它的生成函数可以用类似斐波那契的思路，错项相减得到：

推广到任意常数k的情况，则可以给生成函数整体乘以常数k。

生成函数的移位和填项

有时我们定义数列，它从某一项开始才会遵循特定规律，这种时候我们可以先给生成函数乘以x的某次幂，进行移位。例如，某数列前三位是0，后面是常数1，那么，我们就给全是1的数列的生成函数乘以x3x^3x3

如果前三位不希望是0，而是1，2，3，则可以把对应的多项式加到原来的生成函数上：

自然数列

自然数列：

自然数列的处理思路比较特别，我们需要利用导数公式，把常数数列移位后求导。

我们约定G_c(x)G\_c(x)G_c(x) 是常数数列 1,1,1,...,1,...{1,1,1,...,1,...}1,1,1,...,1,...的生成函数

考虑到我们已知

把它代入到G(x)

可以在wolframalpha中查看求导的步骤以及验证最后展开的形式。

平方数列

平方数列：

参考从常数数列到自然数列的思路，我们把自然数列的生成函数乘以x，再求导即可:

在wolframalpha中查看

任意次方数列

作为平方数列的推广，我们可以推导任意次方数列的生成函数

这个生成函数没有一般的初等代数形式，但是我们可以从低阶的生成函数递推得到：

例如，三次方数列：

在wolframalpha中查看

数列相加

我们考虑两个数列

现在假设我们要求一个数列：

那么，根据多项式运算的性质，这个新数列的生成函数显然等于，此二数列生成函数相加：

多项式数列

有了数列相加和任意次方相关的知识，我们来考虑多项式数列：

我们可以把它按每一项分解后，对生成函数求和：

求前n项和

通过生成函数，我们可以解决任意数列的前n项和问题。

原数列

我们假设其前n项和数列为

那么根据前n项和的定义，有：

我们假设原数列的生成函数是G(x)G(x)G(x)，前n项和数列的生成函数是Gs(x)G_s(x)Gs​(x)

变换后可以得到：

例如，我们要求平方数列的前n项和

根据前面推理：

直接泰勒级数展开可得:

在wolframalpha中查看

组合数

从n个元素中选出k个元素的方案数。

当我们反过来，认为n固定，数列中第k项是CnkC_n^kCnk​时， 数列变成了：

此时，数列生成函数为：

这个形式是著名的二项式定理，也是杨辉三角形第n行第k个数。

生成函数的组合意义

当我们从两个不同集合中，选取总数为n的组合时，假设两个池子中可以选取的数量的生成函数分别是G1(x)G_1(x)G1​(x)和G2(x)G_2(x)G2​(x)，那么组合数G(x)的生成函数为二者相乘：

我们在第一节中苹果、香蕉、梨的组合方式就是例子。

生成函数的递推意义

有1分、2分、5分硬币若干，想要凑出1元钱，求有多少种凑法。

但是这个函数次数略高，wolframalpha也不好解了。

首先我们把它展开：

我们再回忆一下，什么样的递推关系能够产生这个形状的生成函数呢？我们把斐波那契数列的情况推广一下，假设有这样一个递推关系：

它的生成函数是：

那么，我们反过来，也可以从这个形状的生成函数，得到递推关系：

既然有了递推关系，我们又可以使用矩阵快速幂啦！

上一篇中，我们编写了一个二维矩阵的乘法，我们首先把它扩展成一个通用矩阵乘法：

const mul = (m1, m2) =>
    m1.map((row) => m2.map((any, j) => row.map((v, i) => v * m2[i][j]).reduce((a, b) => a + b, 0)));

快速幂沿用之前的代码

const pow = (v, n, mul = (a, b) => a * b) => {
    let r = v, m = n - 1, c = v;
    while(m > 0) {
        if(m % 2)
            r = mul(r, c);
        m = m >> 1;
        c = mul(c, c);
    }
    return r;
}

之后我们搞一个传输矩阵和原始矩阵，就可以算出结果啦：

const transformMatrix = [
[0,  0,  0,  0,  0,  0,  0,  1],
[1,  0,  0,  0,  0,  0,  0, -1],
[0,  1,  0,  0,  0,  0,  0, -1],
[0,  0,  1,  0,  0,  0,  0,  1],
[0,  0,  0,  1,  0,  0,  0,  0],
[0,  0,  0,  0,  1,  0,  0, -1],
[0,  0,  0,  0,  0,  1,  0,  1],
[0,  0,  0,  0,  0,  0,  1,  1]]

const originMatrix = [
[1, 1, 2, 2, 3, 4, 5, 6],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
]

const countCoin = n => mul(originMatrix, pow(transformMatrix, n, mul))[0][0];

console.log(countCoin(100)); //541

在关于硬币的几个动态规划问题中，我已经给出了此题的动态规划解法。我们这里刚好可以拿来验证。

我们把它推广到任意种类硬币的情况：

给定若干种数量不限的硬币的币值，编写代码计算n分有几种表示法。

设硬币面值为：

生成函数为：

我们要先编写多项式乘法代码来计算它的递推函数：

const polynomialMultiple = (p1, p2) => {
    let r = Array(p1.length + p2.length - 1).fill(0);
    p1.forEach((v1, i) =>
        p2.forEach((v2, j) => r[i + j] += v1 * v2)
    );
    return r;
}

注意，这个多项式相乘并不是经过优化的算法，仅仅是字面解法，我们在后文中会介绍多项式乘法的优化算法。

最后我们用代码生成传输矩阵和原始矩阵，就可以使用快速幂来求最终结果了：

function countCoins(values, n) {
    const transformMatrix = values
        .map(v => [1].concat(Array(v - 1).fill(0)).concat([-1]))
        .reduce(polynomialMultiple)
        .slice(1)
        .map(v => -v)
        .reverse()
        .map((v, i, {length}) => {
            let r = Array(length - 1).fill(0);
            (i > 0) && (r[i - 1] = 1);
            return r.concat(v);
        })
    let r = [1].concat(Array(transformMatrix.length - 1).fill(0));
    
    for(let value of values) 
        for(let i = value; i < transformMatrix.length; i++) 
            r[i] += r[i - value];
    
        
    const originMatrix = [r].concat(
        Array(transformMatrix.length - 1).fill(Array(transformMatrix.length).fill(0)))
        
    return mul(originMatrix, pow(transformMatrix, n, mul))[0][0];
}
countCoins([1,2,5],100); //541

经过验证，结果与快速幂的结果一致，但是时间复杂度从O(n)O(n)O(n)降低到了O(log(n))O(log(n))O(log(n))。

针对本题，实际上还有时间复杂度更好的解法，我们留待后文讨论。

其它一些数列

等差数列

等比数列

循环数列

小结

此处推荐一个数学公益网站：oeis.org/ 这里收录了大量的数列，提供它们的生成函数、递推公式和相关论文，本文中介绍的基本数列都在其中。

针对生成函数的初等代数变换可以极大地覆盖组合问题，我们遇到题目如有以下特点，可以往这个方向思考：

1. 求解结果是单个数值，且较大
2. 题目规模n有可能存在递推关系，或者组合关系