排列组合
什么是排列与组合？
排列（Permutation）与组合（Combination）是组合数学中两个最基本的计数概念。它们的核心区别只有一个：顺序是否重要。
排列（Permutation）：顺序重要。想象你在书架上摆放 3 本书——《红楼梦》、《西游记》、《三国演义》。从左到右的排列"红-西-三"和"三-西-红"是完全不同的两种摆法。从 n 个物品中选取 r 个并排列，总方案数记作 P(n,r) 或 A(n,r)。
组合（Combination）：顺序不重要。假设你从 10 个同学中选 3 人组成篮球小组，选出"张三、李四、王五"与选出"王五、李四、张三"是同一个小组。从 n 个物品中选取 r 个（不考虑顺序），总方案数记作 C(n,r) 或 (nr)。
直觉记忆法
排列 = 安排座位（谁坐哪个位置很重要）
组合 = 挑队员（谁先被选不重要，只要最终名单一样）
由此可以推出一个关键关系：C(n,r) = P(n,r) / r!。因为同样一组 r 个物品可以有 r! 种不同排列，组合只计一次。
这两个概念最早可以追溯到古印度数学家 Mahavira（约 850 年）和中国宋代数学家贾宪（约 1050 年）。欧洲方面，Blaise Pascal（帕斯卡）和 Pierre de Fermat（费马）在 1654 年的通信中奠定了现代组合数学的基础。
阶乘 (n!)
阶乘是排列组合计算的基石。n 的阶乘定义为从 1 到 n 所有正整数的乘积：
例如：5! = 1 × 2 × 3 × 4 × 5 = 120。
谁发明了 "!" 符号？
感叹号记法由法国数学家 Christian Kramp 在 1808 年引入。在此之前，阶乘的表示方法五花八门，没有统一标准。Kramp 选择 "!" 的原因可能很简单：它简短、醒目、不容易与其他数学符号混淆。
为什么 0! = 1？
这是一个常见疑问。0! = 1 并非"计算"得出的结果，而是一个约定（convention），基于以下理由：
- 空乘积原则：数学中，零个数相乘的结果定义为乘法单位元 1（类似于零个数相加的结果为 0）。
- 使公式自洽：例如 C(n,0) = n! / (0! × n!) = 1（从 n 个物品中选 0 个只有一种方式——什么都不选），这在直觉上完全合理。
- 递推关系：n! = n × (n-1)!。令 n=1 得 1! = 1 × 0!，所以 0! = 1。
Stirling 近似公式
当 n 很大时，直接计算 n! 几乎不可能（170! 已经超出双精度浮点数范围）。苏格兰数学家 James Stirling（1730）和法国数学家 Abraham de Moivre 提出了一个优美的近似公式：
为什么有用？在统计力学、信息论和算法复杂度分析中，我们经常需要处理 log(n!)。Stirling 公式给出 log(n!) ≈ n log n − n，这使得理论推导变得可行。例如，排序算法的下界证明（Ω(n log n)）就依赖于此。
Stirling 近似精度
n 越大，相对误差越小，趋近于 1/(12n)。
排列 — P(n,r)
排列回答的问题是：从 n 个不同物品中，选 r 个并排列（考虑顺序），有多少种方法？
为什么是这个公式？
用"逐步填坑"的方式理解最直观：
第 2 个位置：剩下 n−1 种选择
第 3 个位置：剩下 n−2 种选择
…
第 r 个位置：剩下 n−r+1 种选择
总数 = n × (n−1) × (n−2) × … × (n−r+1) = n!/(n−r)!
例：3 本书排在书架上
有重复排列 — nr
如果允许重复选取（放回），每个位置都有 n 种选择，互不影响。
为什么？因为每个位置的选择是独立的。第 1 个位置有 n 种选择，第 2 个位置也有 n 种选择（因为第 1 个选过的还可以再选），以此类推。这就是乘法原理的直接应用。
现实例子：4 位数字密码（0–9），每位可以重复 → 104 = 10,000 种可能。
多重集排列 — "MISSISSIPPI" 问题
如果 n 个物品中有些是相同的，排列数需要除去因相同物品互换而导致的重复计数。
经典例题："MISSISSIPPI" 的排列数
为什么要除？4 个 I 互相交换不产生新排列（你无法区分它们），所以要除以 4! 消除这些"虚假"排列；S 和 P 同理。
组合 — C(n,r)
组合回答的问题是：从 n 个不同物品中，选 r 个（不考虑顺序），有多少种方法？
为什么 C(n,r) = P(n,r) / r!？
但组合只关心"选了谁"，不关心顺序。
同一组 r 个物品有 r! 种排列方式。
所以组合数 = 排列数 / r! = P(n,r) / r! = n! / (r!(n-r)!)
例：从 5 人中选 2 人组队
帕斯卡三角 (杨辉三角)
帕斯卡三角是组合数的一个优美的几何表示，满足递推关系：
为什么？考虑第 n 个物品：要么选它（对应 C(n-1, r-1)，即从剩余 n-1 个中再选 r-1 个），要么不选它（对应 C(n-1, r)，即从剩余 n-1 个中选够 r 个）。这两种情况互斥且穷尽。
第 n 行第 r 列 = C(n,r)。例如高亮的 6 = C(4,2)。
历史：不叫"帕斯卡三角"更公平
虽然西方称之为"帕斯卡三角"（Pascal's Triangle, 1654），但这个结构在更早的东方文献中就已出现：
- 贾宪（约 1050 年，北宋）：在《释锁算术》中首次给出此三角，用于开高次方。
- 杨辉（1261 年，南宋）：在《详解九章算法》中引用贾宪的三角，因此中文世界称之为"杨辉三角"。
- Omar Khayyam（约 1100 年，波斯）：也独立发现了此结构。
- Blaise Pascal（1654 年，法国）：系统研究了这个三角的数学性质，并将其与概率论联系起来。
有重复组合 — Stars and Bars
如果允许重复选取，从 n 种物品中选 r 个的方案数为：
这个公式也叫"隔板法"或 Stars and Bars（由美国概率学家 William Feller 在 1950 年的经典教材中推广）。
直觉理解：想象 r 颗星星（★）和 n−1 个隔板（|）排成一排，隔板把星星分成 n 组，每组代表某种物品被选了几个。例如从 3 种水果中选 4 个：★★|★|★ 表示"2 个苹果、1 个橙子、1 个香蕉"。总共 r + n − 1 个位置中选 r 个放星星（或 n−1 个放隔板），方案数 = C(n+r−1, r)。
二项式定理
二项式定理将 (a + b)n 展开为一个求和式，其系数恰好是组合数：
为什么系数是 C(n,k)？
展开时，从每个因式中选 a 或 b。
要得到 an−kbk 项，需要从 n 个因式中选 k 个贡献 b（其余贡献 a）。
从 n 个中选 k 个的方法数 = C(n,k)。
所以 an−kbk 的系数就是 C(n,k)。
例：(a + b)4 的展开
牛顿的推广
Isaac Newton（1665 年，时年仅 22 岁）将二项式定理推广到了非整数和负数指数的情况。对于任意实数 α：
其中广义二项式系数 C(α,k) = α(α−1)(α−2)…(α−k+1) / k!。这使得我们能够展开 √(1+x)、1/(1+x)2 等表达式，是微积分和级数理论的重要工具。
实际应用
排列组合不只是课本上的抽象概念——它们在现实世界中无处不在。
🎰 彩票概率
6/49 彩票：从 49 个数字中选 6 个（顺序无关）。中奖概率 = 1/C(49,6) = 1/13,983,816 ≈ 0.00000715%。你被闪电击中的概率（约 1/500,000）都比这高 28 倍。
🃏 扑克牌
从 52 张牌中发 5 张手牌：C(52,5) = 2,598,960 种可能。皇家同花顺只有 4 种（每种花色一个），概率 = 4/2,598,960 ≈ 1/649,740。
👥 委员会选举
从 20 人中选 5 人委员会：C(20,5) = 15,504 种方案。如果再从 5 人中选出主席、副主席、秘书：P(5,3) = 60 种。总方案数 = 15,504 × 60 = 930,240。
🔐 密码安全
4 位 PIN（0–9）：104 = 10,000 种（有重复排列）。8 位混合密码（大小写+数字，62 种字符）：628 ≈ 2.18 × 1014。密码长度每增加 1 位，暴力破解时间增长 62 倍。
🧬 DNA / 蛋白质序列
DNA 由 4 种碱基（A, T, C, G）组成。长度 n 的序列有 4n 种可能。人类基因组约 32 亿碱基对，理论可能序列数 = 43.2×10⁹——一个天文数字。蛋白质由 20 种氨基酸组成，长 100 的蛋白质有 20100 ≈ 10130 种可能序列。
💻 算法复杂度
旅行商问题 (TSP) 需要检查 n 个城市的所有排列：(n−1)!/2 条回路。20 个城市就有 ≈ 6 × 1016 种——正是排列的"组合爆炸"使得暴力求解不可行，推动了动态规划和启发式算法的发展。
常见错误
即使理解了公式，应用时仍然容易犯错。以下是最常见的陷阱：
错误 1：混淆排列与组合
✗ "从 10 人中选 3 人组队，用 P(10,3) = 720"
✓ 组队不考虑顺序，应用 C(10,3) = 120
判断准则：问自己"如果交换被选中者的顺序，结果是否不同？"如果不同，用排列；如果相同，用组合。
错误 2：忽略"有重复"与"无重复"的区别
✗ "3 位数字密码（0–9），用 P(10,3) = 720"
✓ 数字可重复使用，应用 10³ = 1,000
判断准则：选过的物品还能不能再选？能 → 有重复；不能 → 无重复。
错误 3：多重集排列忘记除以重复因子
✗ "AABB 的排列数 = 4! = 24"
✓ 有重复字母，应为 4!/(2!×2!) = 6
六种排列：AABB, ABAB, ABBA, BAAB, BABA, BBAA。
错误 4：r > n 时使用无重复排列/组合公式
✗ "从 5 种颜色中选 8 个（可重复），用 C(5,8)"——C(5,8) 未定义！
✓ 有重复组合，应用 C(5+8-1, 8) = C(12,8) = 495
相关工具
如果你在使用排列组合，以下工具可能对你也有帮助：
FAQ
核心区别在于顺序是否重要。排列（Permutation）考虑顺序，因此 ABC 和 BCA 是不同的排列。组合（Combination）不考虑顺序，{A,B,C} 和 {C,A,B} 是同一个组合。公式关系：C(n,r) = P(n,r) / r!，即组合比排列少了 r! 倍（因为消除了 r 个元素的内部排列）。
0! = 1 是一个数学约定，基于三个理由：(1) 空乘积原则——零个数相乘的结果是乘法单位元 1；(2) 递推关系 n! = n × (n-1)! 在 n=1 时要求 0! = 1；(3) 使组合公式自洽——C(n,0) = n!/(0! × n!) = 1，即"从 n 个物品中选 0 个只有一种方式：什么都不选"。
本计算器使用 JavaScript BigInt，可以精确计算任意大小的整数阶乘。但实际上，当 n 超过约 10,000 时，计算时间会显著增加。在科学计算中，170! 是双精度浮点数（64 位 float）能表示的最大阶乘（约 7.26 × 10306）。超过这个范围需要使用大整数库或 Stirling 近似。
问自己两个问题：(1) 顺序重要吗？如果"选 A 再选 B"和"选 B 再选 A"是不同结果（如密码、座位安排），用排列。如果是同一结果（如选团队、抽奖），用组合。(2) 能重复选吗？如果可以重复，使用"有重复"公式（排列：nr；组合：C(n+r-1,r)）。如果不能重复，使用标准公式（P(n,r) 或 C(n,r)）。
帕斯卡三角中隐藏着大量数学规律：(1) 对称性：C(n,r) = C(n, n−r)，每行左右对称。(2) 行和：第 n 行所有数之和 = 2n（因为 (1+1)n = 2n）。(3) 斐波那契数列：沿对角线求和可以得到斐波那契数。(4) 素数判定：第 p 行（p 为素数）的所有中间元素都能被 p 整除。(5) Sierpinski 三角：将奇数染色、偶数不染色，会出现分形图案。