《组合数学》 §1.1 学习笔记

前言：开新坑，但是这个坑比其他的好填。

定义 1.1.1

组成集合的对象称作元素。

定义 1.1.2

多重集是元素可以重复出现的集合。某个元素 \(a_i\) 出现的次数 \(n_i~(n_i = 0,1,\cdots,\infty)\) 称作元素的重数。

通常把含有 \(k\) 种不同元素的多重集 \(S\) 记作 \(\{n_1\cdot a_1, n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) ，也记作 \(\{a_1^{n_1},a_2^{n_2},\cdots,a_k^{n_k}\}\) 。

定义 1.1.3

给定集合 \(A\) ，称集合 \(A\) 中的元素个数为集合 \(A\) 的基数，记作 \(|A|\) 。若 \(|A|=n\) ，称 \(A\) 为一个 \(n\)–集合

定义 1.1.4

给定集合 \(A\) ，称 \(A\) 所有子集构成的集合为集合 \(A\) 的幂集，记作 \(P(A)\) 。

例 1.1.5

图 \(G=(V,E)\) ，\(V\) 称作顶点集，\(E\) 称作边集，其他略。

\(V\) 的所有 \(2\)–子集的集合记为 \(\binom{V}{2}\) ，显然 \(|\binom{V}{2}|=\frac{n(n-1)}{2}\) 。图论相关请参考 图论相关概念 。

定义 1.1.6

若 \(A\) 的非空子集的集合 \(\mathcal{P} = \{A_1,A_2,\cdots,A_k\}\) 满足 \[ A = \bigcup_{i=1}^k A_i \quad\mathbf{and}\quad A_i \cap A_j = \varnothing~(i \ne j) \] 则称 \(\mathcal{P}\) 是 \(A\) 的一个划分。

定义 1.1.7

设 \(A,B\) 为两个集合，他们的笛卡尔积定义为 \[ A\times B = \{(a,b) \mid a \in A, b \in B\} \] 显然有 \(|A\times B| = |A| \times |B|\) 。

一个 \(A\) 到 \(B\) 的二元关系 \(R\) ，记为 \(R: A \to B\) ，定义为 \(A\times B\) 的一个子集。

二元关系 \(R\) 的定义域为 \(\{a\in A \mid \exists b \in B,(a,b) \in R\}\) ，值域为 \(\{b \in B \mid \exists a \in A, (a,b) \in R\}\)

若 \((a,b) \in R\) ，则称 \(a\) 与 \(b\) 有二元关系 \(R\) 。对于 \(a \in A\) ，\(a\) 的像为 \[ R(a) = \{b \in B \mid (a,b) \in R\} \] 故 \(R\) 的值域为 \(\bigcup_{a\in A}R(a)\) 。对于 \(b \in B\) ，\(b\) 的原像为 \[ R^{-1} = \{a\in A \mid (a,b) \in R\} \] 其中 \(R\) 的反关系 \(R^{-1}: B \to A\) 定义为 \[ R^{-1} = \{(b, a) \mid (a,b) \in R\} \] 设 \(R\) 是 \(A\) 上的一个二元关系，即一个 \(A\) 到 \(A\) 的二元关系，

• 称 \(R\) 是自反的，如果对任意 \(a \in A\) 有 \((a,a) \in R\) ；
• 称 \(R\) 是对称的，如果对 \((a,b) \in R\) 有 \((b, a) \in R\) ；
• 称 \(R\) 是反对称的，如果对 \((a,b)\in R,(b,a) \in R\) 有 \(a=b\) ；
• 称 \(R\) 是传递的，如果对 \((a,b)\in R,(b,c) \in R\) 有 \((a,c) \in R\) 。

定义 1.1.8

设 \(R\) 是集合 \(A\) 上的一个二元关系。若 \(R\) 是自反的、对称的和传递的，则称 \(R\) 是定义在 \(A\) 上的一个等价关系。

此时，若 \((x,y) \in R\) ，则称 \(x\) 等价于 \(y\) ，记作 \(x \sim y\) 。

设 \(R\) 为一等价关系，对任意 \(a \in A\) ，\(a\) 的像 \[ R(a) = \{b \in A \mid (a,b) \in R\} \] 称为包含元素 \(a\) 的等价类。显然集合 \(A\) 上的等价类构成 \(A\) 的一个划分。

反之，从 \(A\) 的一个划分也可得到 \(A\) 上的一个等价关系 \(R\) ，

定义为：\((a,b)\in R\) 当且仅当 \(a,b\) 在 \(\mathcal{P}\) 的某个元素中。

定义 1.1.9

设 \(f\) 是从 \(A\) 到 \(B\) 的一个二元关系。若 \(f\) 满足 \(\forall a \in A,|f(a)|=1\) ，则称 \(f\) 是从 \(A\) 到 \(B\) 的一个映射。

对于映射 \(f\) ，

• 若对任意 \(a_1,a_2 \in A,a_1 \ne a_2\) ，有 \(f(a_1) \ne f(a_2)\) ，则称 \(f\) 为单射。

• 若对于任意 \(b \in B\) 都有 \(f^{-1}(b) \ne \varnothing\) ，则称 \(f\) 为满射。

• 若 \(f^{-1}\) 也是映射，则称 \(f\) 为双射。显然 \(f\) 是双射当且仅当 \(f\) 即使单射又是满射。

定理 1.1.10

设 \(A,B\) 为两个基数相同的有限集，\(f\) 为 \(A\) 到 \(B\) 的一个映射，则 \(f\) 为单射当且仅当 \(f\) 为满射。