《组合数学》 §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$ 为满射。