二元集合

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B| = |A| + |B| - |A\cap B|

常用符号

AI:=⋂i∈IAi=⋂{Ai∣i∈I}A_I:=\bigcap_{i\in I} A_i = \bigcap\{A_i | i\in I\}

例如，A1,2,4=A1∩A2∩A4A_{1,2,4} = A_1\cap A_2\cap A_4, 但是更方便的写法是 A124A_{124}

空集表示

A∅=⋂X=XA_\varnothing = \bigcap{X} = X 这个表示的是全集

容斥原理

对于 A1,⋯ ,AnA_1,\cdots ,A_n 是集合 XX 的子集 那么X 的元素中不在集合 A12⋯nA_{12\cdots n} 中的有

(Ac)[n]=∑I⊂[n](−1)∣I∣∣AI∣=∑r≥0(−1)r∑∣I∣=r∣AI∣(A^c)_{[n]} = \sum_{I\subset[n]}(-1)^{|I|}|A_I| = \sum_{r\ge 0}(-1)^r\sum_{|I| = r}|A_I|

推论

令 A1⋯AnA_1 \cdots A_n 是集合那么 ∣A1∪A2∪⋯∪An∣=∑∅≠I⊂[n](−1)∣I∣+1∣AI∣|A_1\cup A_2\cup \cdots \cup A_n| = \sum_{\varnothing \not = I\subset [n]}(-1)^{|I|+1}|A_I|

证明

由于 ⋃i∈IAi\bigcup_{i\in I}A_i 是上述容斥原理的补集，那么我们用容斥原理公式加上一个 ∣X∣−(Ac)[n]|X| - (A^c)_{[n]} 就可以得到

简化公式

如果对于分区集合我们有 ∣I∣=∣J∣⇒∣AI∣=∣AJ∣|I| = |J|\Rightarrow |A_I| = |A_J| 那么我们有 ∣A1∩⋯∩An∣|A_1\cap \cdots\cap A_n| 的值只依赖于 k 即 I={i1,⋯ ,ik}I = \{i_1,\cdots,i_k\} 那么容斥原理公式即为

∣A1∪⋯∪An∣=∑r=1n(−1)r+1∑∣I∣=r(nr)∣AI∣|A_1\cup \cdots \cup A_n| = \sum_{r=1}^n(-1)^{r+1}\sum_{|I| = r}\begin{pmatrix}n\\r\end{pmatrix}|A_I|

上界集合 Closed Up-Set

对于集合类A: A:=A:= 包含 AiA_i 的元素，其中 i∈Ii\in I 同时可以拥有 j∉Ij\not \in I
对于集合类E: E:=E:= 包含 AiA_i 的元素，其中 i∈Ii\in I 同时不拥有 j∉Ij\not \in I
![[/images/ie_theory.png]]
那么定义偏序关系 EI⪯EJ⇔I⊂JE_I \preceq E_J \Leftrightarrow I\subset J 那么我们有 closed up-set :

U[EI]:=⋃{EJ∣I⊂J}U[E_I] := \bigcup\{E_J | I\subset J\}

这个定义表明 AI=U[EI]A_I = U[E_I]

可数参数

  1. Nr:=∑∣I∣=r∣AI∣=∑∣I∣=r∣U[EI]∣N_r:=\sum_{|I| = r}|A_I| = \sum_{|I| = r}|U[E_I]|
  2. er:=∑∣I∣=r∣EI∣e_r := \sum_{|I| = r}|E_I|

上界集合公式

Nr=∑t≥0(tr)etN_r = \sum_{t\ge 0}\begin{pmatrix}t\\r\end{pmatrix}e_t

当然由于 t<rt<r 的时候这个组合数是 0，所以我们可以改写为

Nr=∑t≥r(tr)etN_r = \sum_{t\ge r}\begin{pmatrix}t\\r\end{pmatrix}e_t

失序排列 Derangement

对于排列 σ∈Sn\sigma \in S_n 对于集合 [n][n] 称为失序排列如果 σ(i)≠i\sigma(i)\neq i 对所有 ii 成立

失序排列数量定理

对于集合 [n][n] 的失序排列的可能性数量可以表示为

dn=∑i=0n(−1)i(ni)(n−i)!=n!∑i=0n(−1)ii!d_n = \sum_{i = 0}^n (-1)^i \begin{pmatrix}n \\ i\end{pmatrix}(n-i)! = n! \sum_{i=0}^n \frac{(-1)^i}{i!}

证明

对于集合 Ai:={σ∈Sn∣σ(i)=i}A_i:=\{\sigma\in S_n | \sigma(i) = i\} 因此我们有 ∣Ai∣=(n−1)!|A_i| = (n - 1)! 也就是说 AiA_i 表示第i位正确排列
那么我们有 ∣AI∣=(n−∣I∣)!|A_I| = (n - |I|)! 接下来，使用容斥原理我们就有 d_n 的公式

近似法

对于 σ∈Sn\sigma \in S_n 每一种可能性相当，那么有多少种可能 σ\sigma 是一个失序排列？
因此，我们有

lim⁡n→∞dnn!=lim⁡n→∞∑i=0n(−1)ii!=1e\lim_{n\to \infty}\frac{d_n}{n!} = \lim_{n\to \infty}\sum_{i=0}^n \frac{(-1)^i}{i!} = \frac{1}{e}

满射数量定理

对于 k≥nk\ge n那么满射的数量 f:[k] → [n]f : [k]\ \to \ [n] 是

Sk,n=∑i=0n−1(−1)i(ni)(n−i)kS_{k,n} = \sum_{i=0}^{n-1} (-1)^i\begin{pmatrix}n\\ i\end{pmatrix}(n - i)^ k

这个时候，我们首先应该想到，在 [n][n] 空间中存在某个元素无解的情况，我们设置成上面例子中的 AiA_i 集合