考完就不看の离散数学笔记!

计数原理

问题背景:N个物体放到k个盒子中

  • 排列组合公式:

\[C_n^m = \frac{n!}{m!(n-m)!}\]

\[A_n^m = \frac{n!}{(n-m)!}=\prod_{i=n-m+1}^ni\]

\[A_n^n = n!\]

  • 广义鸽巢原理: 如果\(N\)个物体放置到\(k\)个盒子中,那么至少有一个盒子装有不少于\(⌈{N\over k}⌉\)个物体。
    • 朋友敌人问题:假定有一组6个人,任两人非友即敌。证明存在三个人 彼此是朋友或者存在三人彼此是敌人。
    • 解: 任选其中一人A出来,剩下的5个人中,分成两个子集,一 个是A的朋友的集合,另一个是A的敌人的集合。这两个集合至 少有一个多于两个人。至少有3个人要么是A朋友,要么是A的敌 人。如果三个人是A的朋友,那么如果这三个人之间有一对是朋 友,则已;否则这三个人本身就是彼此为敌人。
  • 组合恒等式

\[C_n^k = \frac{k}{n} C_{n-1}^{k-1}\]

\[Pascal: C_n^k = C^{k}_{n-1} + C_{n-1}^{k-1}\ \text{(杨辉三角中相邻两元素之和)}\]

  • 有重复排列\(n^k\)
  • 有重复组合:把\(N\)个相同的物体放到\(k\)个不同盒子中,有\(C_{k+n-1}^n\)中方法。相当于解不定方程:

\[\sum_{i=0}^n x_i = k, x_i\in [0, r]\]

  • 分组问题:把\(N\)个不同的物体放到\(k\)个相同盒子中:
    • \(2n\) 个人分成 \(n\) 组,每组\(2\)人,有多少分法?
    • 解: 相当于\(2n\) 不同的球放到 \(n\) 个相同的盒子,每个盒子\(2\)个。可以先考虑\(n\)个盒子是有标记有顺序的,分步处理:那么先选第一组\(2\)个,再选第\(2\)\(2\)个,如此类推,一共有\(C(2n,2)C(2n-2,2)...C(2,2)\). 这个数字包括了所有可能的组的排列方法。但实际上\(n\)个盒子作为\(n\)组本身是无序的,所以就应该将有序的分组数再除以\(n\)个组的有序排列数\(n!\),因此结果为:

\[\frac{1}{n!}C(2n,2)C(2n-2,2)...C(2,2)\]

  • 不相邻问题:从\(S={1, 2, ... , n}\)中选择 k 个不相邻的数,有多少种方法?
    • \(k\)个数不相邻,相当于他们是剩下的\(n-k\)个数的隔板,因此有\(c_{N-K+1}^K\)种办法。
  • 不可辨别对象排列:单词计数问题。把单词 SUCCESS 重新排列能得到多少不同的串?
    • 单词长度固定为7,想象有7个位置,首先放入三个S,有\(C_7^3\)种方法;再放入两个C,有\(C_4^2\)种,再放入U和E,有\(A_2^2\)种。乘起来即可。
    • \(n\)个对象中,有类型\(i\)的相同对象\(n_i\)个,共有\(\frac{n!}{\prod n_i!}\)种办法。
  • 四个基本问题
    1. 可辨别对象放入可辨别盒子:分步组合即可。
    2. 不可辨别对象放入可辨别盒子:分组问题。
    3. 可辨别对象放入不可辨别盒子:不作要求。
    4. 不可辨别对象放入不可辨别盒子:不作要求。

高级计数原理

常系数线性递推方程

  • 齐次: 已知\(a_0, a_1, ...a_k \text{(初值)}, a_n = \sum_{i=1}^k c_ia_{n-i}\)\(c\)均为常数
    • 解特征方程:\(r^k-c_1r^{k-1}-c_2r^{k-2}-...c_{k-1}r-c_k=0\),即\(\sum_{i=0}^{k}-c_ir^{k-i}=0,c_0=-1 \ \ (1)\),则\(a_n= r^n\)
    • 例:\(a_n = a_{n-1}+ a_{n-2}\rightarrow r^2=r+1\)
    • 如果\(a(n)\)\(b(n)\)都是某常系数线性齐次解递推关系的解,那么\(a(n)\)\(b(n)\)的任一线性组合\(t_1 a(n)+t_2b(n)\)也是该递推关系的解。
    • 无重根的情况: 给定初值后,解应当是\(a_n = \sum_{i=1}^m \alpha_i r_i^n\)\(r_i\)是式(1)的第\(i\)个解,并且没有重根。\(\alpha\)是待定系数,根据初值确定。
    • 二阶方程,有重根\(r_0\)\(a_n = α_1 r_0^n + α_2 nr_0^n\)
    • 一般情况,有重根: 每个\(r_i\)的系数\(\alpha\)变成:\(\alpha_1+\alpha_2n+...\alpha_{m-1}n^{m-1}\),根据初值求出各个\(\alpha\)。对应的\(r_i\)是几重根,其系数中就有几个\(\alpha\)
  • 非齐次: 已知\(a_0, a_1, ...a_k \text{(初值)}, a_n = \sum_{i=1}^k c_ia_{n-i}+F(n)\)\(c\)均为常数
    • 首先解出相伴齐次方程的通解\(a_h(n)\)
    • 再找到非齐次方程一个特解\(a_p(n)\)
    • 最终结果为\(a_n = a_p+a_h\)
    • 如果\(f(n)\)\(n\)次多项式,则特解一般也是n次多项式
    • \(f(n) = \beta^n\),且\(\beta\)\(e\)重特征根(不是根时e=0),则特解为\(a_p = pn^e\beta^n\)\(p\)为待定系数。

分治(不做要求)

  • 时间复杂度为:\(f(n) = af(n/b) + g(n)\)\(f(.)\)是该类问题需要的复杂度,\(g(n)\)是把子问题合并为原问题需要的复杂度。

生成函数

  • \(\{a_n\} \Rightarrow \sum_i a_ix^i \Rightarrow f(x)\)
  • \(C(m, n) \Rightarrow (1+x)^m\)
  • 物体配置问题: 不同面值\(\{n_1, n_2...n_k\}\)组合得到一个特定数字\(k\),求方法数\(p\)。(求解带限制的不定方程)
    • 同一面值不可辨别:解不定方程\(\sum_i m_i = q\)\(m_i\)为面值\(n_i\)贡献的数值,即\(m_i=\text{选取ni的数量} \times n_i\)
    • 构造生成函数:\(f(x)=\prod_i^{i=k} \sum x^{(m_i\text{可取的值)}}\),该函数中\(x^q\)的系数即为答案。
    • 若不定方程中的\(m\)没有限制,则转化为之前的组合问题。(\(C_{n+k-1}^n\)
    • 若同样面值的纸币/砝码之间有区别,则给相应的项加上乘方。可以看出,每一项表示的是每一个*每最小粒度可辨别元素**贡献的面值。
    • 例子:分饼干,砝码称重量,钱面值组合

容斥原理

  • \(|A\cup B| = |A| + |B|-|A \cap B |\)
  • \(|A \cup B \cup C|= |A|+|B|+|B|-|A\cap B|-|A \cap C|- |B \cap C |+| A\cap B \cap C|\)
  • 一般形式: \(\bigcup_i A_i = \sum_{j=1}^{n} \left( (-1)^{i+1}\sum_{i=1}^{j}\bigcap_i|A_i| \right)\)
  • m个元素\((x)\rightarrow\) n个元素\((y)\),求满射数量: 映射总数为\(N=n^m\),先求非满射数量\(p\)。设集合\(P_i\)表示第\(i\)\(y\)值没有被映射到,则\(p=|\bigcup_i P_i|\),即可利用容斥原理求出\(p\),答案即为\(N-p\)
  • 满射数目为\(\sum_{i=0}^{n-1} (-1)^i(n-i)^mC_n^i\)
  • \(n\)元素错位排列\(n!\sum_{i=0}^n (-1)^i {1\over i!}\)

数论

  • 整除:\(a|b,a|c \Rightarrow a| (mb+nc)\)
  • 取余数(\(mod\))
  • 模同余\(a \equiv b (mod\ m)\)\(a-b=km, a\ mod\ m = b\ mod\ m\)
  • 约定\(a+_mb=(a + b) (mod\ m), a\times_mb=(a \times b) (mod\ m)\)
  • 模同余の性质:

\[\bigstar a ≡ b (mod\ m), c ≡ d (mod\ m)\Rightarrow a + c ≡ b + d (mod\ m), ac ≡ bd (mod\ m)\]

\[a ≡ b (mod\ m)\Rightarrow ac ≡ bc (mod\ m)\text{(不能反推,反推要求c,m互素)}\]

\[(a + b) (mod\ m) = ((a\ mod\ m) + (b\ mod\ m)) mod\ m\]

\[ab\ mod\ m = ((a\ mod\ m) (b\ mod\ m)) mod\ m\ (2)\]

  • 模指数运算:快速计算\(b^n\ mod\ m\)
    • \(n\)分解为二进制串\((n_1n_2n_3n_4...)_{(2)}\),分别从低阶到高计算\(b^{n_i2^{i}} mod\ m\),利用式子\((2)\)计算高阶模运算。
  • 算数基本定理:任何一个大于1的正整数都可以唯一地分解为若干个素数的乘积
  • 最大公约数\(gcd(a, b)\),最小公倍数\(lcm(a, b)\)
  • \(lcm(2^3 3^ 5 7^ 2 , 2^ 4 3^ 3 ) = 2 ^{max(3,4)} 3^{ max(5,3)} 7^ {max(2,0)} = 2 ^4 3^ 5 7^ 2\)
  • 最大公约数上式中\(max\)改为\(min\)即可
  • \(ab = gcd(a, b)\times lcm(a, b)\)
  • 辗转相除:\(a>b\Rightarrow gcd(a, b) = gcd(a\ mod\ b, b)\)
  • \(\exists s, t\in Z, gcd(a, b)=sa+tb\)
  • \(a\)关于\(m\)的模逆\(\bar{a}:a\bar{a}\equiv 1(mod\ m)\)
    • \(m>1, a\ m\)互素,则\(\bar{a}\)存在且唯一。
  • 解同余方程\(ax \equiv b (mod\ m)\): 两边同乘模逆得到\(\bar{a}ax \equiv \bar{a}b (mod\ m)\),简单表示为\(\bar{a}ax\equiv\bar{a}b\ (3)\)
    • 利用传递性求解:\(\bar{a}a\equiv1\)两边同乘x得\(\bar{a}ax\equiv x\),结合式子(3)得\(x\equiv \bar{a}b\),即可解出x。
  • 欧拉函数:\(\Phi(n)=[1,n]\)中与\(n\)互素的数字的数目。
  • \(n\)为素数,则\(\Phi(n) =n-1\)
  • \(p,q\)为素数,则\(Φ(pq) = pq − (p + q − 1) = (p − 1)(q − 1)\)
  • 欧拉定理:\(a ^{Φ(n)} ≡ 1 (mod\ n),a\)\(n\)互素。
  • 费马小定理(欧拉定理在\(n\)取一素数\(p\)时的情况):\(a ^p ≡a(mod\ p),p\)是素数,\(a\)是任意整数。这是\(p\)为素数的必要条件
  • 或者: \(a^{p-1}\equiv1(mod\ p)\)
  • 例:计算\(7^{222} mod\ 11\)\(222=11\times 10+2,\)利用费马小定理得

\[7^{10}\equiv1(mod\ 11)\Rightarrow (7^{10})^{11}\equiv1^{11}(mod\ 11) \]

再计算\(7^2mod\ 11\)即可推出答案。

  • RSA:随机选取2个(足够大的)大素数\(p\)\(q(p<q)\), 记\(n=pq\), \(\Phi(n)=(p-1)(q-1)\). 选择正整数(加密公钥)\(e\),要求\(e\)\(\Phi(n)\)互素, 解密私钥\(d\)\(e\)关于于模\(\Phi\)(n)的模逆,即\(de\equiv1(mod\ \Phi(n))\)
  • 加密时对每一段明文\(m<n: c =m ^e mod\ n\),这里要求\(m,n\)必须互素
  • 解密时对密文\(c:m = c^d mod\ n\)
  • 其中加密公钥e和n是公开的, 而\(p,q, \Phi(n),d\)(秘钥)是保密的.

格论

  • 运算\(*,@\)的吸收律:\(x*(x@y)=x,x@(x*y)=x\)
  • 一个非空集合S和定义在该集合上的一个或多个运算\(o_1,o_2...o_n\)组成的系统称为代数系统\(<S;o_1, o_2, ...o_n>\)
  • 偏序:反对称(\(x≤y , y≤x \Rightarrow x=y\)),传递,自反。
  • 最小上界\(a\vee b\),最大下界\(a\wedge b\)
  • 全序:链式偏序,良序:任何子集都有最小元。
  • 格:任意两个元素都有最小上界和最大下界の偏序(注意,上下界必须唯一)
  • 完全格:任意子集都有最小上界和最大下界の偏序
  • 代数格:\(<L; \vee, \wedge>\)
    • 幂等:\(x∧x=x; x∨x=x\)
    • 交换:\(x∧y=y∧x; x∨y=y∨x\)
    • 结合:\((x∧y)∧z = x∧(y∧z); (x∨y)∨z = x∨(y∨z)\)
    • 吸收:\(x ∧(x∨y ) = x = x∨(x∧y )\)
    • 分配不等式:\(x∨(y∧z)≤(x∨y)∧(x∨z),(x∧y) ∨(x∧z)≤x∧(y∨z)\),二者对偶。
  • 当证明相等时,一般从偏序的定义出发,或者证明两者相互有≤的关系
  • 对偶命题:\(\leqslant,\geqslant,∧,∨\)分别替换成\(\leqslant,\geqslant,∨,∧\)
  • 求子格:要注意哈塞图删掉了原本存在的一些连线
  • 分配格:满足分配律。钻石格、五角格不是.

我记不住的比较难的部分

辗转相除求模逆,解同余方程,解递推方程(齐次、非齐次),证明格代数不等式,全错位排列