组合数学 – 期末复习

Partition Number

$$\begin{gather*} P(n):=\#\{(x_1,x_2,\dots,x_{m})|n=x_1+x_2+\cdots+x_m,x_1\ge x_2\ge\cdots\ge x_m\ge 1,m\in\mathbb{N}\}\\ P(n,m):=\#\{(x_1,x_2,\dots,x_{m})|n=x_1+x_2+\cdots+x_m,x_1\ge x_2\ge\cdots\ge x_m\ge 1\}\\ P(n)=P(n-1)+\sum_{m=1}^{\lfloor\frac{n}{2}\rfloor}P(n-m,m)\\ P(x):=\sum_{n\ge 0}P(n)x^n=\prod_{k\ge 1}\frac{1}{1-x^k}\\ P_{odd}(n)=\prod_{odd\ k\ge1}\frac{1}{1-x^k}=\prod_{k\ge 1}\frac{1-x^{2k}}{1-x^k}=\prod_{k\ge1}(1+x^k)=P_{diff}(n)\\ P(n)\sim e^{C\sqrt{n}} \end{gather*}$$

素数分布

Bertrand-Chebyshev 定理

$$[n,2n]间存在素数$$
证明思路：
$$\begin{gather*} \alpha_p(n):=\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\lfloor\frac{n}{p^3}\rfloor+\cdots\\ \binom{2n}{n}=\frac{(2n)!}{n!n!}=\prod_{prime\ p\le 2n}p^{\alpha_p(2n)-2\alpha_p(n)}\\ \prod_{prime\ p\le n}p^{\alpha_p(2n)-2\alpha_p(n)}\le 2^{\sqrt{2}\log_2{2n}}\cdot2^{\frac{4}{3}n}\cdot 1\Rightarrow\prod_{prime\ p\in(n,2n]}p^{\alpha_p(2n)-2\alpha_p(n)}>1 \end{gather*}$$

素数定理

$$\pi(n)\sim\frac{n}{\log_2{n}}$$

4k+3型素数有无穷多个

二次剩余

$$\begin{gather*} p\ prime,\ \left(\frac{a}{p}\right):=\left\{\begin{aligned}0\quad& p|a\\1\quad& a\equiv b^2,\ b\not\equiv0\pmod{p}\\-1\quad& otherwise\end{aligned}\right. \end{gather*}$$

$\underline{Thm}\ (Euler)$

$$\begin{gather*} p\nmid a，则\left(\frac{a}{p}\right)=(a^{\frac{p-1}{2}}\mod{p}) \end{gather*}$$
$$\begin{gather*} \left(\frac{-1}{p}\right)=\left\{\begin{aligned}1\quad& p为4k+1型\\-1\quad& p为4k+3型\end{aligned}\right.\\ \left(\frac{2}{p}\right)=\left\{\begin{aligned}1\quad& p为8k\pm1型\\-1\quad& p为8k\pm3型\end{aligned}\right. \end{gather*}$$

4k+1型素数有无穷多个

二次互反律

$$\begin{gather*} p,q\ odd\ prime，则\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^\frac{(p-1)(q-1)}{4} \end{gather*}$$

抽屉原理

4k+1型素数为平方和

证明：
$$\begin{gather*} \left(\frac{-1}{p}\right)=1\Rightarrow\exists s\in\{1,2,\dots,{p-1}\},\quad s^2\equiv -1\pmod{p}\\ T:=\{a+bs|0\le a,b\le\lfloor\sqrt{p}\rfloor\}\\ |T|=(1+\lfloor\sqrt{p}\rfloor)^2>p\\ \exists a_1,b_1,a_2,b_2,\quad (a_1,b_1)\not \equiv(a_2,b_2)\wedge a_1+sb_1\equiv a_2+sb_2\\ a_1-a_2\equiv s(b_1-b_2)\\ (a_1-a_2)^2+(b_1-b_2)^2\equiv 0\\ p|(a_1-a_2)^2+(b_1-b_2)^2\le 2\lfloor\sqrt{p}\rfloor^2<2p\\ \Rightarrow (a_1-a_2)^2+(b_1-b_2)^2=p \end{gather*}$$

d-染色二维整点一定存在四顶点同色矩形

Ramsey Theory

$$R(n_1,n_2,\cdots,n_r)<\infty$$
证明：
$$\begin{align*} R(n_1,n_2,\dots,n_{r})-1\le& R(n_1,n_2,\dots,n_{r})-1 \\&+R(n_1,n_2-1,\dots,n_{r})-1\\ &+\cdots+R(n_1,n_2,\dots,n_{r}-1)-1\\ &+1 \end{align*}$$
$$\begin{gather*} R(3,3)=6\\ R(3,4)=9 \end{gather*}$$

Schur Theorem

$$\exists N(d),\quad 对\{1,2,\dots,{N(d)}\}\ d-染色,\quad\exists 同色x,y,z,\quad x+y=z$$
证明思路：
$$按|i-j|的染色为v_iv_j边染色，利用拉姆塞理论得到同色三角形$$

Van der Waerden Theorem

$$\exists W(d,l),\quad 对\{1,2,\dots,{W(d,l)}\}\ d-染色,\quad\exists 同色l-AP(l-长等差数列)$$
证明关键：
$$block思想\\几色即几维（d）\\几点即几层（l）$$

平面整点2-染色一定存在顶点同色等腰直角三角形

平面点2-染色一定存在与给定30度角直角三角形全等的顶点同色三角形

平面整点2-染色一定存在顶点同色的正方形