排列，组合，循环排列与斯特林数

· · 个人记录

一：排列

1.定义：

从 n 个不同的元素中任取 m(m \le n) 个元素，按照一定顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。

2.符号：

从 n 个不同元素中取出 m 个元素的一个排列数，用符号 A^m_n 表示。

3.公式：

**特殊规定： $0!=1$。** ## 4.性质： ① $A^{n-1}_n = A^n_n

② A^m_n \times A^{n-1}_{n-1} = A^{m-1}_{n-1} \times A^n_n

③ A^{n-m}_n \times A^m_m = A^n_n

二：组合

1.定义：

从 n 个不同的元素中任取 m(m \le n) 个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。

2.符号：

从 n 个不同元素中取出 m 个元素的一个组合数，用符号 C^m_n 表示。

3.公式：

## 4.性质： ① $C^m_n = C^{n-m}_n

② C^m_n = C^{m-1}_{n-1} + C^m_{n-1} (重点) ，即选第 m 个数与不选第 m 个数的方案之和。

三：循环排列（又称圆排列，环排列）

1.定义：

## 2.公式： $n$ 个数的循环排列的方案数为：$(n-1)!$。 从 $n$ 个数中选 $m$ 个数的循环排列的方案数为: $C^m_n \times (n-1)! = \frac{A^m_n}{n}$。 **证明：** ①设 $n$ 个数的循环排列方案数有 $x$ 种。 ∵一个由 $n$ 个数组成的循环排列所对应的直线排列有 $n$ 种; ∴$n$ 个数的循环排列所对应的直线排列共有 $x \times n$ 种; 又∵由 $n$ 个数组成的直线排列有 $n!$ 种; ∴$x \times n = n!$; ∴$x = (n-1)!$. ②∵从 $n$ 个数中选 $m$ 个数的方案数为$C_n^m$; 又∵$m$ 个数的循环排列的方案数为 $(m-1)!$ 种; ∴从 $n$ 个数中选 $m$ 个数的组成的循环排列的方案数为 $C_n^m \times (m-1)!= \frac{A_n^m}{m}$ 种. **注意：如果不考虑元素按顺时针的方向与按逆时针的方向之间的差别，这两种排列只能算一种排列，那么两个公式分别变成：** $\frac{(n-1)!}{2}$ 和 $\frac{C_n^m \times (m-1)!}{2} = \frac{A_n^m}{2m}

四：斯特林数

第一类斯特林数：

1.定义：

### 2.公式 $S1(n,m) = S1(n-1,m-1) + S1(n-1,m) \times (n-1)

证明：

将 n 个不同元素构成 m 个圆排列，若第 n 个元素单独构成一个圆排列，则剩下的 n-1 个人要构成 m-1 个圆排列，方案数为 S1(n-1,m-1)；若第 n 个元素不单独构成一个圆排列，则我们可以先让 n-1 个人构成 m 个圆排列，方案数为 S1(n-1,m) ，再将第 n 个人放在 n-1 个人中每个人的左边(也可以是右边)，方案数为 n-1 ，因此总的方案数为 S1(n,m) = S1(n-1,m-1) + S1(n-1,m) \times (n-1)

3.边界：

## 第二类斯特林数： ### 1.定义： $S2(n,m)$ 表示把 $n$ 个不同元素划分到 $m$ 个集合的方案数。 ### 2.公式： ①$S2(n,m) = S2(n-1,m-1) + S2(n-1,m) \times m

②S2(n,m) = \frac{\sum \limits_{k=0}^m(-1)^k \times C_m^k \times (m-k)^n}{m!}

证明：

将 n 个不同元素划分成 m 个集合，若第 n 个元素单独构成一个集合，则剩下的 n-1 个人要构成 m-1 个集合，方案数为 S2(n-1,m-1)；若第 n 个元素不单独构成一个集合，则我们可以先让 n-1 个人构成 m 个集合，方案数为 S2(n-1,m) ，再将第 n 个人放在 m 个集合里，方案数为 m ，因此总的方案数为 S2(n,m) = S2(n-1,m-1) + S2(n-1,m) \times m

3.边界：

## 两类斯特林数之间的关系： $\sum_{i=0}^n S1(n,i) \times S2(i,m) = \sum_{i=0}^n S2(n,i) \times S1(i,m)