6.2 排列、组合与重复选择：顺序和重复是否重要
“从 10 个数字选 4 位密码有多少种”没有唯一答案：能否重复？首位能否为零？1234 和 4321 是否不同？组合公式之前必须先回答这些问题。
四个基础模型
| 模型 | 顺序 | 可重复 | 数量 |
|---|---|---|---|
| 长度 r 的序列 | 重要 | 可以 | n^r |
| r-排列 | 重要 | 不可以 | n!/(n-r)! |
| r-组合 | 不重要 | 不可以 | C(n,r) |
| r-重组合 | 不重要 | 可以 | C(n+r-1,r) |
先选模型，再代公式。
这里 n,r 为非负整数，阶乘比要求 0≤r≤n；不放回却选超过 n 个时，数量为 0。重组合的隔板公式要求 n≥1。从零种类型选零个有一种空选择，选正数个则有零种，需要单独处理。
排列：有序且不放回
从 n 个不同元素中选 r 个排成顺序：
P(n,r)=n(n-1)...(n-r+1)=n!/(n-r)!十个数字中取四个且不重复，允许首位为零，并把结果视作长度 4 的代码：
P(10,4)=10×9×8×7=5040若要求真正的四位十进制数，首位不能为零：
9×9×8×7=4536若允许重复，则长度 4 的代码有 10⁴ 个；真正四位数有 9×10³ 个。
全排列与重复元素
n 个不同元素全排列：
n!若有重复元素，交换相同元素不会产生新序列。含 n₁,...,n_k 个相同类别，总长度 n：
n!/(n₁!n₂!...n_k!)单词 LEVEL 有 5 个字母，L 两个、E 两个：
5!/(2!2!)=30该公式假设只按字符序列区分结果；若字符实例还有隐藏身份，模型会变化。
组合：无序且不放回
从 n 个不同元素中选 r 个子集：
C(n,r)=n!/[r!(n-r)!]推导：先数有序选择 P(n,r)，每个无序子集的 r! 个排列都被重复计数：
C(n,r)=P(n,r)/r!对称性：
C(n,r)=C(n,n-r)选择 r 个元素，等价于决定哪 n-r 个不选。
Pascal 恒等式
固定一个特殊元素 x，大小为 r 的子集分两类：
- 包含
x：从余下n-1个选r-1个； - 不包含
x：从余下n-1个选r个。
因此：
C(n,r)=C(n-1,r-1)+C(n-1,r)这既是组合证明，也是 Pascal 三角的递推。用动态规划计算整行组合数时可利用它；若只求单个 C(n,r)，可采用乘除交替的算法，避免先算巨大阶乘：
C(n,r)=∏_{i=1..r} (n-r+i)/i，取 r=min(r,n-r)整数实现要安排约分或使用大整数，避免中间溢出和浮点舍入。
Python 3 使用任意精度整数，下面按步先乘后整除。第 i 次循环后，value=C(n-r+i,i)，因此本步骤的除法恰好整除；不能先把每个分数单独向下取整：
def choose(n, r):
if n < 0 or r < 0:
raise ValueError("nonnegative integer inputs required")
if r > n:
return 0
r = min(r, n - r)
value = 1
for i in range(1, r + 1):
value = value * (n - r + i) // i
return value
print(choose(10, 3)) # 120
print(choose(0, 0)) # 1
print(choose(3, 4)) # 0
print(choose(100, 50)) # 100891344545564193334812497256日常代码可直接使用 Python 3.8+ 的 math.comb。大整数避免溢出，但位数增长仍增加计算与存储成本。
二项式定理
展开 (x+y)^n 时，从 n 个因子中选择 r 个取 y，其余取 x：
(x+y)^n=Σ_{r=0..n} C(n,r)x^(n-r)y^r令 x=y=1：
Σ_{r=0..n} C(n,r)=2^n左边按子集大小分类统计幂集，右边按每个元素选或不选统计。两种计数同一对象，得到恒等式。
重组合与隔板法
从 n 种类型中选 r 个，允许重复且不计顺序，相当于求非负整数解：
x₁+x₂+...+x_n=r用 r 个星和 n-1 个隔板编码：
***|*||**表示四种类型计数 (3,1,0,2)。总位置 r+n-1，选择 n-1 个隔板位置：
C(r+n-1,n-1)=C(r+n-1,r)若每类至少一个，先给每类分一个，剩余 r-n 个：
C(r-1,n-1)，前提 r≥n若有上界 x_i≤u_i，简单隔板法不再直接适用，可用容斥或生成函数。
圆排列与对称性
n≥1 个不同对象围成一圈，若只把整体旋转视为同一种排列：
(n-1)!因为固定一个对象作为起点，消去 n 种旋转重复。
若镜像也视为相同，对 n≥3 个各不相同对象，数量为 (n−1)!/2；n=1,2 时都只有一种，不能再除以 2。若允许重复颜色等额外对称，每个等价类的大小可能不同，需要检查群作用，或用 Burnside 引理。
满射计数
把 m 个有标签任务分给 n 个有标签工作节点，并要求每个节点至少一个任务，相当于计算从 m 元集合到 n 元集合的满射。
用容斥：
Σ_{k=0..n} (-1)^k C(n,k)(n-k)^m先数全部 n^m 个函数，再减去至少空一个指定节点的分配，加回同时空两个节点的分配，依次进行。
下例用 Python 3.8+，假设 m,n 都是非负整数。4 个有标签任务分给 3 个节点且不留空节点，共 36 种；独立枚举也给出同一结果。空集合边界采用计数约定 0^0=1：
from math import comb
from itertools import product
def onto_count(m, n):
return sum((-1)**k * comb(n, k) * (n - k)**m for k in range(n + 1))
m, n = 4, 3
by_enumeration = sum(len(set(outputs)) == n
for outputs in product(range(n), repeat=m))
print(onto_count(m, n), by_enumeration) # 36 36
print(onto_count(0, 0), onto_count(0, 2), onto_count(2, 0)) # 1 0 0完成检查
分别计算并说明模型：
- 8 位数字 PIN，允许重复和前导零；
- 10 人选班长、副班长、委员各一人；
- 10 人选 3 人小组；
- 12 个相同任务分给 4 个有标签节点，允许空节点；
- 同上但每个节点至少 1 个；
MISSISSIPPI的不同字母排列数。