TOC

排列与组合

吐槽:现在网上各种讲解,不要太贴心。
要是我读书那会儿有这么多资源,我能上清华(手动狗头)。

计算公式

计算原则:分类相加,分步相乘

排列

从 n 个不同元素中取出 m 个元素,按顺序排成一列

注:英文单词应该是 Permutation 比较通用,但国内基于 Arrangement 采用 A 做简写。

$$\begin{aligned}
A_n^m &= n \times (n - 1) \times (n - 2) \times \cdots \times (n - m + 1) \
&= \frac {n!} {(n - m)!}
\end{aligned}$$

PS: 0 的阶乘等于 1

特殊情况:全排列:$A_n^n$,其排列数等于 n 的阶乘($n!$)

组合

从 n 个不同元素中取出 m 个元素,组成一组

$$\begin{aligned}
C_n^m &= \frac {A_n^m} {A_m^m} = \frac {A_n^m} {m!} \
&= \frac {n!} {m! \cdot (n - m)!}
\end{aligned}$$

可以推导出:

  1. $A_n^m = C_n^m \cdot A_m^m$ 排列就是先组合,再做全排列
  2. $C_n^m = C_n^{n - m}$ 取出 m 个元素就相当于留下 n - m 个元素

举例

来自网上搜到的高考真题,或加上一些改编。

1、6 个男医生,5 个女医生,选 2 个男医生,1 个女医生,有多少中组合?

$C_6^2 \cdot C_5^1 = ((6 \times 5) \div 2) * 5 = 75$

再加一条:去 8 个社区驻点,有几种分派方式?再乘一个 $A_8^5$

2、6 把椅子,3 个人随机坐,两人不能相邻,有多少种坐法?

1 2 3 4 5 6 三个人都不能相邻的话,至少需要占 5 把椅子,相当于多一把椅子,可以插在任意位置,稍微一想,有 6 种可能。
然后就是简单的三个人的排序问题了。

$A_3^3 \cdot 6 = 36$

编程实现

import math
from scipy.special import comb, perm

print(perm(10, 6)) # 151200.0
# 10 * 9 * 8 * 7 * 6 * 5 = 151200
(lambda n, m: math.factorial(n) / math.factorial(n - m))(10, 6)

print(comb(10, 6)) # 210.0
# 6! => math.factorial(6)
# 151200 / math.factorial(6) = 210.0
(lambda n, m: math.factorial(n) / (math.factorial(n - m) * math.factorial(m)))(10, 6)

如果能用上 SymPy 相比会更有意思。