组合数学
组合数
广义组合数
${n \choose m} = \frac{n^{\underline{m}}}{m!}$ $n$ 为实数，$m$ 为自然数
广义二项式定理
$(x+1)^\alpha = \sum\limits_{i\geq0} {\alpha \choose i}x^i$ $\alpha$ 为实数
单位根反演：
$[n \mid k]=\frac{1}{n}\sum {i=0}^{n-1} \omega {n}^{ik}$
$[k \mod n \equiv j ]=\frac{1}{n}\sum {i=0}^{n-1} \omega {n}^{i(k-j)}$
例：求 $\sum {n \choose 3i}$
范德蒙恒等式
${n+m\choose j} = \sum\limits_{0\leq i\leq j}{n\choose i} {m\choose j-i}$
整值多项式
给定一个多项式 $p(x)$，对于任意整数 $x$，$p(x)$ 为一个整数，那么称 $p(x)$ 为一个整值多项式
性质：
整值多项式 $p(x)$ 可以写成如下形式：
$p(x)=\sum\limits_{i\leq n} a_i{x\choose i}$ $a_i$ 为整数
推论:
给定一个 $n$ 次多项式 $p(x)$，若其在 $x = t,x = t+1,··· ,x = t+n,t \in Z$ 上值为整数，那么该多项式必定是整值多项式，反向亦成立
例： 已知 $p(0),p(1),…,p(n)$，求 $a_0,a_1,…,a_n$
组合数估算
$(\frac{n}{m})^m \leq {n \choose m} \leq (\frac{ne}{m})^m$
斯特林公式
$n! = \sqrt{2 \pi n} (\frac{n}{e})^n$
球盒问题
集合论
反链
sperner 定理
若 $\mathcal{F}$ 是一个反链，则 $max{ \mathcal{F}} = {n\choose \lceil \frac{n}{2}\rceil}$
相交集族
最大 K 相交集族 = ${n-1\choose k-1}$
圆排列映射
数列
例：快排复杂度分析
$P(n) = \frac{2}{n}\sum \limits_{i=1}^{n-1} P(i)+1$
$P(n)=\frac{n+1}{n}P(n-1)+2$
$P(n) = 2 \ln2$
特征方程法
已知 $afn=bf{n-1}+cf_{n-2}$
令 $x_1, x_2$ 为方程 $ax^2=bx+c$ 两根，则 $f_n = c_1x_1^n+c_2x_2^n$
$c_1, c_2$ 用待定系数法求出
例：用 $1 × 2 $ 的多米诺骨牌覆盖 $3 × n$ 的棋盘有多少种方法
生成函数
例：设 $h_n$表示由数字 $1, 2, 3$ 构造的 $n$ 位数的个数，其中 $1$ 的个数是奇数，$2$ 的个数是 $3$ 的倍数，求 $h_n$
卡特兰数
$cn =\sum{i=0}^{n-1} ci \cdot c{n-i-1}$
$C(x)= xC(x)^2+1$
$c_n = \frac{1}{n+1} {2n \choose n}$
例： $n$ 个数字在进栈之前，已经有 $m$ 个数在栈中，问输出序列的种数
例：一位数学家随身只携带了一元钱来到拉斯维加斯的赌场，并去玩最简单的掷硬币游戏。在游戏中，他每次只押一元钱，输与赢的概率相同均为 1/2 且每次只输或赢一元钱。无论他赢了多少钱他都会继续掷硬币而不离开，若钱数为零，则按照赌场规定他需要离开。在本题中我们假设赌场的钱是无穷多的。
(1) 最终的结局是赌场破产还是数学家输光了钱
(2) 这位数学家一共能在赌场待多久
容斥原理
$\varphi(n) = n \prod (1-\frac{1}{p_i})$
错排问题
$fn = (n-1)(f{n-1}+f_{n-2})$
$f_n \to \frac{n!}{e}$
100 囚徒问题
斯特林数
下降幂 上升幂 斯特林数关系
斯特林反演
分拆数
P(n,k) = Q (n, k)
Ferres 图
$2^{c_1 \sqrt{n}} \leq P(n) \leq 2^{c_2\sqrt{n}}$
鸽巢原理
n 个人 有两个人认识的人数相同
1～100 中取 51 个数 必有两个互素 \ 整除
1～20 中取 7 个数 S 必有两个子集的和相等
有 101 个不同数 一定存在长度为 11 的上升子序列或下降子序列
小明要备考英语四级，他给自己安排了一个学习计划，每天最少做一题，在80天的时间里要做完 120 道题，求证:一定有连续的若干天，小明在这些天里恰好做了39 道题
Erdös-Ginzburg-Ziv Theorem
对于任意素数 $p$ ，任意 $2p-1$ 个不同的数中，必有 $p$ 个数的和是 $p$ 的倍数
推论：
任意 $2x-1$ 个不同的数中，必有 $x$ 个数的和是 $x$ 的倍数
Ramsey 理论
Number
R(3,4)=9
R(n,m)<= R(n-1, m)+R(n, m-1)
(n-1)(m-1) +1 <= R(n,m) <= C(n+m-2, n-1)
$R(n,n) \geq {2^{n/2-1}n} / e$
舒尔定理
范德瓦尔登定理
图论
树
1.For a simple graph G of order n the following are equivalent:
(A) G is connected and acyclic;
(B) G is connected and has size n − 1;
(C) G is acyclic and has size n − 1;
(D) For every two vertices u and v, the graph G contains exactly one uv-path.
2.kruskal 算法
3.prufer 序列
二分图
1.A graph is bipartite if and only if it has no cycles of odd length.
2.Berge 定理 A matching M in a bipartite graph G is a maximum matching in G if and only if G has no M-augmenting path.
3.HALL 定理 Suppose G is a bipartite graph with bipartition {X, Y }. The graph G has a matching saturating X if and only if |N(S)| ≥ |S| for every subset S of X
4.Konig 定理 if G is a bipartite graph, then the maximum size of a matching in G equals the minimum size of a vertex cover in G.
欧拉路
A graph is Eulerian if and only if all its vertices have even degrees and all of its edges belong to a single component.
连通度
$\kappa(G) \leq \kappa’(G) \leq \delta(G)$
If G is simple and |G| ≥ 3, then the following are equivalent (and characterize simple 2-connected graphs):
(A) G is connected and has no cut-vertex;
(B) For every two vertices x and y of G, there are two internally-disjoint
xy-paths;
(C) For every two vertices x and y of G, there is a cycle through x and y.
(D) δ ≥ 1 and every pair of edges of G lies on a common cycle.
If x and y are non-adjacent distinct vertices of a graph G, then the minimum size of a vertex-cut separating x from y equals the maximum number of pairwise internally-disjoint xy-paths.
平面图
Edges in a plane graph form a cycle if and only if the edges in the dual graph form a bond.
The following are equivalent for a plane graph G:
(A) G is bipartite;
(B) every face of G has even length;
(C) G∗ is Eulerian.
If a connected non-empty plane graph has v vertices, e edges, and f faces, then v − e + f = 2
A graph is planar if and only if it has neither K5 nor K3,3 as a topological minor.
图染色
χ(G) ≥ |G|/α(G)
χ(G)≤∆(G)+1
If G is a connected simple graph other than a clique and an odd cycle, then χ(G) ≤ ∆(G)
Every loopless planar graph has a proper 5-coloring.
If G is bipartite, then χ′(G) = ∆(G)