排列组合
又称:排列数、组合数、A(n,r)、C(n,r)
排列和组合都是「从 n 个物体里取出 r 个」的计数方法,唯一的区别是讲不讲顺序。排列讲顺序,比如给三名选手排金银铜牌;组合不讲顺序,比如从三名选手里挑两人组队。记法是排列数 A(n,r)(也写 P(n,r))、组合数 C(n,r)。
算排列 A(n,r):第 1 个位置有 n 种选法、第 2 个 n−1 种,一直选到第 r 个,连乘 r 个递减的因子,即 A(n,r) = n! ÷ (n−r)!。算组合 C(n,r) 时不在乎顺序——同样 r 个物体,排列把它们的 r! 种不同排序都算作不同,而组合视为同一种,所以只要把排列数除以 r! 消掉这些重复顺序,就得到组合数:C(n,r) = A(n,r) ÷ r! = n! ÷ [r!·(n−r)!]。这就是 A = C × r! 的由来。
举个例子:从 10 个人里取 3 个。如果要排名次(排列),A(10,3) = 10×9×8 = 720;如果只组队(组合),C(10,3) = 720 ÷ 3! = 720 ÷ 6 = 120。如果允许重复选取(同一物体可选多次),情况不同:可重复排列每步都有 n 种选择,共 nʳ 种;可重复组合用「隔板法」得到 C(n+r−1, r)。一个实用记忆:C(n,r) = C(n,n−r),取 r 个等价于「留下 n−r 个」,选较小的那边算更快。排列组合是概率和统计的基础。