排列组合

一、基本概念区分

排列与组合

1. 排列（Permutation）

   指从 n 个不同元素中取出 m 个元素，按照一定顺序排列的方式数。

   特点：元素顺序不同视为不同排列。

2. 组合（Combination）

   指从 n 个不同元素中取出 m 个元素，不考虑顺序的方式数。

   特点：元素顺序不同视为相同组合。

二、核心公式 （需要重点记忆部分）

核心公式

1. 排列数公式（重要 需重点记忆）

• 全排列（m = n）：从 n 个元素中取出 n 个全排列的方式数，记为 $n!$（n 的阶乘）。

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

例如：$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$。

• 选排列（m < n）：从 n 个元素中取出 m 个排列的方式数，记为 $P(n, m)$ 或 $A(n, m)$。

$$P(n, m) = n \times (n-1) \times \dots \times (n-m+1) = \frac{n!}{(n-m)!}$$

计算过程结合阶乘公式转化:

• 阶乘的定义是：对于正整数 n ，$n!=n\times(n - 1)\times(n - 2)\times\cdots\times 2\times 1$ ，并且规定 $0!=1$ 。 观察 $P(n, m)=n\times(n - 1)\times(n - 2)\times\cdots\times(n - m + 1)$ ，分子分母同时乘以 $(n - m)!$ ，即：

$$\begin{align*}P(n, m)&=\frac{[n\times(n - 1)\times(n - 2)\times\cdots\times(n - m + 1)]\times(n - m)!}{(n - m)!}\\ &=\frac{n\times(n - 1)\times(n - 2)\times\cdots\times(n - m + 1)\times(n - m)\times\cdots\times 2\times 1}{(n - m)!}\\ &=\frac{n!}{(n - m)!} \end{align*}$$

例如：从 5 个元素中选 3 个排列，$P(5, 3) = 5 \times 4 \times 3 = 60$。

2. 组合数公式 （重要 需重点记忆）

从 n 个元素中取出 m 个的组合方式数，记为 $C(n, m)$ 或 $\binom{n}{m}$。

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

例如：从 5 个元素中选 3 个组合，$C(5, 3) = \frac{5!}{3!2!} = 10$。

三、重要性质与推论 （暂时不用记忆）

重要性质与推论

1. 组合数的对称性

$$C(n, m) = C(n, n-m)$$

例：$C(7, 2) = C(7, 5) = 21$。

1. 组合数的递推公式（杨辉三角性质）

$$C(n, m) = C(n-1, m-1) + C(n-1, m)$$

适用于通过前一行组合数推导后一行（如杨辉三角第 n 行对应 $C(n, 0)$ 到 $C(n, n)$）。

1. 全组合数之和

   从 n 个元素中取 0 个到 n 个的组合数之和等于 $2^n$，即：

$$\sum_{m=0}^n C(n, m) = 2^n$$

例：n=3 时，$C(3,0)+C(3,1)+C(3,2)+C(3,3) = 1+3+3+1=8=2^3$。

1. 排列与组合的关系

   排列数可看作先选组合再排列：

$$P(n, m) = C(n, m) \times m!$$

四、应用场景举例

案例

1. 排列应用

• 排队问题：5 人排成一列，有 $5! = 120$ 种排法。

• 密码设置：4 位不同数字的密码，有 $P(10, 4) = 5040$ 种可能。

1. 组合应用

• 选小组：从 10 人中选 3 人组成小组，有 $C(10, 3) = 120$ 种选法。

• 扑克牌问题：从 52 张牌中选 5 张，有 $C(52, 5) = 2598960$ 种组合。

1. 综合应用

• 分配问题：将 5 本书分给 3 人，每人至少 1 本，需结合排列与组合（先分组再分配）。

五、扩展：重复元素的排列与组合

扩展知识

1. 重复排列

• n 个元素中有重复元素时，全排列数为：若有 $n_1, n_2, \dots, n_k$ 个相同元素（$n_1 + n_2 + \dots + n_k = n$），则排列数为

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

例：单词 “BOOK” 中字母的排列数为 $\frac{4!}{2!} = 12$（O 重复 2 次）。

1. 重复组合（可重复选取）

• 从 n 个元素中可重复地取 m 个，组合数为

$$C(n + m - 1, m)$$

例：买 3 种水果（可重复），共 5 种水果可选，方案数为 $C(5+3-1, 3) = C(7,3) = 35$。

六、公式记忆技巧

公式记忆技巧

• 排列：先选后排序，分母为 $(n-m)!$。

• 组合：仅选不排序，需除以 $m!$（消除顺序影响）。

• 核心关系：组合是排列的 “去序” 版本，即 $C(n,m) = \frac{P(n,m)}{m!}$。