Part1. 逻辑、集合、映射与计数

1.1 命题

命题：可以判断对错的叙述，形如若 \(p\) 则 \(q\)。

真值：若命题为真则为真，命题为假则为假。

逆命题：若 \(q\) 则 \(p\).

否命题：若 \(\neg p\) 则 \(\neg q\).

逆否命题：若 \(\neg q\) 则 \(\neg p\).

原命题和逆否命题真值相同，否命题和逆命题真值相同。

1.1.1 充分、必要、充要条件

命题若 \(p\) 则 \(q\)。

其中 \(p\) 为 \(q\) 的充分条件，\(q\) 为 \(p\) 的必要条件，\(p \Leftrightarrow q\) 为充要条件，即充分必要条件的合称。

【注意】："若 \(p\) 则 \(q\)" 不能与 "\(p \Rightarrow q\)" 混为一谈。

1.1.2 全称量词和存在量词

全称量词：意义为”所有，任意，每一个“，记为 \(\forall\).

存在量词：意义为”存在一个，至少有一个，某些“，记为 \(\exists\).

全称命题：结构为”对于 \(M\) 中任意一个 \(x\)，有 \(p(x)\) 成立“，简记为 \(\forall x \in M, p(x)\).

存在命题：结构为”存在 \(M\) 中的一个 \(x_0\)，使 \(p(x_0)\) 成立“，简记为 \(\exists x_0 \in M, p(x_0)\).

1.1.3 充分、必要条件的集合意义

若 \(p\) 以集合 \(A\) 的形式出现，若 \(q\) 以集合 \(B\) 的形式出现，即 \(A=\{x|p(x)\},B=\{x|q(x)\}\)，则充分，必要条件可叙述为：

1. 若 \(A\subseteq B\)，则 \(p\) 是 \(q\) 的充分条件；
2. 若 \(A \supseteq B\)，则 \(p\) 是 \(q\) 的必要条件；
3. 若 \(A = B\)，则 \(p\) 是 \(q\) 的充要条件；
4. 若 \(A \subsetneqq B\)，则 \(p\) 是 \(q\) 的充分不必要条件；
5. 若 \(A \supsetneqq B\)，则 \(p\) 是 \(q\) 的必要不充分条件；
6. 若 \(A \nsubseteq B\) 且 \(A \nsupseteq B\)，则 \(p\) 是 \(q\) 的既不充分也不必要条件；

1.2 集合

集合元素的三个特征：确定性，互异性，无序性。

元素与集合的关系：属于与不属于，记为 \(\in\)，\(\notin\).

集合与集合的关系：包含与不包含，记为 \(\subseteq\)，\(\nsubseteq\).

集合 \(A\) 大小表示为 \(|A|\).

通常用 \(\{\}\) 来框定集合，\(()\) 来框定 \(N\) 元组。

1.2.1 集合关系

1.2.2 集合的基本运算

集合的并集：\(A \cup B=\{x|x\in A \vee x\in B\}\).

集合的交集：\(A \cap B=\{x|x\in A \wedge x\in B\}\).

集合的补集：\(\complement_U A=\{x|x\in U \wedge x \notin A\}\).

三种集合运用的性质：

1. 并集的性质：\(A \cup\varnothing=A\)；\(A \cup A=A\)；\(A\cup B=B \cup A\)；\(A\cup B=A\Leftrightarrow B \subseteq A\).

2. 交集的性质：\(A \cap\varnothing=A\)；\(A \cap A=A\)；\(A\cap B=B \cap A\)；\(A\cap B=A\Leftrightarrow A \subseteq B\).

3. 补集的性质：\(A \cup(\complement_UA)=U\)；\(A \cap(\complement_UA)=\varnothing\)；\(\complement_U(\complement_UA)=A\)；\(\complement_U(A\cap B)=(\complement_UA) \cup(\complement_UB)\)；\(\complement_U(A\cup B)=(\complement_UA)\cap(\complement_UB)\).

集合的运算律

\(A \cup(B\cap C)=(A\cup B)\cap(A\cup C)\).

\(A \cap(B\cup C)=(A\cap B)\cup(A\cap C)\).

\(\complement_U(A\cap B)=\complement_UA\cup\complement_UB\).

\(\complement_U(A\cup B)=\complement_UA\cap\complement_UB\).

1.2.3 常见的数集记法

【注意】\(\mathbb{N}\) 为自然数集，包含 \(0\)，\(\mathbb{N}^*\) 为正整数集，不包含 \(0\)。

1.3 映射

对于非空集合 \(A,B\)。按照某种确定的对应关系 \(f\)，使对于集合 \(A\) 中的任意一个元素 \(x\)，在集合 \(B\) 中都有唯一确定的元素 \(f(x)\) 与之对应。则对应关系 \(f:A\to B\) 为从集合 \(A\) 到集合 \(B\) 的一个映射。

1. 映射的定义域，像集合

   在映射 \(f:A\to B\) 中，\(x\) 的取值范围 \(A\) 叫做映射的定义域；与 \(x\) 的值对应相等的 \(f(x)\) 值叫做 \(x\) 在映射 \(f\) 下的像，集合 \(f(A)=\{f(x)|x\in A\}\) 叫做映射的像集合。像集合 \(f(x)\) 是集合 \(B\) 的子集。

2. 若 \(f(A)=B\)，则映射 \(f\) 称为满射；若对于 \(A\) 中任意两个不同的元素 \(x_1 \not= x_2\)，均有 \(f(x_1) \not= f(x_2)\)，则映射 \(f\) 称为单射；如果映射 \(f\) 既是单射又是满射，则映射 \(f\) 称为 1-1 映射。（感性理解为二分图最大匹配后的结果即为 1-1 映射）。\(\exists f^{-1}:B\to A\)，使得 \(\forall x\in A\)，均有 \(f^{-1}(f(x))=x,\forall y=B\)，均有 \(f(f^{-1}(y))=y\).

1.4 组合数学与计数

记 \(A_n^m\) 表示从 \(n\) 个数中选出 \(m\) 个数排列的方案数。

推导：第一个位置有 \(n\) 个数可选，第二个位置有 \(n-1\) 个数可选 ，\(\dots\)，第 \(m\) 个位置有 \(n-m+1\) 个数可选。则方案数为：\(\prod\limits_{i=1}^{m}(n-i+1)\).

化简可得：

记 \(C_n^m\) 表示从 \(n\) 个数中选出 \(m\) 个数的方案数。

推导：就是将 \(A_n^m\) 的顺序忽略，即 \(\frac{A_n^m}{m!}\).

化简可得：

1.4.1 组合计数的相关性质：

1. \(C_n^k=C_n^{n-k}\)

   证明：在杨辉三角中，以 \(\frac{n}{2}\) 为中轴呈对称态，设杨辉三角中第 \(n\) 行的元素组成的数列为 \(d_k\)，即 \(d_n=d_{n-k}\)；综上，\(C_n^k=C_n^{n-k}\)

2. \(C_n^0+C_n^1+C_n^2+\dots+C_n^n=2^n\)

   证明：在杨辉三角中，第 \(n\) 行的元素和为 \(2^n\)

3. \(C_n^0+C_n^2+C_n^4+\dots=C_n^1+C_n^3+C_n^5+\dots\)

   证明：3在杨辉三角中，以 \(\frac{n}{2}\) 为中轴呈对称态。当 \(n\) 为偶数时，左右元素一一对应（1-1映射等价）。当 \(n\) 为奇数时，左右元素可交错映射（比如 \(n=5\) 时，杨辉三角中第 \(5\) 行的元素数列为 \(1~4~6~4~1\)，等价映射为 \(f(1)=4\)，\(f(1)=4\)，\(f(6)=6\)。且无论 \(n\) 的值为多少，总是可以找到一个等价映射，使得其成立，证明略）。

4. \(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\)

   证明：在杨辉三角中，第 \(n\) 行 \(k\) 列元素等于第 \(n-1\) 行 \(k\) 列元素加上第 \(n-1\) 行 \(k-1\) 列元素。

5. \(C_n^k=\frac{n}{k}C_{n-1}^{k-1}\)

   证明：\(C_n^k=\frac{n!}{k!(n-k)!}=\frac{n}{k}·\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n}{k}C_{n-1}^{k-1}\)

6. \(C_n^k=\frac{n-k+1}{k}C_{n}^{k-1}\)

   证明：\(C_n^k=\frac{n!}{k!(n-k)!}=\frac{n-k+1}{k}·\frac{n!}{(k-1)!(n-k+1)!}=\frac{n-k+1}{k}C_{n}^{k-1}\)

1.4.2 容斥原理

有 \(n\) 个集合 \(A_i\)，要计算 \(|\bigcup_{i=1}^n A_i|\) 的值。

首先看一种 \(n=3\) 的特殊情况：有三个集合 \(A,B,C\)。要计算 \(|A\cup B\cup C|\)，显然：

将此规律拓展，便得到了通解：

证明：考虑计算贡献，左式每个元素出现一次，右式每个元素出现：\(C_k^1-C_k^2+C_k^3-\dots+(-1)^{i-1} ·C_k^i+\dots+(-1)^{k-1}·C_k^k=1\)

1.4.3 错位排列

对于长度为 \(n\) 的排列 \(A\)，求所有 \(A_i \not= i\) 的排列个数。

设 \(D_n\) 为长度为 \(n\) 的错位排列个数。

容易得到容斥：

化简得：

可以发现 sigma 里面一坨很像泰勒系数，利用一些高科技手段，证得 \(D_n\approx\frac{n!}{e}\).（我不会证啊，不过结论合乎周礼）。记得四舍五入。

Part2. 数列

2.1 数列基础

2.1.1 等差数列

对于一个数列 \(a\)，\(\forall i(1\le i<n),d\in \mathbb{R}\)，满足 \(a_{i+1}-a_i=d\)，则数列 \(a\) 为等差数列。

\(a_1\) 为等差数列的首项，\(a_n\) 为等差数列的末项，\(d\) 为公差。

性质

\(a_n=a_1+(n-1)·d=dn+(a_1-d)\)

\(S_n=\frac{(a_1+a_n)n}{2}=na_1+\frac{n(n-1)}{2}d\)

所以，等差数列的每一项都与第一项与公差有关。

2.1.2 等比数列

对于一个数列 \(a\)，\(\forall i(1\le i<n),q\in \mathbb{R}\) 且 \(q \not= 0\)，满足 \(\frac{a_{i+1}}{a_i}=q\)，则数列 \(a\) 为等比数列。

\(a_1\) 为等比数列的首项，\(a_n\) 为等比数列的末项，\(q\) 为公比。

性质

\(a_n=a_1·q^{n-1}=\frac{a_1(1-q^n)}{1-q}\)

等比数列的每一项都与第一项与公比有关。

2.1.3 求和符号的性质

1. 重命名性质（任意更换下标字母不影响求和）；
2. 累加性质，即 \(\sum\limits_{i=1}^{n}a_i=\sum\limits_{i=1}^{m}a_i+\sum\limits_{i=m+1}^{n}a_i(m<n)\)
3. 线性性质，即 \(\sum a_i+b_i=\sum a_i+\sum b_i, \sum ka_i=k\sum a_i\)
4. 交换顺序性质，即 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^m a_{ij}=\sum\limits_{j=1}^m \sum\limits_{i=1}^n a_{ij}\)

2.2 裂项

裂项的意义：在处理冗杂凌乱的分数数列时，可以考虑将其裂项之后，整理成简单的分式进行运算。

说白了就是一种工具。

例如：\(\sum\limits_{i=1}^n\frac{1}{i(i+1)}\)

这样就整理成了一个一阶的分式，和 \(n\) 阶的分式相比，减去了不少计算量。

2.2.1 Abel恒等式

令 \(S_n=\sum\limits_{i=1}^na_i\)，则

2.3 递推转通项

若递推式形如 \(a_{n+1}=a_{n}+f(n)\)，可转为通项 \(a_{n+1}=a_1+\sum\limits_{i=1}^{n-1}f(i)\).

若递推式形如 \(a_{n+1}=a_{n}·f(n)\)，可转为通项 \(a_{n+1}=a_1\prod\limits_{i=1}^{n-1}f(i)\).

2.3.1 待定系数法

形式一

适用于解决形如 \(a_{n+1}=pa_n+q(p,q\in\mathbb{R})\) 形式的递推式转化。

待定系数为 \(p\) 的等比数列，即 \(a_{n+1}+x=p(a_n+x)\)，解得 \(x=\frac{q}{p-1}\)。

令 \(b_n=a_n+x\)，因为 \(b\) 是等比数列，所以 \(b_n=b_1·p^{n-1}\)

将 \(b\) 数列代回原式得 \(a_{n+1}+x=p(b_1·p^{n-1})\)

化简可得：\(a_{n+1}=(a_1+x)·p^{n}-x\)

将 \(x\) 代入上式得：\(a_{n+1}=(a_1+\frac{q}{p-1})·p^{n}-\frac{q}{p-1}\)

形式二

适用于解决形如 \(a_{n+2}=pa_{n+1}+qa_n(p,q\in\mathbb{R})\) 形式的递推式转化。

解除方程 \(x^2-px-q=0\) 的 \(x_1,x_2\).

若 \(x_1 \not= x_2\)，设 \(a_n=c_1x_1^n+c_2x_2^n\) 待定系数解出 \(c_1,c_2\)。

若 \(x_1=x_2\)，设 \(a_n=c_1x_1^n+c_2nx_1^n\) 待定系数解出 \(c1,c2\)。

带入可得通项公式。

2.3.2 换元法

适用于解决形如 \(a_{n+1}=pa_n+f(n)(p,f(n)\in\mathbb{R})\) 形式的递推式转化。

可以待定系数为 \(p\) 的等比数列，即 \(a_{n+1}+g(x+1)=p(a_n+g(n))\)，解出 \(g(n)\) 然后按照 2.3.1 的方法解即可。

还有另外一种做法，即将等式两边同时除以 \(p^{n+1}\)，转化为 \(\frac{a_{n+1}}{p^{n+1}}=\frac{a_{n}}{p^{n}}+\frac{f(n)}{p^{n+1}}\).

令 \(b_n=\frac{a_{n}}{p^{n}}\)，则原式为 \(b_{n+1}=b_n+\frac{f(n)}{p^{n+1}}\).

转化为：\(b_{n+1}=b_1+\sum\limits_{i=1}^{n-1}\frac{f(i)}{p^{i+1}}\).

然后将 \(b\) 转化为 \(a\) 数列即可。

Part3. 数学归纳法

3.1 第一数学归纳法

对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：

1. 证明 \(f(1)=1\)，即当 \(n=1\) 时，命题 \(f\) 成立；
2. 若 \(f(k)=1\)，证明 \(f(k+1)=1\)，即假设当 \(n=k\) 时，命题 \(f\) 成立；则需证明当 \(n=k+1\) 时，命题 \(f\) 成立；

当这两个条件同时满足时，则条件（命题）成立，反之不成立。

例题1

求证 \(1+3+5+\dots+(2n-1)=n^2\)

证明：当 \(n=1\) 时，\(1 = 1^2\)，所以 \(f(1)=1\)；

假设 \(n=k\) 时，\(f(k)=1\)，则当 \(n=k+1\) 时，原式为 \(1+3+5+\dots+(2k-1)+[2(k+1)-1]\)

化简可得 \(1+3+5+\dots+(2k-1)+2k+1\)

将 \(1+3+5+\dots+(2k-1)=k^2\) 代入上式得：

\(k^2+2k+1=(k+1)^2\)

所以当 \(n=k+1\) 时，\(f(k+1)=1\).

即命题 \(f\) 成立。

例题2

求证：\(\sum\limits_{i=1}^n\left \lfloor \frac{i}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor · \left \lfloor \frac{n+1}{2} \right \rfloor\)

证明：当 \(n=1\) 时，显然成立

假设 \(n=k\) 时，\(f(k)=1\)，则当 \(n=k+1\) 时，原式为 \(\sum\limits_{i=1}^{k+1}\left \lfloor \frac{i}{2} \right \rfloor = \left \lfloor \frac{k+1}{2} \right \rfloor · \left \lfloor \frac{k+2}{2} \right \rfloor\)

变形，代入得：

所以当 \(n=k+1\) 时，\(f(k+1)=1\).

即命题 \(f\) 成立。

3.2 第二数学归纳法

对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：

1. 证明 \(f(1)=1\)，即当 \(n=1\) 时，命题 \(f\) 成立；
2. 若 \(f(1,2,\dots,k)=1\)，证明 \(f(k+1)=1\)，即假设当 \(n=1,2,\dots,k\) 时，命题 \(f\) 成立；则需证明当 \(n=k+1\) 时，命题 \(f\) 成立；

当这两个条件同时满足时，则条件（命题）成立，反之不成立。

3.3 第三数学归纳法

对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：

1. 证明 \(f(2)=1\)，即当 \(n=2\) 时，命题 \(f\) 成立；
2. 设递增数列 \(A\)，若 \(f(A_k)=1\)，证明 \(f(A_{k+1})=1\)，即当 \(n=A_{k+1}\) 时，命题 \(f\) 成立；
3. 若 \(f(k)=1\)，证明 \(f(k-1)=1\)，即假设当 \(n=k\) 时，命题 \(f\) 成立；则需证明当 \(n=k-1\) 时，命题 \(f\) 成立；

当这三个条件同时满足时，则条件（命题）成立，反之不成立。

例题3

求证：对于任意正实数 \(x_1,x_2,\dots,x_n\)，均有 \(\frac{\sum\limits_{i=1}^{n}x_i}{n} \ge \sqrt[n]{x_1x_2\dots x_n}\)

证明：

当 \(n=2\) 时，原式成立，即 \(f(2)=1\).

当 \(n=2^k\) 时，两两一组合并，可得 \(f(2^{k})=1\).

假设 \(n=k\) 时，\(f(k)=1\)，则有：

故命题 \(f\) 成立。

Part4. 数论

4.1 整除

若 \(a\) 能整除 \(b\)，则 \(\exists n\in \mathbb{Z}\)，满足 \(an = b\)；记为 \(a | b\)

整除的性质

传递性：\(a|b,b|c\) 则 \(a|c\)；

可加减性：\(n|a,n|b\) 则 \(n|a\pm b\)

可乘性：\(a|b,c|d\) 则 \(ac|bd\)

4.2 最大公约数与最小公倍数

\(a,b\) 的最大公约数记为 \(\gcd(a,b)\)，\(\gcd(a,b)=\min\{x|(x|a)\wedge(x|b)\wedge(x>0)\}\)

\(a,b\) 的最小公倍数记为 \(\operatorname{lcm}(a,b)\)，\(\operatorname{lcm}(a,b)=\max\{x|(a|x)\wedge(b|x)\wedge(x>0)\}\)

带余除法

\(\forall a,b\in\mathbb{Z}^{+},\exists q,r\in\mathbb{Z}\)，使得：

带余除法满足存在性和唯一性，证明略。

Part5. 常用定理及函数

5.1 欧拉函数

记 \(\varphi(n)\) 表示小于 \(n\) 的正整数中与 \(n\) 互质的数的个数。

计算方法：将总数减去与 \(n\) 不互质的数的个数。将 \(n\) 质因数分解后，记 \(p_1,p_2,p_3,\dots,p_k\) 为 \(n\) 的质因子，则有：

因数分解可得：

计算欧拉函数的步骤中运用到了容斥原理，可见容斥原理的应用范围非常广。

欧拉函数的性质：

1. 若 \(\gcd(a,b)=1\)，则有 \(\varphi(a)·\varphi(b)=\varphi(ab)\)，即欧拉函数为积性函数。

   证明：

   设 \(A\) 为 \(a\) 的质因子集合，集合元素记为 \(p_1,p_2,p_3,\dots,p_k\)，\(B\) 为 \(b\) 的质因子集合，集合元素记为 \(P_1,P_2,P_3,\dots,P_m\)。

   \(\because\gcd(a,b)=1\)，\(\therefore A \cap B=\varnothing\).

   \(\because\varphi(a)=a(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k}),\varphi(b)=b(1-\frac{1}{P_1})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_m})\)

   \(\therefore \varphi(ab)=ab(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k})(1-\frac{1}{P_1})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_m})\)

   \(\therefore\varphi(a)·\varphi(b)=\varphi(ab)\)

2. 若 \(p\) 为质数，\(\varphi(p)=p-1\).

   证明：

   \(\because p\) 为质数，\(\therefore\) 小于 \(p\) 的正整数中与 \(p\) 互质的数的个数为 \(p-1\).

3. 若 \(p\) 为质数，\(\varphi(p)=p^k-p^{k-1}\).

   证明：

   \(\because p\) 为质数，\(\therefore\) 与 \(p\) 不互质的数只能为 \(p\) 的倍数，共有 \(p^{k-1}\) 个。

   \(\therefore\) \(\varphi(p)=p^k-p^{k-1}\).

5.2 卡特兰数

记 \(C_n\) 为变量为 \(n\) 的卡特兰数值。其递推式为：

通项公式为：

卡特兰数通常可以解决一下问题（是一下问题的解）：

1. 有 \(n\) 对括号匹配的序列数，解为 \(C_n\)；
2. \(A,B\) 双方打羽毛球，从 \(0:0\) 打到 \(n:n\)，\(A\) 从来没有落后过的方案数，解为 \(C_n\)；
3. 在一个 \(n\times n\) 的网格中，从 \((0,0)\) 处开始走，每次可以向上走一格或向右走一格，在任意时刻，向右走的次数不能少于向上走的的次数，求合法路径数，解为 \(C_n\)；
4. 一个圆周上有 \(2n\) 个点，两两配对并在两点间连一条弦，要求所连的 \(n\) 条弦没有交点，求配对数，解为 \(C_n\)；
5. 将 \(n\) 边的凸多边形以不相交的对角线分成 \(n−2\) 个三角形的方案数，解为 \(C_{n-2}\)。并可以转化为问题 \(4\)；
6. \(\sum\limits_{i=1}^{2n} a_i(a_i\in\{-1,1\})=0,\forall 1\le k\le 2n,\sum\limits_{i=1}^k a_i\ge 0\) 的方案数，解为 \(C_n\)；（此问题为问题 \(2,3\) 的母题）；
   卡特兰数的应用不止这些，遇到新问题应随机应变，转化为卡特兰数解。

5.3

Part6. 博弈论

对于一个无运气成分，无平局的游戏一定有必胜策略。

必败点：走到该点，采取最优策略一定失败；

制胜点：走到该点，采取最优策略一定胜利；

必胜策略推导：

1. 只能走到只制胜点的都是必败点；
2. 可以走到必败点的都是制胜点；

本栏目推荐文章
• [oeasy]python0004_游乐场_和python一起玩耍_python解释器_数学运算
• 在算法比赛中的常用数学库函数
• 数学基础(一)-标量、向量、矩阵、张量以及各范数的含义
• 数学家候选人
• 速通 离散数学(1)
• 具体数学第六章习题选做（genshining）
• 数学与通信
• 利用JavaScript函数进行数学计算和逻辑判断
• Github page数学公式无法正常显示解决方案(MathJax)
• 2023-2024清华附中一道初三数学新定义题的详细题解

数学 大礼包 大礼大礼包 大礼 数学day 数学 大礼包 大礼 大礼包 大礼 大礼包 大礼 大礼包 数量有限 大礼tdengine 大礼包 大礼 特权harmonyos 数学 数学题 数学分析