具体数学
阅读数:126 评论数:0
跳转到新版页面分类
数学
正文
一、递归问题
河内塔（Tower of Hanoi）是一个经典的数学谜题和逻辑游戏，这个谜题涉及到一组圆盘和三根柱子，玩家的目标是将所有圆盘从一根柱子移动到另一根柱子，同时遵守以下规则：
- 每次只能移动一个圆盘。
- 大圆盘不能放在小圆盘上面。
河内塔问题通常有三根柱子，分别标记为A、B和C。开始时，所有圆盘按照从大到小的顺序堆叠在柱子A上。
玩家的目标是将所有圆盘从柱子A移动到柱子C，可以借助柱子B作为辅助。
河内塔问题的解决方法可以通过递归算法来实现。基本思路是将问题分解为较小的子问题，然后递归地解决这些子问题。
（1）递归步骤
- 将 n−1个圆盘从柱子A移动到柱子B，利用柱子C作为辅助。
- 将剩下的最大圆盘从柱子A移动到柱子C。
- 最后将 n−1 个圆盘从柱子B移动到柱子C，利用柱子A作为辅助。
（2）递归终止条件
当只有一个圆盘时，直接将它从柱子A移动到柱子C。
在这个问题中，有一个编号为 1 到 $n$ 的人围坐在一圈里。从第一个人开始，每次数到第 $k$ 个人，就将该人移除圈外，然后从下一个人开始继续数。重复这个过程，直到圈内只剩下一个人为止。问题的关键是找出最后留在圈内的那个人的编号。
约瑟夫问题有一个著名的解决方法，可以通过数学推导得到。以下是一个简单的解决方法：
（1）递推公式
设 $f(n, k)$ 表示 n 个人中最后留下的人的编号。那么我们有递推公式：
$ f(n, k) = (f(n-1, k) + k) \mod n $
推导过程：
- 假设我们已经知道 $ n-1 $ 个人中最后留下的人的编号为 $ f(n-1, k) $。现在考虑有 $ n $ 个人的情况。
- 在有 $ n $ 个人的情况下，第一个被移除的人的编号是 $ k \mod n $。
- 那么，第 $ k $ 个人被移除后，剩下的 $ n-1 $ 个人中最后留下的人的编号应为 $ f(n-1, k) $。但由于我们从第 $ k $ 个人开始重新计数，所以实际上是 $ f(n-1, k) $ 在圈中的下一个位置，即 $ (f(n-1, k) + k) \mod n $。
（2）初始条件
当只有一个人时，即 $n=1$ 时，最后留下的人的编号为 1，即 $f(1, k) = 1$。
二、和式
和式记号通常用于表示数列的和。在数学中，和式记号通常用希腊大写字母 sigma（Σ）表示，它表示对一系列项进行求和的操作。和式的一般形式如下：
$ \sum_{i=m}^{n} a_i $
和式直接表示了一系列值的总和，而递归式通过定义每一项与前一项的关系来描述整个序列。
三、整值函数
四、数论
（1）完全剩余系
在模 $m$ 下，一个完全剩余系是一组数，其中每个数模 $m$ 后的余数都是不同的。换句话说，这个集合中的任意两个不同的数在除以 $m$ 后都不会得到相同的余数。例如，集合 $\{0, 1, 2, 3, 4\}$ 是模 $5$ 下的一个完全剩余系，因为这些数除以 $5$ 后的余数分别是 $\{0, 1, 2, 3, 4\}$，互不相同。
（2）简化剩余（独立剩余）
一个模 $m$ 下的简化剩余系是由与 $m$ 互素的整数组成的完全剩余系。在简化剩余系中，每个数都代表了一个与 $m$ 互素的同余类。例如，模 $10$ 下的简化剩余系可以是 $\{1, 3, 7, 9\}$，因为这些数与 $10$ 互素。
（3）中国独立定理
中国剩余定理提供了一种方法，用于解决一系列形式为 $x \equiv a_i \mod m_i$ 的同余方程，其中 $m_i$ 之间互素。这个定理说明了为什么我们可以独立地考虑每个同余方程，并最终找到一个解，该解在所有给定的模下都有效。
解决中国剩余定理问题的一般步骤如下：
- 计算M，计算所有模数的乘积，$M = m_1m_2\ldots m_n$。
- 计算单个模的乘积。对于每个 $i$，计算 $M_i = \frac{M}{m_i}$。
- 计算逆元。找到每个 $M_i$ 关于模 $m_i$ 的逆元，记为 $M_i^{-1}$。逆元的定义是 $M_iM_i^{-1} \equiv 1 \mod m_i$。
- 计算解。
解 $x$ 可以通过以下公式计算：
$x \equiv \sum_{i=1}^{n}a_iM_iM_i^{-1} \mod M$
示例：
假设我们有以下同余方程组：
1. $x \equiv 2 \mod 3$
2. $x \equiv 3 \mod 5$
3. $x \equiv 2 \mod 7$
我们可以按照上述步骤解决这个问题：
1. $M = 3 \times 5 \times 7 = 105$
2. $M_1 = 35, M_2 = 21, M_3 = 15$
3. $M_1^{-1} = 2 \mod 3, M_2^{-1} = 1 \mod 5, M_3^{-1} = 1 \mod 7$（这里我们通过计算或查找表格来找到逆元）
4. $x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \equiv 233 \mod 105$
因此，$x \equiv 23 \mod 105$ 是这个同余方程组的一个解。
（1）$\phi$ 函数
$\phi(n)$ 函数，也称为 Euler's Totient Function，对于一个正整数 $n$，表示小于或等于 $n$ 的正整数中与 $n$ 互素的数的数量。互素意味着两个数的最大公约数为 1。
性质：
- 对于素数 $p$，$\phi(p) = p - 1$，因为一个素数小于它的所有正整数都与它互素。
- 对于两个互素的正整数 $a$ 和 $b$,有 $\phi(a \cdot b) = \phi(a) \cdot \phi(b)$。这是因为每一个与 $a$ 互素的数都可以与每一个与 $b$ 互素的数组合，形成一个与 $a \cdot b$ 互素的唯一数。
- 如果 $n$ 是素数 $p$ 的 $k$ 次幂，即 $n = p^k$**，那么 $\phi(n) = p^k - p^{k-1}$。所有不与 $n$ 互素的数都可以写成 $p$ 的倍数的形式，即 $p, 2p, 3p, \ldots, p^{k-1}p$。我们简单地从所有的数中减去那些包含 $n$ 的素因子 $p$ 的数，剩下的就是与 $n$ 互素的数。
- 如果 $n$ 的质因数分解是 $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}$，那么 $\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$。所有小于 $n$ 的数中，有 $\frac{1}{p_i}$ 的比例的数能被 $p_i$ 整除，因此它们不与 $n$ 互素。
（2） $\mu(n)$函数
对于任意正整数 $n$，莫比乌斯函数 $\mu(n)$ 定义为：
- 如果 $n$ 是平方数的倍数，则 $\mu(n) = 0$。
- 如果 $n$ 不是平方数的倍数，并且 $n$ 有偶数个不同的质因数，则 $\mu(n) = 1$。
- 如果 $n$ 不是平方数的倍数，并且 $n$ 有奇数个不同的质因数，则 $\mu(n) = -1$。
性质：
- 乘性。莫比乌斯函数是一个乘性函数，即对于任意两个互质的正整数 $a$ 和 $b$，有 $\mu(a \cdot b) = \mu(a) \cdot \mu(b)$。
- 求和性质。对于任意正整数 $n$，莫比乌斯函数的和满足 $\sum_{d|n} \mu(d) = 0$，其中 $d|n$ 表示 $d$ 是 $n$ 的一个正除数。唯一的例外是 $n = 1$，此时 $\sum_{d|1} \mu(d) = \mu(1) = 1$。
五、二项式系数
二项式系数，通常表示为 $\binom{n}{k}$ 或 $C(n, k)$，在数学中用于表示在没有重复的情况下，从 $n$ 个项目中选择 $k$ 个项目的方法数。
（1）对称性
$ \binom{n}{k} = \binom{n}{n-k} $
这个恒等式说明，从 $n$ 个项目中选择 $k$ 个项目的方法数，与从相同的 $n$ 个项目中选择剩下的 $n-k$ 个项目的方法数相同。
（2）帕斯卡恒等式
$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $
这个恒等式可以通过考虑一个特定的项目是否被选中来理解。选择 $k$ 个项目的方法数可以分为两部分：一部分包括了这个特定的项目（因此，从剩下的 $n-1$ 个项目中选择 $k-1$ 个），另一部分不包括这个特定的项目（从剩下的 $n-1$ 个项目中选择 $k$ 个）。
（3）加和恒等式
$ \sum_{k=0}^{n} \binom{n}{k} = 2^n $
这个恒等式表示，从 $n$ 个项目中选择任意数量的项目的方法数总和等于 $2^n$。这是因为每个项目有两种可能性：被选中或不被选中。
（4）上升和下降幂的恒等式
上升幂：$ (x)_n = x(x+1)(x+2) \cdots (x+n-1) = \sum_{k=0}^{n} \binom{n}{k} x^k $
下降幂：$ x^n = \sum_{k=0}^{n} \binom{n}{k} (x)_k $
（5）Vandermonde恒等式
$ \binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} $
这个恒等式可以用于证明，从两个不相交的集合（一个有 $m$ 个元素，另一个有 $n$ 个元素）中选择 $r$ 个元素的方法数，等于对所有可能的 $k$ 值，从第一个集合中选择 $k$ 个元素，从第二个集合中选择 $r-k$ 个元素的方法数的总和。
生成函数是一种强大的数学工具，用于研究序列和解决组合数学问题。生成函数将序列的项与某个函数的系数联系起来，通过分析这个函数，可以得到序列的性质。
（1）定义
给定一个序列 $\{a_n\}$，其生成函数 $G(x)$ 定义为无穷级数：
$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n$
这里的 $x$ 通常是一个形式变量，意味着 $G(x)$ 的分析通常集中在代数操作和系数比较上，而不是函数的收敛性或数值计算。
超几何函数可以看作是普通幂级数的推广，能够解决一系列复杂的数学问题。
（1）高斯超几何函数
高斯超几何函数是一种特别重要的超几何函数，通常表示为 $_2F_1$。它的定义是：
$
_2F_1(a, b; c; z) = \sum_{n=0}^{\infty} \frac{(a)_n (b)_n}{(c)_n} \frac{z^n}{n!}
$
其中，$a$、$b$ 和 $c$ 是常数参数，$z$ 是函数的变量，$(x)_n$ 表示 $x$ 的上升阶乘幂，定义为：
$
(x)_n = x(x+1)(x+2)\cdots(x+n-1)
$
对于 $n=0$，定义 $(x)_0 = 1$。
超几何变换通常指的是利用超几何函数进行的变换。
（1）线性变换
- $ _2F_1(a, b; c; z) = (1-z)^{-a} _2F_1\left(a, c-b; c; \frac{z}{z-1}\right) $
- $ _2F_1(a, b; c; z) = (1-z)^{-b} _2F_1\left(c-a, b; c; \frac{z}{z-1}\right) $
这些变换利用超几何函数的参数和变量之间的关系，提供了在不同参数和变量取值下计算超几何函数的方法。
（2）欧拉变换
- $ _2F_1(a, b; c; z) = (1-z)^{c-a-b} _2F_1(c-a, c-b; c; z) $
欧拉变换是超几何函数的一个重要性质，它展示了函数在参数变换下的对称性。
（3）Kummer变换
- $ _2F_1(a, b; a+b-c+1; 1-z) = \frac{\Gamma(a+b-c+1)\Gamma(c)}{\Gamma(a)\Gamma(b)} _2F_1(c-a, c-b; c-a-b+1; z) $
Kummer变换是处理 $1-z$ 形式变量时的一个有用工具，特别是在解决微分方程时。
部分超几何和式是上述级数的部分和，可以表示为：
$
S_N(a, b; c; z) = \sum_{n=0}^{N} \frac{(a)_n (b)_n}{(c)_n} \frac{z^n}{n!}
$
这里的 $N$ 是一个非负整数，表示求和的最后一项。部分超几何和式通常用于近似计算超几何函数的值，特别是当完整级数的解析求和困难或不可能时。
六、特殊的数
斯特林数（Stirling numbers）是组合数学中的一类特殊数
（1）第一类斯特林数
第一类斯特林数 $s(n, k)$ 表示将 $n$ 个对象排成 $k$ 个非空循环排列的方法数。
- $s(0, 0) = 1$
- $s(n, 0) = 0$，对所有 $n > 0$
- $s(n, n) = 1$，对所有 $n$
- $s(n, k) = s(n-1, k-1) - (n-1) \cdot s(n-1, k)$，对所有 $n, k > 0$
第一类斯特林数的指数生成函数是：
$x(x-1)(x-2) \cdots (x-n+1) = \sum_{k=0}^{n} s(n, k) \cdot x^k$
（2）第二类斯特林数
第二类斯特林数 $S(n, k)$ 表示将 $n$ 个对象分成 $k$ 个非空不区分顺序的集合的方法数。
- $S(0, 0) = 1$
- $S(n, 0) = 0$，对所有 $n > 0$
- $S(n, n) = 1$，对所有 $n$
- $S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)$，对所有 $n, k > 0$
第二类斯特林数的指数生成函数是：
$\frac{(e^x - 1)^k}{k!} = \sum_{n=k}^{\infty} S(n, k) \frac{x^n}{n!}$
欧拉数可以通过直接展开母函数或使用递归关系来计算。例如，前几个非零欧拉数是：
- $E_0 = 1$
- $E_2 = -1$
- $E_4 = 5$
- $E_6 = -61$
- $E_8 = 1385$
（1）定义
欧拉数 $E_n$ 可以通过欧拉多项式的系数来定义，其中欧拉多项式是通过以下母函数给出的：
$ \frac{2e^x}{e^{2x} + 1} = \sum_{n=0}^{\infty} E_n \frac{x^n}{n!} $
（2）性质
- 奇偶性。当 $n$ 为奇数时，$E_n = 0$。因此，非零的欧拉数只在偶数下标处出现。
- 交错性。欧拉数交错出现，即它们的符号交替变化。
（3）递归
对于非负整数 $n$，欧拉数 $E_n$ 可以通过以下递归式计算：
$E_n = \sum_{k=0}^{n-1} \binom{n}{k} E_k$
对于所有 $n > 0$，并且 $E_0 = 1$。需要注意的是，这个递归式实际上并不直接给出欧拉数，而是给出了一种计算它们绝对值的方式，并且需要根据 $n$ 的值来调整符号。
欧拉数的符号遵循一个简单的规则：
- 当 $n$ 是奇数时，$E_n = 0$。
- 当 $n$ 是偶数时，欧拉数的符号交替出现，从 $E_0 = 1$ 开始。
第 $n$ 个调和数定义为前 $n$ 个正整数倒数的和，数学上通常表示为 $H_n$，定义如下：
$ H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \sum_{k=1}^{n} \frac{1}{k} $
（1）性质
- 增长速度。
调和数以对数的速度增长，随着 $n$ 的增加，$H_n$ 趋近于自然对数 $\ln(n)$ 加上欧拉-马歇罗尼常数 $\gamma$，大约等于 0.57721。即：
$ H_n \approx \ln(n) + \gamma $
- 发散性。虽然调和数增长得很慢，但它们会随着 $n$ 的增加无限增长，即调和级数是发散的。
（1）定义
伯努利数 $B_n$ 可以通过伯努利多项式的递推关系定义。伯努利数的生成函数定义为：
$ \frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!} $
其中，$e^x$ 是自然对数的底 $e$ 的 $x$ 次幂。
（2）性质
- 交替性。从 $B_1$ 开始，奇数项的伯努利数（除了 $B_1$）都是零，即 $B_{2n+1} = 0$ 对于所有 $n \geq 1$。
- 前几个伯努利数。 - $B_0 = 1$
- $B_1 = -\frac{1}{2}$
- $B_2 = \frac{1}{6}$
- $B_3 = 0$
- $B_4 = -\frac{1}{30}$
- 以此类推。
（3）递推公式
伯努利数可以通过以下递推关系计算：
$ \sum_{k=0}^{n} \binom{n+1}{k} B_k = 0, \quad \text{对于 } n > 0 $
这个递推关系可以用来计算任意高阶的伯努利数。
（1）定义
斐波那契数列是通过以下递归关系定义的：
- $F_0 = 0$,
- $F_1 = 1$,
- $F_n = F_{n-1} + F_{n-2}$ 对所有 $n \geq 2$.
这意味着，从第三项开始，每一项都是前两项的和。
（2）前几项
根据上述定义，斐波那契数列的前几项是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
（3）性质
- 黄金比例。斐波那契数列中相邻两项的比值随着数列的增长，逐渐趋近于黄金比例 $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887...$。具体来说，$\lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi$。
- 封闭形式。
斐波那契数列的第 $n$ 项可以用“斐波那契公式”（也称为“比内公式”）直接计算，而不是通过递归：
$ F_n = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}} $
其中，$\phi$ 是黄金比例。
- 整除性质。如果 $m$ 能整除 $n$，那么 $F_m$ 能整除 $F_n$。
- 求和公式。斐波那契数列的前 $n$ 项和可以表示为 $F_0 + F_1 + \cdots + F_n = F_{n+2} - 1$。
连项式（Continued Fraction）是数学中一种用于表示实数的表达式，特别是用于无理数的精确表示和有理数的近似。
连项式的一般形式可以表示为：
$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \ddots}}}}$
其中，$a_0$ 是整数部分，而 $a_1, a_2, a_3, \ldots$ 是连续的正整数。这种形式也被称为简单连续分数（Simple Continued Fraction）。
七、生成函数
（1）多米诺排列问题
多米诺排列问题是一个经典的组合数学问题，它要求计算用 $1 \times 2$ 多米诺骨牌完全覆盖 $2 \times n$ 矩形板的排列方式数量。这个问题可以通过生成函数来解决。
为了构建这个问题的生成函数，我们首先观察到每个多米诺骨牌覆盖两个单位的面积。因此，对于 $2 \times n$ 的矩形板，我们可以通过添加 $n$ 个多米诺骨牌来完全覆盖它。
设 $f_n$ 表示完全覆盖 $2 \times n$ 矩形板的排列方式数量。我们想要构造一个生成函数 $F(x)$，它的幂级数展开的系数给出了每种长度 $n$ 的覆盖方式数量：
$F(x) = \sum_{n=0}^{\infty} f_n x^n$
对于 $2 \times n$ 矩形板，有两种基本的覆盖方式：横向和纵向。横向覆盖占用 $2 \times 1$ 空间，可以认为是一个“基础块”。纵向覆盖实际上是两个横向覆盖叠加，也可以看作是两个基础块。
因此，每增加一个多米诺骨牌，实际上是增加了一个或两个“基础块”的长度。这意味着，对于每一个 $n$，$f_n$ 可以通过 $f_{n-1}$（增加一个横向覆盖）和 $f_{n-2}$（增加两个纵向覆盖）来计算。这给出了一个递归关系：
$f_n = f_{n-1} + f_{n-2}$
注意，$f_0 = 1$（没有多米诺骨牌也是一种覆盖方式），$f_1 = 1$（只有一种方式放置一个多米诺骨牌）。
通过这个递归关系，我们可以构造 $F(x)$ 的差分方程：
$F(x) - xF(x) - x^2F(x) = 1$
解这个方程，我们得到：
$F(x) = \frac{1}{1 - x - x^2}$
这个生成函数的系数正好对应于斐波那契数列，这是因为覆盖 $2 \times n$ 矩形板的方法数满足斐波那契递归关系。因此，$f_n$ 实际上就是斐波那契数列的第 $n+1$ 项（因为 $f_0 = 1$ 对应斐波那契序列的第一项）。
这种方法展示了如何使用生成函数来解决多米诺排列问题，同时也揭示了这个问题与斐波那契数列之间的联系。
（2）换零钱
换零钱问题是一个经典的组合计数问题，其目标是确定用一组给定面额的硬币凑成特定金额的不同方式数量。利用生成函数来解决这个问题是一种强大的方法，因为它能够将问题转化为寻找特定幂次项系数的问题。下面我们将详细解释如何使用生成函数来解决换零钱问题。
- 问题假设
假设我们有无限数量的几种硬币，面额分别为 $d_1, d_2, \ldots, d_k$，我们想要凑出总金额 $n$。我们的目标是找到凑出总金额 $n$ 的所有不同方式的数量。
- 构建生成函数
对于每种面额的硬币 $d_i$，我们构建一个生成函数：
$G_{d_i}(x) = 1 + x^{d_i} + x^{2d_i} + x^{3d_i} + \ldots$
这个生成函数实际上是一个几何级数，其中 $x^{jd_i}$ 表示用面额为 $d_i$ 的硬币凑出金额 $jd_i$ 的一种方式。由于我们可以使用任意数量的每种硬币，这个级数是无限的。
因为这是一个几何级数，我们可以用公式将其简化为：
$G_{d_i}(x) = \frac{1}{1 - x^{d_i}}$ （r^n当趋向于无穷是为0，因为收敛）
- 总生成函数
为了找到凑出特定金额 $n$ 的所有不同方式的数量，我们需要考虑所有硬币面额的组合。这可以通过将所有单独的生成函数相乘来实现：
$G(x) = \prod_{i=1}^{k} G_{d_i}(x) = \prod_{i=1}^{k} \frac{1}{1 - x^{d_i}}$
总生成函数 $G(x)$ 的 $x^n$ 项的系数就是凑出金额 $n$ 的方式数量。
- 计算方法
要找到 $x^n$ 的系数，我们需要展开总生成函数 $G(x)$。对于简单的情况，比如少量的硬币面额和较小的金额，这可能可以手动完成。对于更复杂的情况，通常需要使用计算机代数系统。
- 示例
假设我们有面额为1和2的硬币，我们想要凑出金额4。对应的生成函数为：
$G(x) = \frac{1}{(1-x)(1-x^2)}$
两个基本的几何级数求和公式：
1. $\frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + \cdots$
2. $\frac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \cdots$
我们需要找到 $G(x)$ 展开式中 $x^4$ 的系数。通过计算或软件帮助，我们可以得到：
$G(x) = 1 + x + 2x^2 + 2x^3 + 3x^4 + \ldots$
因此，凑出金额4的方式数量为3。
（1）示例：斐波那契数列
假设我们有斐波那契数列的递归式：
$F(n) = F(n-1) + F(n-2), \quad \text{对于 } n \geq 2$
并且给定初始条件：
$F(0) = 0, \quad F(1) = 1$
我们的目标是找到 $F(n)$ 的闭合形式解。
（2）构建生成函数
首先，定义斐波那契数列的生成函数 $G(x)$：
$G(x) = F(0) + F(1)x + F(2)x^2 + F(3)x^3 + \cdots = \sum_{n=0}^{\infty} F(n)x^n$
（3）应用递归关系
使用斐波那契数列的递归关系，我们可以将 $G(x)$ 写成：
$G(x) = F(0) + F(1)x + \sum_{n=2}^{\infty} (F(n-1) + F(n-2))x^n$
分离出 $F(0)$ 和 $F(1)x$，并将剩余部分按照 $F(n-1)$ 和 $F(n-2)$ 分开：
$G(x) = 0 + x + \sum_{n=2}^{\infty} F(n-1)x^n + \sum_{n=2}^{\infty} F(n-2)x^n$
（4）重写生成函数
注意到上述两个无穷级数实际上是 $G(x)$ 的变形，我们可以将它们写成 $G(x)$ 的表达式：
$G(x) = x + xG(x) + x^2G(x)$
简化得到：
$G(x) = \frac{x}{1 - x - x^2}$
（5）求解生成函数
现在，我们得到了斐波那契数列的生成函数 $G(x)$。要找到 $F(n)$ 的闭合形式，我们需要对 $G(x)$ 进行分解。$G(x)$ 可以通过部分分式分解或其他方法来处理。对于斐波那契数列，$G(x)$ 的分解可能涉及到黄金分割比 $\phi = \frac{1 + \sqrt{5}}{2}$ 和 $\psi = \frac{1 - \sqrt{5}}{2}$。
我们注意到生成函数 $G(x)$ 的分母可以被分解为：
$1 - x - x^2 = 0$
的解是：
$\phi = \frac{1 + \sqrt{5}}{2}, \quad \psi = \frac{1 - \sqrt{5}}{2}$
这两个解是著名的黄金比率及其共轭。因此，我们可以将 $G(x)$ 重写为分部分式的形式：
$G(x) = \frac{x}{(1 - \phi x)(1 - \psi x)}$
（6）提取系数
为了找到序列 $F(n)$ 的通项，我们需要从 $G(x)$ 中提取出 $x^n$ 的系数。通过部分分式分解，我们可以将 $G(x)$ 写为两个简单分式的和：
$G(x) = \frac{A}{1 - \phi x} + \frac{B}{1 - \psi x}$
其中，$A$ 和 $B$ 是需要确定的常数。注意到：
$\frac{1}{1 - \phi x} = 1 + \phi x + \phi^2 x^2 + \cdots = \sum_{n=0}^{\infty} \phi^n x^n$
$\frac{1}{1 - \psi x} = 1 + \psi x + \psi^2 x^2 + \cdots = \sum_{n=0}^{\infty} \psi^n x^n$
通过分解 $G(x)$，我们可以找到 $F(n)$ 的闭合形式，通常是 $F(n) = A\phi^n + B\psi^n$，其中 $A$ 和 $B$ 是根据初始条件确定的常数。
特征的生成函数（Moment Generating Function, MGF）是概率论和统计学中一个重要的概念，用于研究随机变量的分布特性。特征的生成函数可以提供随机变量所有矩（包括期望值、方差等）的信息，是分析随机变量特性的强大工具。
（1）定义
对于随机变量 $X$，其特征的生成函数 $M_X(t)$ 定义为：
$M_X(t) = E[e^{tX}]$
其中，$E[\cdot]$ 表示期望值，$t$ 是实数。
（2）性质
- 存在性。对于所有实数 $t$，如果 $E[e^{tX}]$ 存在，则 $M_X(t)$ 存在。
- 唯一性。如果两个随机变量的特征生成函数相等（在它们共同定义的区间内），那么这两个随机变量具有相同的分布。
- 可加性。如果 $X$ 和 $Y$ 是独立的随机变量，那么它们之和 $X+Y$ 的特征生成函数是它们各自特征生成函数的乘积，即 $M_{X+Y}(t) = M_X(t)M_Y(t)$。
- 矩的生成。$X$ 的第 $n$ 阶原点矩（如果存在）可以通过对 $M_X(t)$ 求 $t$ 的 $n$ 阶导数并在 $t=0$ 处求值得到：
$E[X^n] = M_X^{(n)}(0)$
在数学和信号处理领域，卷积是一种重要的运算，它描述了两个函数（信号、序列等）的组合方式。当涉及到生成函数时，卷积的概念可以用来分析和计算两个序列的组合（通常是乘积）的结果。这在组合数学、概率论以及许多其他数学领域中非常有用。
给定两个实数或复数序列 $\{a_n\}$ 和 $\{b_n\}$，它们的卷积是一个新的序列 $\{c_n\}$，定义为：
$c_n = \sum_{k=0}^{n} a_k b_{n-k}$
在连续函数的情况下，如果有两个函数 $f(t)$ 和 $g(t)$，它们的卷积定义为：
$(f * g)(t) = \int_{-\infty}^{\infty} f(\tau)g(t-\tau) d\tau$
（1）定义
对于给定的序列 $\{a_n\}_{n=0}^{\infty}$，其指数生成函数定义为：
$A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$
这里，$x$ 是一个形式变量，$n!$ 表示 $n$ 的阶乘。
（2）性质
- 加法。如果两个序列 $\{a_n\}$ 和 $\{b_n\}$ 的指数生成函数分别是 $A(x)$ 和 $B(x)$，那么序列 $\{a_n + b_n\}$ 的指数生成函数是 $A(x) + B(x)$。
- 乘法。如果想计算两个序列的点积或Hadamard积 $\{a_n b_n\}$ 的指数生成函数，那么结果是 $A(x) \cdot B(x)$。每个元素 $d_n = a_n \cdot b_n$
- 导数。序列 $\{a_n\}$ 的指数生成函数 $A(x)$ 的导数 $A'(x)$ 是序列 $\{na_{n}\}$ 的指数生成函数。
- 卷积。两个序列的卷积 $\{c_n\}$，其中 $c_n = \sum_{k=0}^{n} a_k b_{n-k}$，的指数生成函数是 $A(x)B(x)$。卷积是一个新序列 $\{c_n\}$，其中每个元素 $c_n = \sum_{k=0}^{n} a_k b_{n-k}$
（1）定义
给定一个数论函数 $f(n)$，其狄利克雷生成函数 $D(s)$ 定义为无穷级数：
$D(s) = \sum_{n=1}^{\infty} \frac{f(n)}{n^s}$
其中，$s$ 是一个复数，通常情况下我们关注的是 $s$ 的实部大于某个界限的情况，以确保级数收敛。
（2）性质
- 乘法性。如果两个算术函数 $f$ 和 $g$ 是乘性的，那么它们的狄利克雷生成函数的乘积与这两个函数的狄利克雷卷积的生成函数相等。这意味着，如果 $f * g = h$，则 $D_f(s)D_g(s) = D_h(s)$。
- 解析延拓。某些狄利克雷生成函数可以在其最初定义的收敛域之外进行解析延拓。黎曼ζ函数就是一个著名的例子，它可以延拓到复平面上，除了 $s=1$ 处的一个简单极点外。
（3）例子
- 黎曼ζ函数。
最著名的狄利克雷生成函数之一是黎曼ζ函数，对应的数论函数 $f(n) = 1$ 对所有的 $n$，所以它的狄利克雷生成函数是：
$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$
黎曼ζ函数在理解素数分布中起着核心作用。
- 除数函数。
除数函数 $d(n)$ 表示 $n$ 的正除数的个数，其狄利克雷生成函数是：
$D(s) = \sum_{n=1}^{\infty} \frac{d(n)}{n^s}$
八、离散概率
离散概率是概率论的一个分支，它处理的是离散随机变量的概率问题。离散随机变量是指那些取值在一个可数集合中的随机变量，例如投掷硬币的结果、掷骰子的点数、计数型数据等。离散概率的核心是概率质量函数（Probability Mass Function, PMF），它给出了随机变量取每个可能值的概率。
（1）概率质量函数
对于离散随机变量 $X$，其概率质量函数 $P(X=x)$ 给出了 $X$ 取特定值 $x$ 的概率。PMF 满足以下条件：
- $0 \leq P(X=x) \leq 1$ 对所有 $x$ 成立。
- $\sum_{\text{所有 }x} P(X=x) = 1$，即所有可能值的概率之和为1。
（2）伯努利试验
伯努利试验是只有两种可能结果的单次随机试验，通常称为“成功”和“失败”。如果“成功”的概率是 $p$，则“失败”的概率是 $1-p$。伯努利随机变量的 PMF 是：
$P(X=x) = \begin{cases}
p & \text{如果 } x=1 \\
1-p & \text{如果 } x=0
\end{cases}$
（3）二项分布
二项分布是进行 $n$ 次独立的伯努利试验，并计算成功次数的分布。如果每次试验成功的概率为 $p$，则成功 $k$ 次的概率由 PMF 给出：
$P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}$
其中，$\binom{n}{k}$ 是组合数，表示从 $n$ 项中选择 $k$ 项的方式数。
（3）泊松分布
泊松分布是描述在固定时间或空间内发生某事件的次数的分布，它由参数 $\lambda$（事件的平均发生率）定义。泊松分布的 PMF 是：
$P(X=k) = \frac{\lambda^k e^{-\lambda}}{k!}$
泊松分布适用于描述稀有事件的计数，如一定时间内接到的电话数量。
（1）期望
随机变量 $X$ 的期望值是 $X$ 取值的加权平均，权重是每个值的概率。对于离散随机变量，期望值定义为：
$E[X] = \sum_{\text{所有 }x} x \cdot P(X=x)$
（2）方差
方差衡量随机变量取值的离散程度。对于离散随机变量，方差定义为：
$Var(X) = \sum_{\text{所有 }x} (x - E[X])^2 \cdot P(X=x)$
概率生成函数（Probability Generating Function，简称PGF）是一种用于分析离散随机变量分布的强大工具。对于给定的离散随机变量 $X$，其概率生成函数定义为：
$G_X(s) = E[s^X] = \sum_{x=0}^{\infty} P(X=x) \cdot s^x$
其中，$E[s^X]$ 表示 $s^X$ 的期望值，$P(X=x)$ 是随机变量 $X$ 取特定值 $x$ 的概率，而 $s$ 是一个实数或复数，通常在 $|s| \leq 1$ 内。
（1）性质
- 求和。如果 $X$ 是一个离散随机变量，那么 $G_X(1) = 1$。
- 期望值 。随机变量 $X$ 的期望值 $E[X]$ 可以通过求导获得：$E[X] = G_X'(1)$。
- 方差。随机变量 $X$ 的方差 $Var(X)$ 可以通过 $G_X$ 的一阶和二阶导数计算：$Var(X) = G_X''(1) + G_X'(1) - (G_X'(1))^2$。
- 随机变量的和。如果 $X$ 和 $Y$ 是两个独立的离散随机变量，它们的和 $Z = X + Y$ 的概率生成函数为 $G_Z(s) = G_X(s) \cdot G_Y(s)$。
（1）散列函数
- 均匀性。每个可能的散列值都有相同的概率被选中。
- 随机性。散列函数应该使得任何输入数据映射到散列表的任何位置上都是随机的。
（2）冲突概率
- 生日问题。这个问题可以用来估计在给定数量的键值和散列表大小下，至少发生一次冲突的概率。
- 鸽巢原理。这个原理说明，如果有更多的键值要映射到散列表中，而散列表的大小是固定的，那么必然会发生冲突。
（3）处理冲突的方法
- 开放寻址法。在这种方法中，当发生冲突时，会寻找下一个空闲的散列位置。离散概率可以用来计算找到空闲位置所需的平均尝试次数。
- 链表法。在这种方法中，每个散列位置存储一个链表，所有映射到该位置的键值都会被添加到链表中。离散概率可以用来估计链表的平均长度，从而分析查找、插入和删除操作的平均时间复杂度。
九、渐进式
（1）大O符号（Big O Notation）- $O(f(n))$
如果存在正常数 $c$ 和 $n_0$，使得当 $n \geq n_0$ 时，$T(n) \leq c \cdot f(n)$，则我们说 $T(n) = O(f(n))$。
表示函数的上界，用于描述算法的最坏情况性能。
（2）大Ω符号（Big Omega Notation）- $\Omega(f(n))$
如果存在正常数 $c$ 和 $n_0$，使得当 $n \geq n_0$ 时，$T(n) \geq c \cdot f(n)$，则我们说 $T(n) = \Omega(f(n))$。
表示函数的下界，用于描述算法的最好情况性能。
（3）大Θ符号（Big Theta Notation）- $\Theta(f(n))$
如果 $T(n) = O(f(n))$ 并且 $T(n) = \Omega(f(n))$，则我们说 $T(n) = \Theta(f(n))$。
表示函数的确切增长率，用于描述算法在平均情况下的性能。
（4）小o符号（Little o Notation）- $o(f(n))$
如果对于任意正常数 $c > 0$，存在正常数 $n_0$，使得当 $n \geq n_0$ 时，$T(n) < c \cdot f(n)$，则我们说 $T(n) = o(f(n))$。
表示函数增长率严格小于 $f(n)$ 的增长率，用于描述算法性能的非紧确上界。
（5）小ω符号（Little omega Notation）- $\omega(f(n))$
如果对于任意正常数 $c > 0$，存在正常数 $n_0$，使得当 $n \geq n_0$ 时，$T(n) > c \cdot f(n)$，则我们说 $T(n) = \omega(f(n))$。
表示函数增长率严格大于 $f(n)$ 的增长率，用于描述算法性能的非紧确下界。
（1）常数规则
如果 $f(n) = O(g(n))$，那么对于任何常数 $c$，$cf(n) = O(g(n))$。这意味着当评估算法的复杂度时，可以忽略常数因子。
（2）加法规则
如果 $f(n) = O(h(n))$ 且 $g(n) = O(k(n))$，那么 $f(n) + g(n) = O(\max(h(n), k(n)))$。当算法由多个部分组成时，整体复杂度由最大的那部分决定。
（3）乘法规则
如果 $f(n) = O(h(n))$ 且 $g(n) = O(k(n))$，那么 $f(n) \cdot g(n) = O(h(n) \cdot k(n))$。这意味着两个算法复杂度的乘积等于各自复杂度乘积的大O表示。
（4）多项式规则
如果 $f(n)$ 是一个 $k$ 次多项式，那么 $f(n) = O(n^k)$。在大O表示中，只保留最高次项，并忽略最高次项的系数。
（5）对数规则
对数运算的底数在大O表示中是可以忽略的。例如，无论底数是多少，$O(\log_2 n)$ 和 $O(\log_{10} n)$ 都可以简写为 $O(\log n)$。
（6）指数规则
如果有一个函数的增长率远超过另一个函数，比如指数函数和多项式函数，那么只保留增长率更高的那个。例如，如果 $f(n) = 2^n + n^3$，那么 $f(n) = O(2^n)$。
（1）主定理
如果我们有一个递归式如下：
$T(n) = aT\left(\frac{n}{b}\right) + f(n)$
其中，$a \geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个给定的函数，那么主定理能够帮助我们确定 $T(n)$ 的渐近行为。主定理分为三种情况：
- **情况1**：如果 $f(n) = O(n^{\log_b a - \epsilon})$ 对于某个常数 $\epsilon > 0$，那么 $T(n) = \Theta(n^{\log_b a})$。（分治占主导）
- **情况2**：如果 $f(n) = \Theta(n^{\log_b a})$，那么 $T(n) = \Theta(n^{\log_b a} \log n)$。（均衡）
- **情况3**：如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 对于某个常数 $\epsilon > 0$，并且对于某个常数 $c < 1$ 和所有足够大的 $n$，满足 $af\left(\frac{n}{b}\right) \leq cf(n)$，那么 $T(n) = \Theta(f(n))$。（处理子问题占主导）
**递归的深度**：在分治算法中，每次递归都会将问题分解成更小的子问题。如果每次将问题规模缩小为原来的 $1/b$，那么递归的深度大约是 $\log_b n$。
**每层的工作量**：在每一层递归中，由于问题被分解成了 $a$ 个子问题，如果我们假设每层递归的工作量相同，那么随着递归深度的增加，总工作量会随着 $a$ 的幂次增长。
**综合考虑**：因此，当我们看到 $n^{\log_b a}$，可以将其理解为：在分治算法中，随着问题规模 $n$ 的增大，算法的时间复杂度会按照 $n$ 的某个幂次增长，这个幂次是由子问题数量 $a$ 和问题规模缩小比例 $b$ 共同决定的。
（2）渐近等价
两个函数 $f(n)$ 和 $g(n)$ 被认为是渐近等价的，如果它们的比值在 $n$ 趋于无穷大时趋向于1，即：
$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$
渐近等价是一种强大的技巧，用来简化复杂度分析中的表达式。它允许我们将复杂的函数替换为更简单的函数，只要这两个函数在 $n$ 趋于无穷大时具有相同的增长率。例如，对于大 $n$，$n^2 + n$ 与 $n^2$ 渐近等价，因为：
$\lim_{n \to \infty} \frac{n^2 + n}{n^2} = 1$
欧拉求和公式是数学中用于估计级数求和的一种方法，特别是当涉及到求和项为无穷多时。这个公式可以用来近似计算级数的和，同时提供一个误差估计。它是分析数论中的一个重要工具，尤其在估计素数定理的证明中发挥了关键作用。
（1）基本形式
欧拉求和公式将一个函数在整数点上的求和转换为该函数的积分，加上一系列修正项。其基本形式如下：
$ \sum_{n=a}^{b} f(n) = \int_{a}^{b} f(x) \, dx + \frac{f(a) + f(b)}{2} + \int_{a}^{b} P_1(x) f'(x) \, dx $
其中，$P_1(x) = x - \lfloor x \rfloor - \frac{1}{2}$ 是第一类 Bernoulli 多项式，$\lfloor x \rfloor$ 表示 $x$ 的下取整函数。
（2）更一般的形式
欧拉-麦克劳林求和公式是欧拉求和公式的一个扩展，它提供了更高阶的修正项，可以用来得到更精确的近似。其形式如下：
$ \sum_{n=a}^{b} f(n) = \int_{a}^{b} f(x) \, dx + \frac{f(a) + f(b)}{2} + \sum_{k=1}^{m} \frac{B_{2k}}{(2k)!} \left( f^{(2k-1)}(b) - f^{(2k-1)}(a) \right) + R_m $
这里，$B_{2k}$ 是第 $2k$ 项 Bernoulli 数，$f^{(2k-1)}$ 表示 $f$ 的 $2k-1$ 阶导数，$R_m$ 是余项，表示误差估计。