同等学力申硕计算机专业--数学公式集合（新增学习笔记）

作者: 旋风竹影 | 来源:发表于2020-03-22 21:22 被阅读0次

组合数学部分：

基础公式：

定义:从n个不同的元素中, 取r个并按次序排列, 称为从n中取r个的一个排列, 全部这样的排列数记为P(n, r).

$P(n,r)=n(n-1)(n-2)...(n-r+1)=\frac{n!}{ (n-r)!}$

定义: 从n个不同的元素中, 取r个但是不考虑次序时候, 称为从n中取r个的一个组合, 全部这样的组合总数记为C(n, r).

$C(n,r)=\frac{P(n,r)}{r!} =\frac{n!}{(n-r)!r !}$

定义: 从n个不同的元素中, 取r个沿一圆周排列, 称为从n中取r个的一个圆周排列, 全部这样的排列数记为Q(n, r).

$Q{(n,r)}=\frac{P(n,r)}{r}$ $Q(n,n)=(n-1)!$

牛顿二项式公式：

$（1+x）^n = \sum_{k=0}^∞C_{n}^kx^k$

$（1+ax）^n = \sum_{k=0}^∞C_{n}^ka^kx^k$

推广牛顿二项式公式:

$（1+x）^{-n} = \sum_{k=0}^∞C_{-n}^kx^k$ $C_{-n}^k ={(-1)}^kC_{n+k-1}^k$

${(1+x)}^{-n} = \sum_{k=0}^∞{(-1)}^kC_{n+k-1}^kx^k$

${(1-x)}^{-n} = \sum_{k=0}^∞C_{n+k-1}^kx^k , -1<x<1$

常用公式：

$（1-x）^{\frac{1}{2} } = 1-{\frac{1}{2} }x-{\frac{1}{8} }x^2-{\frac{1}{16} }x^3-{\frac{1}{128} }x^4-...-{\frac{(2k-3)!!}{(2k)!!} }x^k-..., -1\leq x\leq 1$

第二类Stirling数 $S(n,k)$ 有以下性质(用于等价关系划分个数计算)：

$S(n,1) = S(n,n) =1$ ;

$S(n,2)=2^{n-1}-1$ ;

$S(n,n-1)=C(n,2)$ ;

$S(n,k)=kS(n-1,k)+S(n-1,k-1)$ .

多重集合的一个r组合， $S=\{ ∞\cdot 1,∞\cdot 2, ...,∞\cdot k\}$ ，则这个序列个数等于S的r组合个数为 $C_{（r+k-1,r)}$ ,用一一对应的方法来做。

母函数与递归关系：

设多重集 $S=\{ ∞\cdot a_{1},∞\cdot a_{2}, ...,∞\cdot a_{k}\}$ , 则的 r-(可重)排列数是 $k^r$ .

定理：设 $S=\{ n_{1}\cdot a_{1}, n_{2}\cdot a_{2}, ..., n_{k}\cdot a_{k}\}$ ，且 $n=\sum_{i=1}^kn_{i}$ ,则S的排列数等于 $\frac{n!}{n_{1}!\cdot n_{2}!\cdot ...\cdot n_{k}!}$

定义: 利用给定序列 $a_{0},a_{1},a_{2} ,…$ 所构造的函数 $F(x)= a_{0} +a_{1}x+a_{2}x^2+…$

称为序列 $a_{0},a_{1},a_{2} ,…$ 的母函数

母函数的运算

设序列 $\{a_{i} \}$ 的母函数 $A(x)=\sum_{k=0}^i a_{k} x^k$ , $\{b_{i} \}$ 的母函数为 $B(x)=\sum_{k=0}^i b_{k} x^k$ . 运算定义如下:

(1) 相等:A(x)=B(x) <=> $\{a_{i} \}$ = $\{b_{i} \}$ <=> $a_{i}$ = $b_{i}$ , i=1,2,…

(2) 相加: A(x)+B(x)= $\sum_{k=0}^i( a_{k}+b_{k}) x^k$

(3) 相减: A(x)-B(x)= $\sum_{k=0}^i( a_{k}-b_{k}) x^k$

(4) 数乘: cA(x)= $\sum_{k=0}^ic a_{k} x^k$

(5) 相乘: A(x)B(x)= $\sum_{k=0}^ic_{k}x^k$ , 其中

$c_{0}$ = $a_{0} b_{0}$ ,

$c_{1}$ = $a_{0} b_{1} +a_{1} b_{0}$

$c_{2}$ = $a_{0} b_{2} +a_{1} b_{1} +a_{2} b_{0} ,...............,$

$c_{r}$ = $a_{0} b_{r} +a_{1} b_{r-1} +...+a_{r} b_{0} ,...........$

(6) 逆: 如果A(x)B(x)=1, 则称B(x)为A(x)的逆, 记为B(x)= $A^{-1}(x)$ = $1/A(x)$ .

$\frac{1}{1-x} = 1 + x + x^2 + x^3 +...$

一元二次方程的根的通解： $x = \frac{ -b\pm \sqrt{b^2-4ac} }{ 2a }$

常系数齐次递归关系：

$H_{n}- a_{1}H_{n-1}- a_{2}H_{n-2}-...- a_{r}H_{n-r} = 0$

如 $a_{r}\neq 0$ ，则递归关系上式为一元 $r$ 次方程，即 $r$ 次特征方程如下：

$x^r- a_{1}x^{r-1}- a_{2}x^{r-2}-...- a_{r-1}x-a_{r} = 0$

设 $q_{i}$ （i=1,2,...）为特征方程的根，则有：

如果 $q_{i}$ 为不同实数根则 $H_{n}$ 的一般解如下：

$H_{n}=c_{1}q_{1}^n + c_{2}q_{2}^n +...+c_{r}q_{r}^n$

如果 $q_{i}$ 为i个重复特征根则 $H_{n}$ 的一般解如下：

$H_{n}=（c_{1} + c_{2}n + c_{3}n^2 ...+c_{{e_{i}}}n^{e_{i}-1}）q_{i}^n$

当特征方程为二次方程， $q_{1}$ 和 $q_{2}$ 是特征方程的，当 $q_{1} \neq q_{2}$ 时， $H_{n}=b_{1}q_{1}^n+b_{2}q_{2}^n$ ，当 $q_{1}=q_{2}=q$ （重根），则 $H_{n}=(b_{1}+b_{2}n)q^n$ 。

仅有两个复特征根：

当特征根为复数时，则有任意复数 $a+bi$ 都可以写成 $ce^{id}$ ,故可设两个复数特征根如下：

$\alpha _{1} = \delta + i\omega = \rho e^{i\theta } = \rho (\cos \theta + i\sin \theta )$

$\alpha _{1} = \delta - i\omega = \rho e^{-i\theta } = \rho (\cos \theta - i\sin \theta )$

其中 $\rho = \sqrt{\delta ^2 + \omega ^2}$

图论：

欧拉公式： $R+V-E =2, R\geq 2$ ，R为区域，V为顶点，E为边。

一个无向图 $G_{(V,E)}$ 是连通图，那么E的数目大于等于顶点的数目减1，即 $|E|\geq |V| -1$ 。

完全二部图的定义：设G=(V，E)为二分图，V=XUY，且X中的任一顶点与Y中每一个顶点均有且仅有唯一的一条边相连，则称G为完全二部图或完全偶图。

【定理一】图G是2-可着色的当且仅当G是二部图。

【定理二】奇圈和奇数阶轮图都是3-色图，而偶数阶轮图都是4-色图。

【定理三】树的着色数为2。

离散数学部分：

蕴含条件：

P是Q的充分条件时用： $P \rightarrow Q$

一般词汇：（如果P那么Q，只要P就Q，P就Q）

Q是P的必要条件时用： $Q \rightarrow P$

一般词汇：（只有P才Q，仅当P才Q，Q仅当P）

Q是P的充分且必要条件时用： $Q \leftrightarrow P$

一般词汇：（当且仅当，充分且必要）

等价公式：

$P \rightarrow Q \Leftrightarrow ┐P \lor Q$

$P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \land (Q \rightarrow P)$

$P \leftrightarrow Q \Leftrightarrow (┐P \leftrightarrow ┐Q)$

$P \leftrightarrow Q \Leftrightarrow (P \land Q) \lor (┐Q \land ┐P)$

推理定律：

$A \Rightarrow （A \lor B）$ （附加）

$（A \land B） \implies A$ （化简）

$((A \rightarrow B) \land A) \implies B$ （假言推理）

主析取范式： $A_{1} \lor A_{2} \lor A_{3} \lor ... \lor A_{n}$ 其中 $A_{i}$ 是包含所有变元且该变元有且仅出现一次的合取式，称为小项。有n个变元，则有 $2^n$ 。

主合取范式： $A_{1} \land A_{2} \land A_{3} \land ... \land A_{n}$ 其中 $A_{i}$ 是包含所有变元且该变元有且仅出现一次的析取式，称为大项。有n个变元，则有 $2^n$ 。

集合论：

幂集定义： $P(A) = \{x | x \subseteq A \}$ 即全部子集。实例： $P(∅) = \{∅\}$ , $P(\{∅\}) = \{∅,\{∅\}\}$ ，计数：如果|A|=n，则|P(A)| = $2^n$

【定理】非空集合S关于它上面的任何等价关系R的商集具有下列特点：S/R ≠ ∅；若A∈S/R，则A ≠ ∅；若A，B∈S/R，A≠B，则A∩B = ∅.

【定义】设A为非空集合，若存在A的一个子集族 $A`$ 满足： $∅ \notin A ^ `；\cup A ^ ` = A；\forall x,y \in A ^ ` \land x\neq y \rightarrow x \cap y = ∅$ , 则称 $A`$ 是A的一个划分， $A`$ 中元素称为划分块。