1. 概念#

可数集合是指具有与自然数集合 $\mathbb{N}$ 一一对应的元素的集合。也就是说，如果一个集合可以被安排在一个由自然数索引的无限列表中，那么它就是可数的。例如，自然数集合、整数集合、有理数集合等都是可数的。

具体来说,当且仅当一个集合 $A$ 的元素可以排列成一个序列 $a_1,a_2,\dots$ 时，该集合 $A$ 是可数无穷的。如果 $A$ 是可数无穷的，则存在一个双射 $f:\mathbb{Z}^+\rightarrow A$。如果 $A=\{a_1,a_2,\dots\}$，则定义 $f:\mathbb{Z}^+\rightarrow A$，$f(i)=a_i$ 是一个双射，满足 $a_i=f(i)$，对于每一个 $i=1,2,3,\dots$。

不可数集合是指元素无法一一对应于自然数集合的集合。也就是说，如果一个集合不能被安排在一个由自然数索引的无限列表中，那么它就是不可数的。例如，实数集合、幂集（一个集合的所有子集构成的集合）等都是不可数的。

2. 重要定理#

1. 实数集合是不可数的。

2. 可数并集仍然是可数的。

3. 如果一个集合 $A$ 是可数无穷的，那么它的任何无穷子集 $X$ 也是可数的。

4. 如果一个集合 $A$ 是不可数的，那么它的任何包含它的集合 $X$ 也是不可数的。

5. 如果两个集合 $A$ 和 $B$ 都是可数无穷的，那么它们的并集 $A\cup B$ 也是可数无穷的。

6. 如果两个集合 $A$ 和 $B$ 都是可数无穷的，那么它们的笛卡尔积¹ $A\times B$ 也是可数无穷的。

1. 求和原理（The Sum Rule）#

对于一个有限集合 $A$ ，如果将它划分为 $k$ 个非空的子集 ${A_1, A_2, \dots, A_k}$ ，那么 $A$ 的元素个数等于每个子集的元素个数之和，即 $|A|=|A_1 |+|A_2 |+\cdots+|A_k |$

2. 乘积原理（The Product Rule）#

对于有限集合 $A_1, A_2, \dots, A_k$ ，它们的笛卡尔积的元素个数等于每个集合的元素个数之积，即 $|A_1\times A_2\times\cdots\times A_k|=|A_1| \cdot |A_2|\cdot \cdots\cdot|A_k|$

3. 双射原理（The Bijection Rule）#

对于两个有限集合 $A$ 和 $B$ ，如果它们之间存在一个双射函数（即一一对应函数） $f: A\to B$ ，那么它们的元素个数相等，即 $|A|=|B|$ 。

1. 概念#

集合排列（Permutations of Set）是指对给定集合中的元素进行重新排列的过程，使得每个元素只出现一次，并按照一定顺序进行排列。

给定一个集合 $A=\{a_1,\ a_2,\ \dots, a_n\}$ 和一个正整数 $r$ （ $r \leq n$ ），一个 $r$ 元排列 of $A$ 是由 $A$ 中选择 $r$ 个不同的元素，并按照一定顺序排列得到的序列。特别地，如果 $r=n$，则称其为一个 $A$ 的排列，即 $A$ 的所有元素被重新排列的序列。

例如，当 $A=\{1,\ 2,\ 3\}$ 时，它的所有 $2$- 是由 $A$ 中选择 $2$ 个不同的元素并按照一定顺序排列得到的序列，如 $(1,2);(1,3);(2,1);(2,3);(3,1);(3,2)$ 。注意，每个数字只能在每个序列中出现一次，因为它们必须是不同的元素。

同时还有一种特殊的排列：$A$ 的 $r$ 元重排列（$r$-permutation of $A$ with repetition） 它相比普通的排列多出一个性质，就是允许序列中包含重复的元素，而在集合的定义中元素是不能重复的。

具体来说，一个 $A$ 的 $r$ 元重排列 是由 $A$ 中的元素构成的长度为 $r$ 的序列，其中每个元素都可以重复出现多次。在上一个例子中，集合 $A=\{1,\ 2,\ 3\}$，包含重复元素的所有长度为 $2$ 的排列就是： $(1,1);(1,2);(1,3);(2,1);(2,2);(2,3);(3,1);(3,2);(3,3)$ 。

2. 相关基本定理#

1. 概念#

多重集合是指一个集合中的元素可以重复出现，每个元素可能会有不同的重复次数。在一个多重集合中，元素的重复次数被称为其重数（multiplicity）。一个 $n$-multiset 是指一个有 $n$ 个元素的多重集合。

一个多重集合 $A$ 可以用下面的形式表示：$A = \{n_1\cdot a_1, n_2\cdot a_2, \dots, n_k\cdot a_k\}$，其中 $a_1, a_2, \dots, a_k$ 是不同的元素，$n_1, n_2, \dots, n_k$ 分别表示这些元素在 $A$ 中出现的次数。因此，$A$ 中元素的总数为 $n_1 + n_2 + \dots + n_k$。

一个 $r$-subset $T$ 是指一个多重集合 $A$ 的子集，使得 $T$ 中每个元素的重数不超过其在 $A$ 中出现的重数，并且 $T$ 中元素的总数为 $r$。换言之，$T$ 可以写成 $T = \{t_1\cdot a_1, t_2\cdot a_2, \dots, t_k\cdot a_k\}$ 的形式，其中 $0 \leq t_i \leq n_i$，并且 $t_1 + t_2 + \dots + t_k = r$ 。

2. 多重集合的排列#

一个多重集合的排列和一个普通集合的排列非常相似，不过要求每个元素出现的次数与它在原多重集合中出现的次数相同。

设 $A=\{n_1\cdot a_1,\dots,n_k\cdot a_k\}$ 是一个 $n$ 元多重集合。若一个序列 $x_1,\ \dots,\ x_n$ 中满足 $a_i$ 恰好出现 $n_i$ 次，则称它为 $A$ 的一个排列。例如，对于 $A=\{1\cdot a, 2\cdot b, 3\cdot c\}$，序列 $a,b,c,b,c,c$ 是 $A$ 的一个排列，序列 $b,c,b$ 是 $A$ 的一个 $3$ 排列。

3. 多重集合的重复排列定理#

与普通集合类似，一个多重集合 $A$ 的排列方式总数的计算公式为 $\frac{(n_1 + n_2 + \cdots + n_k)!}{(n_1!n_2!\cdots n_k!)}$ 其中，$A$ 是由 $k$ 种元素构成的多重集合，每个元素 $a_i$ 重复出现 $n_i$ 次。也就是说，$A$ 中的每个元素 $a_i$ 有 $n_i$ 个相同的副本。