「BUAA Discrete Mathematics Chapter2」排列与组合

Part 0 前言

内容概况

BUAA离散数学3同步笔记，对应内容为《组合数学》（Richard A.Brualdi）第2章与PPT对应授课内容。

读者前置知识期望

1. 高中数学基本知识
2. 离散数学1、2基本知识
3. 如果没有以上知识，善用搜索引擎也可

Part 1 四个基本计数原理

加法原理

集合S被划分为两两不相交的部分$S_1$, $S_2$,···,$S_m$，则$S$的对象数目可以通过其每一个部分的对象的数目相加得到。

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

乘法原理

$S$是对象的有序对$(a,b)$的集合，其中第一个对象$a$来自大小为$p$的一个集合，对于对象$a$的每一个选择，对象$b$有$q$种选择，于是，$S$的大小为$p \times q$

$$|S| = p \times q$$

减法原理

$A$为集合，$U$包含$A$，定义$A$在$U$中的补$\overline{A}$：

$$\overline{A} = U \backslash A = \{x \in U:x\notin A\}$$

$A$的对象的数目由以下公式给出：

$$|A| = |U| - |\overline{A}|$$

除法原理

$S$是一个优先级和，将其划分为$k$个部分，使得每一个部分包含的对象数目相同。划分的部分中的数目由下述公式给出：

$$k = \frac{|S|}{在一个部分中的对象数目}$$

Part 2 集合的排列

定理2.2.1 排列数$P(n,r)$

定义：$r$排列表示有$r$个元素的排列。

定义：$P(n,r)$表示$n$元素集合$r$排列的数目。

对于正整数$n$和$r$，$r \le n$，有：

$$P(n,r) = n \times (n-1) \times ···\times(n-r-1)$$

定理2.2.2 循环$r$排列

$n$元素集合的循环$r$排列的数目是：

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

特别地，$n$个元素的循环排列的数目是$(n-1)!$

---

• ← Previous Post
• Next Post →

---