“排列与组合”笔记

数学 组合数学

---

主页地址 ：月光森林

---

1. 基本计数原理

设集合S的 一个划分 即为S的子集的集合$S_1, S_2, ..., S_m$ ，使得S的每一个元素恰好是这些子集之一的元素：

• $S = S_1 \cup S_2 \cup ... \cup S_m$

• $S_i \cap S_j = \varnothing (i \neq j)$

子集$S_1, S_2, ..., S_m$称为该划分的部分。

集合$S$的元素个数表示为$|S|$, 又是称之为$S$的大小。

加法原理

设集合S划分为部分$S_1, S_2, ..., S_m$ 。则S的元素个数可以通过找出它的每一个划分的个数来确定，我们把这些数相加，得到：

$$|S| = |S_1| + |S_2| + ... + |S_m|$$

如果集合$S_1, S_2, ...,S_m$可以重叠，那么要使用一个更深刻的原理（容斥原理）来计数S中的元素个数。

用选择的术语叙述加法原理的形式为 ：

如果有p种方法能够从一堆中选择一个物体，而有q种方法能从另一堆中选择一个物体，那么从这两堆中选择一个物体的方法共有p+q种。

这种形式的加法原理可以很容易推广到多堆。

乘法原理

令S是元素的序偶(a, b)的集合，其中一个元素a来自大小为p的一个集合，而对a的每个选择，元素b存在着q种选择。于是，S的大小为p × q :

$$|S| = p × q$$

乘法原理的第二种形式：

如果一项任务有p项结果，而不论第一项任务的结果如何，第二项任务都有q个结果，那么，这两个任务连续执行就有p×q个结果。*

减法原理

令A是一个集合，而U是包含A的更大的集合。设

$$B = \bar{A} = \{x \in U ; x \notin A \}$$

是A在U中的补。那么A中的元素个数|A|由下列法则给出：

$$|A| = |U| - |B|$$

在应用减法原理中，集合U通常是某个自然的集合，包括讨论中所有元素的（即所谓的泛集）。使用减法原理只有当对U中的元素计数和对$|\bar{A}|$中元素计数比对A中元素计数容易时才有意义。

除法原理

令S是一个有限集，它以下述方式被划分成k部分，每一部分包含相同数目的元素。此时，划分中的部分的数目由下述公式给出：

$$k = \frac {|S|} {在一个部分中的元素个数}$$

于是，如果我们知道S中元素个数以及各部分所含元素的相同的个数，则可以确定部分的数目。

集合的排列

令r是正整数。我们把n个元素的集合S的一个r-排列理解为n个元素中的r个元素的有序摆放。

我们用 $P(n, r)$ 表示n个元素集合的r-排列的数目。如果 $r > n$ ,则 $P(n, r) = 0$ 。显然，对每一个正整数 $n$， 有 $P(n, 1) = n$ 。一个n-元素集合S的一个n-排列被更简单地称为S的一个排列或n个元素的一个排列。于是，集合S的一个排列就是以某种顺序列出S的所有元素。

定理 ： 对于正整数$n$和$r$ ，$r \leq n$ ，有

$$P(n, r) = n (n - 1) ... (n - r + 1)$$

定义$n!$（读作n的阶乘）为 $n! = n(n - 1) ... 1$ 。并约定$0! = 1$ 。于是我们可以写成：

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

对于$n \ge 0$，定义$P(n, 1)$为 1，正好与$r = 0$时的公式一致。n个元素的排列数为

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

我们把元素的排列看成一条线，称之为线性排列，或线排列。如果两个排列的元素相同而且排列次序也相同，那么就是两个相同的排列，只能算作一种排列。

从集合$S = \{a_1, a_2, ..., a_n\}$的n个不同元素中，取出r个元素按照某种次序（如逆时针）排成一个圆圈，称这样的排列为圆排列，或循环排列。

定理 : n个元素的集合的循环r-排列的个数由

$$\frac {P(n, r)} r = \frac{n!}{r * (n - r)!}$$
给出。特别的，n个元素的循环排列的个数是$(n - 1)!$ 。

集合的组合

令r为非负整数。我们把n个元素的集合S的r-组合理解为从S的n个元素中对r个元素的无序选择。换句话说，S的一个r-组合是S的一个子集，该子集由S的n个元素中的r个组成，即S的一个r-元素子集。

如果用$C(n, r)$表示n-元素集的r-组合的个数。特别地，$C(0, 0) = 1$。

定理 ： 对于 $0 \ge r \ge n$ , 有 $P(n, r) = r! * C(n, r)$
因此

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

多重集的排列

如果S是一个多重集，那么S的一个r-排列是S的r个元素的一个有序排放。如果S的元素个数是n个（包括重复元素），那么S的n-排列也将称为S的排列。

定理 ： 令S是一个多重集，它有K个不同类型的元素，每一个元素都有无限重复次数。那么，S的r-排列的个数为$K^r$。

如果S的k个不同种类是元素的重复数均至少为r，那么定理还是成立的。

定理 ： 令S是一个多重集，有K个不同类型的元素。各元素的重数分别是$n_1, n_2, ..., n_k$。设S的大小为$n = n^1 + n^2 + ... + n^k$。 则S的排列数等于

$$\frac {n!} {n_1!n_2!...n_k!}$$

定理 ： 令n是一个正整数，并令$n_1, n_2, .., n_k$是正整数且$n = n_1 + n_2 + ... + n_k$ 。将n个元素的集合划分成k个被做标签的盒子$B_1, B_2, .., B_k$的方式数为

$$\frac {n!}{n_1! n_2! ... n_k!}$$ 其中盒1含有$n_1$个元素，盒2含有$n_2$个元素，... , 盒k含有$n_k$个元素。

如果这些盒子不被做标签，那么划分的个数是：

$$\frac {n!}{k!n_1! n_2! ... n_k!}$$

多重集的组合

如果S是一个多重集，那么S的r-组合是S中的r个元素的一个无序选择。因此，S的一个r-组合本身就是就是一个多重集 —— S的一个子多重集。

定理 ： 令S为具有k种类型元素的一个多重集，每种元素具有无限的重复数。则S的r-组合的个数等于$C(r + k - 1, r) = C(r + k - 1, k - 1)$。

可以证明，S的r-组合的个数等于方程 $x_1 + x_2 + ... + x_k = r$ 的解的个数，其中这些解$x_1, x_2, ... , x_k$都是非负整数。而这些解的个数等于两种不同类型元素的多重集 $T = \{r · 1, (k - 1) · 0\}$的排列的个数形同。

如果S中的K种元素的重复数都不小于r，定理仍然成立。

假设在r-组合中，

• 每种类型的元素个数都有一个下界$b_1, b_2, ..., b_n$；

• 则可引入新的变量$y_1 = x_1 - b_1, y_2 = x_2 - b_2, ... , y_k = x_k - b_k$；

• 诸$x_i$的下界能够满足当且仅当这些$y_i$是非负的；

• 此时原方程$x_1 + x_2 + ... + x_k = r$可以改写为$y_1 + y_2 + ... + y_k = r - b_1 - b_2 - ... - b_k = r^*$；

• 新方程的非负整数解个个数为$C(r^* + k - 1, k - 1) = C(r^* + k - 1, r^*)$

---

以上です～