组合学 [3]

本篇内容

• 集合的可数与不可数
• 基本计数原理
  • 求和原理
  • 乘积原理
  • 双射原理
• 集合的排列
• 多重集合
• 多重集合的排列

---

集合的可数和不可数

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$ 都是可数无穷的，那么它们的笛卡尔积^[1] $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. 相关基本定理

排列定理

一个包含 $n$ 个元素的集合中，取 $r$ 个元素排成不同的顺序的个数为 $P(n,r)$，即 $n$ 个元素中取 $r$ 个元素排列的总数。

根据 $r$ 元排列 的定义，其中第一个元素有 $n$ 种选择，第二个元素有 $n-1$ 种选择（因为已经选了一个元素），以此类推，第 $r$ 个元素有 $n-r+1$ 种选择。因此，从 $n$ 个元素中选出 $r$ 个元素排列的总数为 $n \cdot (n-1) \cdot (n-2) \cdots (n-r+1)$，或者写成 $n(n-1)(n-2)\cdots(n-r+1)$ 。

根据乘法原理，上述结果还可以写成

$$\frac{n(n-1)(n-2)\cdots(n-r+1)(n-r)(n-r-1)\cdots 1}{(n-r)(n-r-1)\cdots1}= n(n-1)(n-2)\cdots(n-r+1)$$

因此，$r$ 元排列 的总数可以简化为 $n(n-1)(n-2)\cdots(n-r+1)/(n-r)(n-r-1)\cdots1$。这个式子也可以写成 $\frac{n!}{(n-r)!}$ 的形式，即一个 $n$ 元素集合中 $r$ 个元素的排列总数为

$$P(n,r)=\frac{n!}{(n-r)!}$$

集合的重复排列定理（Theorem of Repetitions）

对于一个包含 $n$ 个元素的集合 $A$，在允许重复的情况下，取 $r$ 个元素可以得到 $n^r$ 种不同的排列。

这是因为在构造每个排列时，每个元素都有 $n$ 种选择，而选择的方式是独立的，因此总共有 $n^r$ 种排列。例如，一个包含 $3$ 个元素的集合 $A={1,2,3}$，可以生成包含重复元素的所有长度为 $2$ 的排列，共 $3^2=9$ 种，如$(1,1);(1,2);(1,3);(2,1);(2,2);(2,3);(3,1);(3,2);(3,3)$ 。

---

多重集合

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$ 个相同的副本。

---

1. 1.表示两个集合中所有可能的有序对组成的集合 ↩