组合数学

组合数学

|课程笔记|6491 字13 分钟

生成函数#

定义#

对于一个数列 $\{a_0, a_1, a_2, \dots\}$，定义它的普通生成函数为：

$$ A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = \sum_{n=0}^{\infty} a_n x^n $$

直观记忆法：这里的 $x$ 只是一个“占位符”，它的指数 $n$ 代表“问题的规模”（比如取了 $n$ 个球），而前面的系数 $a_n$ 则代表该规模下的“组合方法数”。

多重组合问题#

基本原理：如果有 $m$ 种不同类型的小球，每种小球可选的数量范围为集合 $S_i$。从这些小球中总共取 $k$ 个的方法数为 $a_k$，那么数列 $\{a_k\}$ 的生成函数就是每种小球独立选择多项式的乘积：

$$ f(x) = \prod_{i=1}^m \left( \sum_{k \in S_i} x^k \right) $$

因为多项式相乘时，指数相加（$x^{k_1} \cdot x^{k_2} = x^{k_1+k_2}$）正好对应了“总球数相加”；而系数相乘再相加，正好契合了计数中的“加法原理与乘法原理”。

例：有 3 种水果：苹果、香蕉、橘子。现要选出 $n$ 个水果，我想知道买 $n$ 个水果有多少种买法，要求：

  1. 苹果的数量必须是偶数；
  2. 香蕉的数量没有限制；
  3. 橘子最多只能选2个。

根据上面的规则我们可以写出三种水果的多项式。苹果的多项式为 $1+x^2+x^4+\cdots$，$x$ 的指数代表我们拿了多少个，$x$ 前面的系数代表达成这个数量，有多少种方法数。如果我们选择 $k$ 个苹果不管怎么选都只有一种做法，所以系数都为 1。同理我们能写出香蕉的多项式为 $1+x+x^2+x^3+\cdots$，橘子的多项式为 $1+x+x^2$。

根据几何级数求和公式我们可以得到：

  1. $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots = \sum_{n=0}^{\infty} x^n$
  2. $\frac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \dots = \sum_{n=0}^{\infty} x^{2n}$

然后我们把每种水果的多项式相乘，就能得到水果买法的生成函数：

$$ f(x) = \left(\frac{1}{1-x^2}\right) \cdot \left(\frac{1}{1-x}\right) \cdot (1 + x + x^2) = \frac{1-x^3}{(1-x)^3(1+x)} $$

我们把生成函数展开成 $a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$ 的形式，$x^n$ 前面的系数 $a_n$ 就是买 $n$ 个水果有多少种买法。

例：考虑方程 $x_1+x_2+\dots+x_k=n$，其中 $n\ge0$。

  1. 设 $a_n$ 为上述方程正整数解的个数，求 $a_n$ 对应的生成函数。
  2. 设 $a_n$ 为上述方程非负偶数解的个数，求 $a_n$ 对应的生成函数。
  3. 设 $a_n$ 为上述方程满足 $x_1+x_2\le10$ 且 $x_3, \dots,x_k\le5$ 的非负整数解的个数，求 $a_n$ 对应的生成函数。

和上一题一个思路，我们先计算每一个变量 $x_i$ 的多项式。由于要求正整数，所以 $x_i$ 的取值范围在 1 到 正无穷，也就是它的指数可以取 $1,2,3,4,\dots$，因此 $x_i$ 的多项式即为 $x+x^2+x^3+\dots$。 第一问没有约束，所以生成函数就是 $k$ 个多项式的乘积：

$$ f(x)=(\frac{1}{1-x}-1)^k=(\frac{x}{1-x})^k $$

第二问要求非负偶数解，因此多项式为 $1+x^2+x^4+\dots$，生成函数为：

$$ f(x) = \frac{1}{(1-x^2)^k} $$

第三问把 $x_1$ 和 $x_2$ 捆绑在一起了，可以把他们当一个整体考虑，也就是 $x_1+x_2$ 一共可以取 $[0,1,2,3,\dots,10]$ 这几个数字，那么他们的方法数就不再固定为 $1$ 了。假如如果它们的和为 $2$，一共可以取 $(2,0), (1,1), (0,2)$ 这 3 种组合，也就是 $3 \cdot x^2 = 3x^2$，因此 $x_1+x_2$ 的多项式为：

$$ 1 + 2x + 3x^2 + 4x^3 + \dots + 11x^{10} $$

而 $x_3$ 到 $x_k$ 限制了非负整数解且 $\le5$，多项式为：$1+x+x^2+\dots + x^5$，所以生成函数为：

$$ f(x) = (1 + 2x + 3x^2 + 4x^3 + \dots + 11x^{10}) \cdot (1+x+x^2+\dots + x^5)^{k-2} $$

对于 $1+x+x^2+\dots + x^5$ 这样的有限等比数列，可以用等比数列求和公式进行化简：

$$ 1+x+x^2+\dots+x^k = \frac{1-x^{k+1}}{1-x} $$

非负整数的拆分#

例：你手里有面值为 1, 2, 3, 4, 5, … 一直到无穷大 的硬币，每种硬币都有无限多个。现在你要凑出总面值为 $n$ 的钱，一共有多少种凑法？

我们回想上一章节的做法，给每个面值的硬币写一个多项式，然后乘积就是凑法的生成函数，我们看 $x^n$ 前面的系数 $a_n$ 就知道凑出总面值为 $n$ 的钱有多少种凑法。一个 1 元硬币可以凑出 0 个 1 元、1 个 1 元、2 个 1 元、3 个 1 元，所以表达式为 $(1 + x^1 + x^2 + x^3 + x^4 + \dots) = \frac{1}{1-x}$。同理 2 元硬币的表达式为 $(1 + x^2 + x^4 + x^6 + x^8 + \dots) = \frac{1}{1-x^2}$。然后把所有面值硬币的括号全部乘起来，就得到了无限制整数拆分的生成函数 $P(x)$：

$$ P(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^4} \cdots = \prod_{i=1}^{\infty} \frac{1}{1-x^i} $$

按照之前的思路，指数代表的不是 物品的个数 吗？所以 2 元硬币的多项式不应该也是 $(1 + x^1 + x^2 + x^3 + x^4 + \dots) = \frac{1}{1-x}$ 吗？实际上指数代表的是 对最终总和 $n$ 的贡献值。比如正整数解那题 $n$ 代表正整数解的数量，所以我们每选择一个正整数贡献就会加一。这题 $n$ 代表的是总面值，所以我们每选择一个 2 元硬币对 $n$ 的贡献是 2。

  1. 假如要求 拆分出来的数互不相同，那么就是每种面值的硬币最多只能拿 1 枚：$Q(x) = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots = \prod_{i=1}^{\infty} (1+x^i)$
  2. 假如要求 只能拆分成奇数，那么只有面值为奇数（1元、3元、5元…）的硬币：$O(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^7} \cdots = \prod_{i=1}^{\infty} \frac{1}{1-x^{2i-1}}$

现在来看下非负整数拆分的问题：将非负整数 $n$ 分成 $k$ 个非负整数的和，即 $x_1 + x_2 + \dots + x_k = n$，有多少种分法，即满足 $x1 \le x2 \le \dots \le x_k$ 非负整数解的个数有多少种?

加上 $x1 \le x2 \le \dots \le x_k$ 这个限制之后题目就变成了求无序的解，数字 4 只能被拆为 $0,0,4$ 不能拆成 $4, 0,0$。其次变量之间被 $x_1 \le x_2 \le \dots \le x_k$ 锁死它们就不独立了，我们没办法直接为每个 $x_i$ 写括号。我们可以利用作差法，令：

  • $y_1 = x_1 \ge 0$
  • $y_2 = x_2 - x_1 \ge 0$
  • $y_3 = x_3 - x_2 \ge 0$
  • $\dots$
  • $y_k = x_k - x_{k-1} \ge 0$

现在把 $x$ 反过来用 $y$ 表示：

  • $x_1 = y_1$
  • $x_2 = y_1 + y_2$
  • $x_3 = y_1 + y_2 + y_3$
  • $\dots$
  • $x_k = y_1 + y_2 + \dots + y_k$

把这些代入原方程 $x_1 + x_2 + \dots + x_k = n$ 里面去，把相同的 $y$ 合并同类项：

$$ k \cdot y_1 + (k-1) \cdot y_2 + (k-2) \cdot y_3 + \dots + 1 \cdot y_k = n $$

这就回到了之前的凑硬币问题，$y_k$ 就是面值为 1 的硬币，它对总面值的贡献是 1。按照刚才学会的方法，直接为每种面值的硬币写括号并乘起来，得到对应的生成函数：

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

除了代数公式，整数拆分还有一个强力的形象化武器叫 Ferrers 图。Ferrers 图的本质价值是：把两类看起来完全不同的拆分之间的对应关系，变成一个简单的几何操作，让"它们数量相等"这件事变得一目了然。

比如，把 $7$ 拆分成 $4 + 2 + 1$，我们可以用圆点画成格子：

● ● ● ●   (4)
● ●       (2)
●         (1)

如果我们把这个图形沿着对角线翻转（转置矩阵），它会变成一个新图形：

● ● ●
● ●
●
●

读出每行的数量，它变成了：$3 + 2 + 1 + 1 = 7$。这就叫做它的共轭拆分（Conjugate Partition）。

例：已知 $a_{k,m}^n$ 表示方程 $x_1 + x_2 + \dots + x_k = n \quad (n \ge 0)$ 在满足以下条件时的非负整数解的个数 $1≤x_1​≤x_2​≤ \dots ≤x_k​≤m$，需要解决以下三个问题：

  1. 证明对称性：$a_{k,m}^n = a_{m,k}^n$。
  2. 证明递推关系：当 $n \ge m > 1$ 且 $n \ge k > 1$ 时，有 $a_{k,m}^n = a_{k,m-1}^n + a_{k-1,m}^{n-m}$。
  3. 求生成函数：令 $b_m^n = \sum_{k=1}^n a_{k,m}^n$（将 $m$ 视为常数），求序列 $\{b_m^n\}_{n \ge 1}$ 的普通生成函数 $B_m(x) = \sum_{n \ge 1} b_m^n x^n$。

$a_{k,m}^n$ 可以看做 $n$ 的一个分拆，其正的部分不超过 $m$，并且部分个数不超过 $k$。可以把它画成一个 Ferrers图，图有 k 行代表拆分为 k 个非负整数解，每行最多有 m 列代表非负整数大小不超过 m。将这个费勒斯图沿着主对角线进行转置，得到新图行数为 m 列数为 k，代表拆为 m 个整数，每个非负整数最大不超过 k，也就是 $a_{m,k}^n$。这说明，每一个“个数为 $k$，最大值 $\le m$”的拆分，都一一对应一个“个数 $\le m$，最大值等于 $k$”的拆分，即 $a_{k,m}^n = a_{m,k}^n$。

$a_{k,m}^n$ 表示将 $n$ 拆分为 $k$ 个正整数，且每个数都 $\le m$。我们可以根据这 $k$ 个正整数中最大那个数 $x_k$ 是否等于 $m$，将所有的解集分为互不相交的两类：

  • 第一类：最大值 $x_k < m$。因为所有 $x_i$ 都是正整数，且最大值严格小于 $m$，这就意味着所有的 $x_i$ 都满足 $x_i \le m-1$。因此，这一类的解数恰好等于“将 $n$ 拆分为 $k$ 个正整数，且最大值 $\le m-1$”的解数，即 $a_{k,m-1}^n$
  • 第二类：最大值 $x_k = m$。此时我们已经确定最大的部件 $x_k$ 占用了大小 $m$。我们将这个最大的数拿掉（或者说从总和 $n$ 中减去一个 $m$），剩下的方程就变成了：$x_1 + x_2 + \dots + x_{k-1} = n - m$。由于原序列满足 $1 \le x_1 \le x_2 \le \dots \le x_{k-1} \le x_k = m$，拿掉 $x_k$ 后，剩下的 $k-1$ 个变量依然是正整数，且它们的最大值显然仍然满足 $\le m$。因此，这一类的解数恰好 family 等于“将 $n-m$ 拆分为 $k-1$ 个正整数，且最大值 $\le m$”的解数，即 $a_{k-1,m}^{n-m}$。

由于这两类情况不重不漏，根据加法原理，总解数等于两类解数之和：

$$ a_{k,m}^n = a_{k,m-1}^n + a_{k-1,m}^{n-m} $$

指数型生成函数#

前面的普通生成函数解决了 组合问题，这里指数型生成函数解决的是 排列问题。对于数列 $\{a_k\}$，其指数型生成函数（EGF）定义为：

$$ f(x) = \sum_{k=0}^{\infty} a_k \frac{x^k}{k!} $$

这里的系数 $a_k$ 与指数 $k$ 与之前的含义相同，$a_k$ 指方案数，$k$ 指的是贡献。

例：用红、蓝、绿三种颜色的球拼成一个长度为 $k$ 的序列。要求：红色球必须取偶数个，蓝色和绿色球的数量没有限制。问有多少种不同的排列方法 $a_k$？

写出每种颜色对应的指数型选择多项式：

  1. 红（偶数个）：$1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots = \frac{e^x + e^{-x}}{2}$
  2. 蓝（无限制）：$1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x$
  3. 绿（无限制）：$1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x$

将它们相乘，得到总的指数型生成函数 $f(x)$：

$$ f(x) = \left(\frac{e^x + e^{-x}}{2}\right) \cdot e^x \cdot e^x = \frac{e^{3x} + e^x}{2} $$
双曲正/余弦的泰勒展开

我们熟知 $e^x$ 的泰勒展开式：

$$ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \frac{x^5}{5!} + \dots $$

如果把 $x$ 换成 $-x$，根据奇偶项的符号变化，可以得到 $e^{-x}$ 的展开式：

$$ e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \frac{x^5}{5!} + \dots $$

仔细观察两个式子，我们要保留的是 $x, x^3, x^5$ 这样的奇数次项，并消去常数项和偶数次项。将上面两个等式相减（做差）：

$$ e^x - e^{-x} = (1 - 1) + (x - (-x)) + \left(\frac{x^2}{2!} - \frac{x^2}{2!}\right) + \left(\frac{x^3}{3!} - \left(-\frac{x^3}{3!}\right)\right) + \dots $$

由于偶数次项符号相同，相减全抵消了；奇数次项符号相反，负负得正全部翻倍：

$$ e^x - e^{-x} = 2x + 2\frac{x^3}{3!} + 2\frac{x^5}{5!} + \dots = 2\left(x + \frac{x^3}{3!} + \frac{x^5}{5!} + \dots\right) $$

例：有 $m$ 种颜色的球，每种颜色可以重复使用。当限定每种颜色取 $k_1, k_2, \dots , k_m$ 个时 $k_1 + k_2 + \dots + k_m = k$, 问有多少种排列方法？

这题与之前的题有所不同，之前我们不管是选球 or 非负整数选一个值都是有一个范围，但是这题限定了第 $i$ 个球取 $k_i$ 个，所以：

$$ f_i(x) = 0 + 0 + \dots + 1 \cdot \frac{x^{k_i}}{k_i!} + 0 + \dots = \frac{x^{k_i}}{k_i!} $$

我们得到的生成函数就是：

$$ G(x) = f_1(x) \cdot f_2(x) \cdots f_m(x) = \prod_{i=1}^m \frac{x^{k_i}}{k_i!}= \frac{x^k}{k_1! k_2! \cdots k_m!} $$

然后 $\frac{x^k}{k!}$ 的系数就是排列方法数量，作一下变形：

$$ G(x) = \frac{k!}{k_1!k_2!\dots k_m!} \cdot \frac{x^k}{k!} $$

$\frac{k!}{k_1!k_2!\dots k_m!}$ 就是所求的排列数了。

课后题#

25秋课后题#

Q1

令 $y_i = x_i + 1 \quad (i = 1, 2, \dots, k)$。将每个变量各加 $1$，则有：

  1. 范围变化：因为 $x_i \ge 0$，所以 $y_i \ge 1$，即 $y_i$ 为正整数。
  2. 大小顺序：由 $x_1 \le x_2 \le \dots \le x_k$ 可得 $y_1 \le y_2 \le \dots \le y_k$。
  3. 方程转化：
$$ y_1 + y_2 + \dots + y_k = (x_1 + 1) + (x_2 + 1) + \dots + (x_k + 1) = (x_1 + x_2 + \dots + x_k) + k = n + k $$

因此，每一个非负整数解 $(x_1, \dots, x_k)$ 都唯一对应一组方程 $y_1 + \dots + y_k = n+k$ 的正整数解 $(y_1, \dots, y_k)$，且满足 $y_1 \le \dots \le y_k$。这建立了两组解之间的一一映射（双射），故其解的个数相等，即 $a_n^k = b_{n+k}^k$。

Q2

对于方程 $x_1 + x_2 + \dots + x_k = n$ 满足 $0 \le x_1 \le x_2 \le \dots \le x_k$ 的非负整数解，因为 $n \ge 1$，所以这 $k$ 个变量中正整数的个数 $m$ 必定满足 $1 \le m \le k$。我们可以根据这组解中正整数的个数 $m$ 对所有解进行分类。当解中恰好有 $m$ 个正整数时，由于序列递增，前 $k-m$ 个变量必然全为 $0$，后 $m$ 个变量为正整数。即：

$$ x_1 = x_2 = \dots = x_{k-m} = 0 $$$$ 1 \le x_{k-m+1} \le x_{k-m+2} \le \dots \le x_k $$

此时方程等价于：

$$ x_{k-m+1} + x_{k-m+2} + \dots + x_k = n $$

根据定义，上述满足大小顺序的 $m$ 个正整数解的个数恰好为 $b_n^m$。由于对于不同的 $m = 1, 2, \dots, k$，各类解集互不相交且不漏，根据加法原理，总解数 $a_n^k$ 等于各分类解数之和：

$$ a_n^k = b_n^1 + b_n^2 + \dots + b_n^k $$

$a^k_n$ 和 $b^k_{n+k}$ 的生成函数都能得到，但是我们没办法展开得到系数，所以不能知道$a^k_n$ 和 $b^k_{n+k}$ 的显式解。

Q3

分两种情况讨论：

  1. 最小项满足 $x_1=0$，剩下的 $k-1$ 个部分之和依然等于 $n$，且每个部分依然满足 $\le m$ 的限制，非负整数解个数为 $a^{k-1,m}_n$
  2. 最小项满足 $x_1 \ge 1$，那么把所有 $x_i-1$ 就能得到 $(x_1-1)+(x_2-1)+\dots = n-k$，对于 $x_i-1$ 满足条件 $x1-1\le x_2-1\le \dots \le m-1$，所以个数为 $a^{k,m-1}_{n-k}$

由于这两类分类不重不漏，根据加法原理，总方案数等于两类方案数之和：$a_n^{k,m} = a_n^{k-1,m} + a_{n-k}^{k,m-1}$。

Q1
$$ \begin{align} G(x) &= \sum \frac{1}{k+1} \frac{x^k}{k!} \\ xG(x) &=\sum \frac{1}{k+1} \frac{x^{k+1}}{k!} \\ \frac{d(xG(x))}{dx} &=\sum \frac{x^k}{k!} = e^x \\ xG(x) &= e^x + C \\ G(x) &= \frac{e^x-1}{x} \end{align} $$
Q2
$$ F(x) = (x+\frac{x^2}{2!}+\dots)^n = (e^x-1)^n $$
Q3
$$ F(x) = (x+\frac{x^3}{3!}+\frac{x^5}{5!}\dots)^n = \left( \frac{e^x - e^{-x}}{2} \right)^n $$

Q1
$$ \begin{align} G(x) &= \sum a_{n+k}x^n \\ x^kG(x) &= \sum a_{n+k} x ^{n+k} = A(x) - (a_0+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1}) \\ G(x) &= \frac{A(x) - (a_0+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1})}{x^k} \end{align} $$
Q2
$$ \begin{align} B(x) &= b_0 + b_1 x + b_2 x^2 + b_3 x^3 + \dots \\ &= a_0 + (a_0 + a_1)x + (a_0 + a_1 + a_2)x^2 + (a_0 + a_1 + a_2 + a_3)x^3 + \dots \\ &= (a_0 + a_1 x + a_2 x^2 + \dots)(1 + x + x^2 + x^3 + \dots \\ &= \frac{A(x)}{1-x} \end{align} $$
Q3
$$ \begin{align} B(x) &= \sum_{n=0}^{\infty} \left( \sum_{i=n}^{\infty} a_i \right) x^n \\ &= \sum_{i=0}^{\infty} \sum_{n=0}^{i} a_i x^n \\ &= \sum_{i=0}^{\infty} a_i \left( \sum_{n=0}^{i} x^n \right) \\ &= \sum_{i=0}^{\infty} a_i \cdot \frac{1 - x^{i+1}}{1-x} \\ &= \frac{1}{1-x} \left( \sum_{i=0}^{\infty} a_i - \sum_{i=0}^{\infty} a_i x^{i+1} \right) \\ &= \frac{A(1) - xA(x)}{1-x} \end{align} $$

求数列生成函数的通法就是：把 $G(x) = \sum{a_nx^n}$ 凑成 $\sum x^n=\frac{1}{1-x}$ 的标准形式，然后就可以对 $\frac{1}{1-x}$ 积分求导还原。

Q1
$$ \begin{align} \sum_{n=0}^{\infty} n x^n &= x \frac{d}{dx} \left( \frac{1}{1-x} \right) = x \cdot \frac{1}{(1-x)^2} = \frac{x}{(1-x)^2} \\ \sum_{n=0}^{\infty} n^2 x^n &= x \frac{d}{dx} \left[ \frac{x}{(1-x)^2} \right]= x \cdot \frac{(1-x) + 2x}{(1-x)^3} = \frac{x+x^2}{(1-x)^3} \\ G(x) &= \sum_{n=0}^{\infty} n^3 x^n = x \frac{d}{dx} \left[ \frac{x+x^2}{(1-x)^3} \right] = \frac{x(1+4x+x^2)}{(1-x)^4} = \frac{x+4x^2+x^3}{(1-x)^4} \end{align} $$
Q2
$$ \begin{align} G(x) &= \sum_{n=0}^{\infty} \frac{1}{n+1} x^n \\ x G(x) &= \sum_{n=0}^{\infty} \frac{1}{n+1} x^{n+1} \\ \frac{d}{dx} [x G(x)] &= \sum_{n=0}^{\infty} \frac{n+1}{n+1} x^n = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \\ x G(x) &= \int_0^x \frac{1}{1-t} dt = -\ln(1-x) \\ G(x) &= -\frac{\ln(1-x)}{x} \end{align} $$

课件习题#

Q1
$$ \begin{aligned} A(x)&=\sum_{n=0}^{\infty}a_nx^n =\sum_{n=0}^{\infty}n(n+2)x^n\\ &=\sum_{n=0}^{\infty}n^2x^n+2\sum_{n=0}^{\infty}nx^n\\[4pt] P(x)&=\sum_{n=0}^{\infty}nx^n\\ \sum_{n=0}^{\infty}x^n&=\frac1{1-x}\\ \sum_{n=1}^{\infty}nx^{n-1}&=\frac1{(1-x)^2}\\ P(x)&=\frac{x}{(1-x)^2}\\[4pt] Q(x)&=\sum_{n=0}^{\infty}n^2x^n=xP'(x)\\ P'(x)&=\frac{d}{dx}\left(\frac{x}{(1-x)^2}\right) =\frac{1+x}{(1-x)^3}\\ Q(x)&=\frac{x(1+x)}{(1-x)^3} =\frac{x+x^2}{(1-x)^3}\\[4pt] A(x)&=\frac{x+x^2}{(1-x)^3} +\frac{2x}{(1-x)^2}\\ &=\frac{x+x^2+2x(1-x)}{(1-x)^3}\\ &=\frac{3x-x^2}{(1-x)^3} \end{aligned} $$
Q2
  1. 求 $1 \cdot 3 + 2 \cdot 4 + \dots + n(n+2)$ 的和式，可以看做求数列 $b_n=\sum_{i=0}^n a_i$ 生成函数 $S(x)=\sum b_n$ 的系数
  2. 根据性质 3 可以得到 $\{b_n\}$ 的生成函数为 $S(x)=\frac{A(x)}{1-x}=\frac{3x-x^2}{(1-x)^4}= 3 \cdot \frac{x}{(1-x)^4} - \frac{x^2}{(1-x)^4}$
  3. 根据广义二项式定理把分母拆开 $\frac{1}{(1-x)^4} = (1-x)^{-4} = \sum_{k=0}^\infty \binom{k+4-1}{k}x^k = \sum_{k=0}^\infty \binom{k+3}{3}x^k$
  4. 第一项有了 $x$ 所以对应 $x_{n-1}$ 的系数 $\dbinom{n+2}{2}$，第二项有了 $x^2$ 所以对应 $x^{n-2}$ 的系数 $\dbinom{n+1}{1}$
  5. 那么 $x^n$ 的系数就是 $[x^n]S(x) = 3\binom{n+2}{3} - \binom{n+1}{3}$
  1. $(1-x)^{-n} = \sum_{k=0}^\infty \binom{k+n-1}{k} x^k = 1 + \binom{n}{1}x + \binom{n+1}{2}x^2 + \dots$
  2. $\binom{n}{r} = \binom{n}{n-r}$

Q1
  1. 参考之前的思路，把 $a$ 和 $b$ 看做一个整体，它对应的多项式就是 $1+2^2*\frac{x^2}{2!}+2^4*\frac{x^4}{4!}+\dots$。需要注意这题是排列问题，所以 $a$ 和 $b$ 两个字母长度为 $k$ 的排列数为 $2^k$。
  2. 对于剩下字母没有要求 $1+x+\frac{x^2}{2!}+\dots=e^x$
  3. 得到乘积为 $(1+2^2*\frac{x^2}{2!}+2^4*\frac{x^4}{4!}+\dots)e^{3x}=(1+\frac{(2x)^2}{2!}+\frac{(2x)^4}{4!}+\dots)e^{3x}=\dfrac{e^{2x}+e^{-2x}}{2} * e^{3x}= \frac{1}{2}(e^{5x} + e^x)$
  4. 然后再展开 $\frac{1}{2}(1+5x+\frac{(5x)^2}{2!}+\dots) + \frac{1}{2}(1+x+\frac{x^2}{2!}+\dots)$
  5. 可以知道 $\frac{x^n}{n!}$ 的系数为 $\frac{5^n+1}{2*n!}$

Q1
  1. 先算第一个方程的非整数解，对于单个 $x$ 的多项式为 $1+x+x^2+\dots=\frac{1}{1-x}$
  2. 乘积就是 $\frac{1}{(1-x)^7}$，然后我们需要 $x^{13}$ 前面的系数
  3. 根据二项式展开得到系数为 $\binom{19}{13}$
  4. 同理计算第二个方程的非负整数解为 $\binom{19}{6}$
  5. 根据二项式系数的性质得到两个相等。

Q1
  1. 1g 砝码的多项式为 $1+x+x^2+x^3$
  2. 2g 砝码的多项式为 $1+x^2+x^4+x^6+x^8$
  3. 4g 砝码的多项式为 $1+x^4+x^8$
  4. 连乘起来得到 $1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8+5x^9+5x^{10}+5x^{11}+4x^{12}+4x^{13}+3x^{14}+3x^{15}+2x^{16}+2x^{17}+x^{18}+x^{19}$
  5. 指数为重量，系数为方案数

Q1
就是分情况讨论，最大的正整数是不是 $m$ 就好了。

递推关系#

定义#

递推关系就是根据前几项定义当前项的规律，找到通项公式。

例如 Hanoi 塔这个经典例子，我们假设将 $n$ 个圆盘从 A 移到 C，设最少需要 $T_n$ 步。

  • 那么将上面 $n-1$ 个圆盘从 A 移到 B 需要 $T_{n-1}$ 步
  • 将最大盘从 A 移到 C 需要 $1$ 步
  • 将 B 上 $n-1$ 个圆盘移到 C 需要 $T_{n-1}$ 步

就能得到递推关系 $T_n = 2T_{n-1} + 1$，根据这个递推关系我们就能找到通项公式：$T_n=2^n-1$。接下来研究的就是：如何根据递推关系得到通项公式。

常系数线性齐次#

  • 一般形式：$a_n + c_1a_{n-1} + c_2a_{n-2} + \dots + c_ka_{n-k} = 0$
  • 解法：令 $a_n = x^n$ 代入，即可导出它的特征方程：$x^k + c_1x^{k-1} + c_2x^{k-2} + \dots + c_k = 0$
  • 通解：
    • 特征方程有 $k$ 个互不相同的根 $q_1, q_2, \dots, q_k$，那么通解可以直接写为 $a_n = \lambda_1 q_1^n + \lambda_2 q_2^n + \dots + \lambda_k q_k^n$
    • 若某个根 $q_1$ 是 $m$ 重根，它贡献的项为 $(\lambda_0 + \lambda_1 n + \lambda_2 n^2 + \dots + \lambda_{m-1} n^{m-1}) q_1^n$

例：求解 $a_n = a_{n-1} + a_{n-2}$，初始条件 $a_0 = 0, a_1 = 1$。

  1. 写出特征方程 $x^2-x-1=0$
  2. 计算特征根 $q_1 = \frac{1 + \sqrt{5}}{2}, \quad q_2 = \frac{1 - \sqrt{5}}{2}$
  3. 通解写为 $a_n = \lambda_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + \lambda_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n$
  4. 代入初始条件解得 $\lambda_1 = \frac{1}{\sqrt{5}}, \lambda_2 = -\frac{1}{\sqrt{5}}$
  5. 通项公式为 $a_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right]$

常系数线性非齐次#

  • 一般形式：$a_n + c_1a_{n-1} + \dots + c_ka_{n-k} = f(n)$
  • 解法：
    • 非齐次项是常数 $f(n)=m$，左移一位就可以把常数项消掉。原式：$a_n - 3a_{n-1} = 5$ 左移一步：$a_{n+1} - 3a_n = 5$，两式相减就能得到常系数线性齐次 $a_{n+1​}−4a_n​+3a_{n−1}​=0$。
    • 非齐次项是 $P_k(n) \cdot \lambda^n$ 的形式，那么它会为最终的特征方程贡献一个额外的辅助根 $x = \lambda$，其重数为 $k + 1$。比如 $a_{n+1}-2a_n=n^2$，它可以看做 $a_{n+1}-2a_n=n^2\times 1^n$，所以辅助根为 $\lambda=1$，通解就是 $a_n=\lambda_1 2^n + (\lambda_2+\lambda_3 n)1^n$。
    • 非齐次项是指数 $f(n)=m^n$，可以通过乘 $m$ 加上左移的操作把非齐次项消掉。例如 $a_n​−3a_{n−1}​=3^n$，左移可以得到 $a_{n+1}-3a_n=3^{n+1}$，乘 $3$ 可以得到 $3a_n​−9a_{n−1}​=3^{n+1}$，把 ①-② 就能得到 $a_{n+1}-6a_n+9a_{n-1}=0$ 然后按照线性齐次的方法解决。

递推关系和生成函数#

如何用生成函数求递推关系的通项公式

例：用生成函数法再次求解方程：$a_n - 2a_{n-1} = 3^n$ ($n \ge 1$)，已知 $a_0 = 1$。

  1. 两侧同乘 $x^n$ 得到 $a_nx^n - 2a_{n-1}x^n=3^nx^n$
  2. 两侧同时求和 $\sum_{n=1}^{\infty} a_n x^n - 2 \sum_{n=1}^{\infty} a_{n-1} x^n = \sum_{n=1}^{\infty} (3x)^n$
  3. 改写成 $\sum_0^{\infty}a_nx^n=A(x)$ 的形式 $(A(x) - a_0) - 2x A(x) = \frac{3x}{1-3x}$
  4. 然后代入 $a_0=1$ 就能得到 $A(x) = \frac{1}{(1-2x)(1-3x)} = \frac{3}{1-3x} - \frac{2}{1-2x}$
  5. 应用几何级数展开公式得到 $A(x) = 3 \sum_{n=0}^{\infty} (3x)^n - 2 \sum_{n=0}^{\infty} (2x)^n = \sum_{n=0}^{\infty} \left( 3^{n+1} - 2^{n+1} \right) x^n$
  6. 所以得到 $a_n = 3^{n+1} - 2^{n+1}$