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 个排成顺序：
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)整数实现要安排约分或使用大整数，避免中间溢出和浮点舍入。
二项式定理
展开 (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 个不同对象围成一圈，若只把整体旋转视为同一种排列：
(n-1)!因为固定一个对象作为起点，消去 n 种旋转重复。
若镜像也视为相同，还要进一步除以 2，但小规模和额外对称可能需要单独检查。一般对称计数不能随意“看有几个对称就除几”，需要保证每个等价类大小一致，或使用 Burnside 引理。
满射计数
把 m 个有标签任务分给 n 个有标签工作节点，并要求每个节点至少一个任务，相当于计算从 m 元集合到 n 元集合的满射。
用容斥：
Σ_{k=0..n} (-1)^k C(n,k)(n-k)^m先数全部 n^m 个函数，再减去至少空一个指定节点的分配，加回同时空两个节点的分配，依次进行。
完成检查
分别计算并说明模型：
- 8 位数字 PIN，允许重复和前导零；
- 10 人选班长、副班长、委员各一人；
- 10 人选 3 人小组；
- 12 个相同任务分给 4 个有标签节点，允许空节点；
- 同上但每个节点至少 1 个；
MISSISSIPPI的不同字母排列数。