数学基础
2023年3月14日大约 8 分钟
数学基础
标准记号和常用函数
单调性
- 若 $m <= n$ 蕴涵 $f(m) <= f(n)$，则函数 $f(n)$ 是单调递增的。
- 若 $m <= n$ 蕴涵 $f(m) >= f(n)$，则函数 $f(n)$ 是单调递减的。
- 若 $m < n$ 蕴涵 $f(m) < f(n)$，则函数 $f(n)$ 是严格递增的。
- 若 $m < n$ 蕴涵 $f(m) > f(n)$，则函数 $f(n)$ 是严格递减的。
向下取整与向上取整
- 对任意实数 $x$
- 用 $\left \lfloor x \right \rfloor$ 表示小于或等于 $x$ 的最大整数（读作"x的向下取整＂）
- 用 $\left \lceil x \right \rceil$ 表示大于或等于 $x$ 的最小整数（读作"x的向上取整＂）
- 对所有实数 $x$
- $x—1 < \left \lfloor x \right \rfloor <= x <= \left \lceil x \right \rceil < x + 1$
- 对任意整数 $n$
- $\left \lfloor n/2 \right \rfloor + \left \lceil n/2 \right \rceil = n$
- 对任意实数 $x >= 0$ 和整数 $a，b > 0$
- $\left \lceil \frac{\left \lceil x/a \right \rceil}{b} \right \rceil = \left \lceil \frac{x}{ab} \right \rceil$
- $\left \lfloor \frac{\left \lfloor x/a \right \rfloor}{b} \right \rfloor = \left \lfloor \frac{x}{ab} \right \rfloor$
- $\left \lceil \frac{a}{b} \right \rceil <= \frac{a + (b - 1)}{b}$
- $\left \lfloor \frac{a}{b} \right \rfloor >= \frac{a + (b - 1)}{b}$
- 对任意实数 $x$
模运算
- 对任意整数 $a$ 和任意正整数 $n$，$a \bmod n$ 的值就是商 $a / n$ 的余数：
- $a \bmod n = a - n\left \lfloor a/n \right \rfloor$
- $0 <= a \bmod n < n$
- 余数：https://zh.wikipedia.org/zh-cn/%E4%BD%99%E6%95%B0
- 对任意整数 $a$ 和任意正整数 $n$，$a \bmod n$ 的值就是商 $a / n$ 的余数：
指数
- 对所有实数 $a > 0$ 、$m$ 和 $n$，我们有以下恒等式：
- $a^{0} = 1$
- $a^{1} = a$
- $a^{-1} = 1/a$
- $(a^{m})^{n} = a^{mn}$
- $(a^{m})^{n} = (a^{n})^{m}$
- $a^{m}a^{n} = a^{m+n}$
- 对所有实数 $a > 0$ 、$m$ 和 $n$，我们有以下恒等式：
- 使用下面的记号：
- $\lg_{}{n} = \log_{2}{n}$（以2为底的对数）
- $\ln_{}{n} = \log_{e}{n}$（自然对数）
- $\lg^{k}{}{n} = (\lg{}{n})^k$（取幕）
- $\lg\lg_{}{n} = \lg(\lg_{}{n})$（复合）
- 如果常量 $b > 1$，那么对 $n > 0$，函数 $\log_{b}{n}$ 是严格递增的。
- 对所有实数 $a > 0$，$b > 0$，$c > 0$ 和 $n$，对数的底不为1，有:
- $a = b^{\log_{b}{a}}$
- $\log_{c}{(ab)} = \log_{c}{a} + \log_{c}{b}$
- $\log_{b}{a^n} = n\log_{b}{a}$
- $\log_{b}{a} = \frac{\log_{c}{a}}{\log_{c}{b}}$
- $\log_{b}{(1/a)} = -\log_{b}{a}$
- $\log_{b}{a} = \frac{1}{\log_{a}{b}}$
- $a^{\log_{b}{c}} = c^{\log_{b}{a}}$
- 使用下面的记号：
阶乘
- 记号 $n!$ (读作"n的阶乘＂）定义为对整数 $n >= 0$，有
- $n! = \left{\begin{matrix} 1 & 若n = 0 \ n*(n-1)! & 若n > 0 \ \end{matrix}\right.$
- 因此，$n! = 1 * 2 * 3 ... n$
- 记号 $n!$ (读作"n的阶乘＂）定义为对整数 $n >= 0$，有
斐波那契数
- 使用下面的递归式来定义斐波那契数：
- $\begin{matrix} F_{0} = 0 \ F_{1} = 1 \ F_{1} = F_{i-1} + F_{i-2} & i >= 2 \ \end{matrix}$
- 每个斐波那契数都是两个前面的数之和，产生的序列为0，1，1，2，3，5，8，13，21，34，55，..
- 使用下面的递归式来定义斐波那契数：
求和
求和公式及其性质
定义
- 有限级数：
- 给定一个数列$a_{1}，a_{2}， ...， a_{n}$，其中$n$是非负整数，可以将有限和$a_{1} + a_{2} + ... + a_{n}$，写作
- $\sum_{k=1}^{n}(a_{k})$
- 若$n = 0$，则定义该和式的值为0。有限级数的值总是良定的，并且可以按任意顺序对级数中的项求和。
- 给定一个数列$a_{1}，a_{2}， ...， a_{n}$，其中$n$是非负整数，可以将有限和$a_{1} + a_{2} + ... + a_{n}$，写作
- 无限级数：
- 给定一个无限数列$a_{1}，a_{2}， ...$，可以将其无限和$a_{1} + a_{2} + ...$，写作
- $\sum_{∞}^{n}a_{k}$
- $\lim \limits_{n \rightarrow ∞} \sum_{∞}^{n}a_{k}$
- 当其极限不存在时，该级数发散；反之，该级数收敛。对于收敛级数，不能随意对其项改变求和顺序。而对于绝对收敛级数，则可以改变其项的求和顺序。
- 给定一个无限数列$a_{1}，a_{2}， ...$，可以将其无限和$a_{1} + a_{2} + ...$，写作
- 有限级数：
线性性质
- 对于任意实数$c$和任意有限序列$a_{1}，a_{2}， ...， a_{n}$和$b_{1}，b_{2}， ...， b_{n}$有
- $\sum_{k=1}^{n}(ca_{k} + b_{k}) = c\sum_{k=1}^{n}(a_{k}) + \sum_{k=1}^{n}(b_{k})$
- 对于任意实数$c$和任意有限序列$a_{1}，a_{2}， ...， a_{n}$和$b_{1}，b_{2}， ...， b_{n}$有
等差级数
- $\sum_{k=1}^{n}k = 1 + 2 + 3 + ... + n$
- $\sum_{k=1}^{n}k = \frac{1}{2} n (n + 1)$ = $\Theta(n^2)$
平方和与立方和
- $\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}$
- $\sum_{k=1}^{n}k^3 = \frac{n^2(n+1)^2}{4}$
几何级数
- 当实数$x != 1$，和式 $\sum_{k=0}^{n}x^k = 1 + x + x^2 + x^3 + x^n$
- $\sum_{k=0}^{n}x^k = \frac{x^{n+1}-1}{x-1}$
- 当和是无限的且$|x| < 1$时，有无限递减几何级数
- $\sum_{k=0}^{n}x^k = \frac{1}{1-x}$
- 当实数$x != 1$，和式 $\sum_{k=0}^{n}x^k = 1 + x + x^2 + x^3 + x^n$
调和级
- $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n} = \sum_{k=1}^{n}\frac{1}{k} = ln(n) + O(1)$
集合等离散数学内容
集合
$| A \cup B | = | A | + | B | - | A \cap B|$
计数与概率
计数
和与积的规则
- 和规则是指从两个不相交集合之一中选择一个元素的方法数等于这两个集合的基数和。
- 若$A$与$B$是两个无共同元素的有限集，那么$|A \cup B| = |A| + |B|$
- 车牌照上每个位置是字母或数字。因为字母有26种选择，数字有10种，所以每个位置上的可能选择有26+10=36种。
- 积规则是指选出一个有序对的方法数等于选出第一个元素的方法数与选出第二个元素的方法数的乘积。
- 如果A与B是两个有限集，则$|A X B| = |A| • |B|$
- 如果一个冰淇淋店提供28种口味的冰淇淋和4种顶料，则一勺冰淇淋与一种顶料构成的圣代的可能种类数是28•4=112。
- 和规则是指从两个不相交集合之一中选择一个元素的方法数等于这两个集合的基数和。
- 从$n$个相异元素中取出$k$个元素，$k$个元素的排列数量为：
- $P_{n}^{k}={\frac {n!}{(n-k)!}}$ = $n(n—1) (n-2)...(n—k+1)$
- 有限集S的一个排列是S中元素的一个有序序列，其中每个元素出现且仅出现一次。
- 例如，令$S={a,b,c}$, 则S有6种排列：$abc,acb,bac,bca,cab,cba$
- 包含$n$个元素的集合的排列数目为$n!$。这是因为序列第一个元素的选择有$n$种，第二个元素的选择有$n—1$种，第三个元素的选择有$n—2$种。
- $S$的一个$k$排列是$S$中$k$个元素的有序序列，且每个元素最多出现一次。（所以，通常的排列是$n$集合的一个$n$排列。）
- 集合${a,b, c,d}$的12个2排列是$ab ,ac ,ad ,ba ,be ,bd ,ca ,cb ,cd ,da ,db ,de$
- 对于$n$集合的$k$排列，其第一个元素有$n$种选择，第二个元素有$n-1$种选择，依此类推，直到选择出$k$个元素，最后被选中的元素是从剩余的$n—k+1$个元素中选出的。
- 从$n$个相异元素中取出$k$个元素，$k$个元素的排列数量为：
- 从$n$个不同元素中取出$k$个元素的所有不同组合的个数，叫做从$n$个不同元素中取出$k$个元素的组合数，记做: $C_{n}^{k}$
- 从$n$个元素中取出$k$个元素，$k$个元素的组合数量为: ${C_{n}^{k}={n \choose k}={\frac {n!}{(n-k)!k!}}}$
- 排列数量除以k的全排列种数（用于去重）
- 从$n$个元素中取出$k$个元素，$k$个元素的组合数量为: ${C_{n}^{k}={n \choose k}={\frac {n!}{(n-k)!k!}}}$
- $n$集合$S$的一个$k$组合是$S$的一个$k$子集。
- 例如，4集合${a,b, c, d}$有6个2组合：$ab ,ac ,ad ,be ,bd ,cd$
- 从$n$个不同元素中取出$k$个元素的所有不同组合的个数，叫做从$n$个不同元素中取出$k$个元素的组合数，记做: $C_{n}^{k}$
- 根据该定理，可以将两个数之和的整数次幂诸如$(x+y)^{n}$展开为类似${ax^{b}y^{c}}$项之和的恒等式，其中$b、c$均为非负整数且$b+c=n$。
- ${ax^{b}y^{c}}$中的系数$a$被称为二项式系数。
- 二项式系数是二项式定理中各项的系数。事实上，$\tbinom {n}{k}$可以被理解为从$n$个相异元素中取出$k$个元素的方法数，所以 $\tbinom nk$大多读作“n取k”。
- $(x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k$
概率
概率是一种描述不确定性的数学工具，用于衡量事件发生的可能性。在概率论中，事件是一些可能发生或不发生的事情，而概率则是表示这些事件发生的可能性大小的数字。概率的值通常在0到1之间，其中0表示事件不可能发生，1表示事件一定会发生。
概率的计算可以通过两种方式进行：经典概率和条件概率。
经典概率是一种用于计算简单事件发生概率的方法，假设每个事件是等可能发生的，那么该事件发生的概率就等于事件的数量除以样本空间的大小。
条件概率则是在已知某个事件发生的前提下，计算另一个事件发生的概率。它通常用于处理复杂事件，其中每个事件的概率可能会受到其他事件的影响。条件概率可以通过贝叶斯定理进行计算，贝叶斯定理是指在已知某个事件的条件下，计算另一个事件的概率。
概率的应用非常广泛，包括但不限于统计学、风险管理、金融学、计算机科学等。在计算机科学中，概率通常用于处理随机事件、随机算法、机器学习等问题，例如在自然语言处理中，贝叶斯分类器就是一种利用概率模型进行文本分类的方法。
矩阵
数学上，一个$m \times n$的矩阵是一个由$m$行（row）$n$列（column）元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。