组合与排列

计算组合数 C(n,r) 与排列数 P(n,r),展示杨辉三角与组合数的对应关系。

C(n,r) = n! / (r! × (n-r)!) — 从 n 个元素中选取 r 个,不考虑顺序
C(5,3) = 10
组合:从 n 个不同元素中取出 r 个元素并成一组,不考虑顺序。例如从 5 人中选 3 人组成小组,有多少种选法?
P(n,r) = n! / (n-r)! — 从 n 个元素中选取 r 个进行排列,考虑顺序
P(5,3) = 60
排列:从 n 个不同元素中取出 r 个元素按一定顺序排成一列。例如从 5 人中选 3 人分别担任班长、副班长、学习委员,有多少种排法?
杨辉三角:每个数等于它上方两数之和。第 n 行第 r 个数(从0开始)正好是 C(n,r)。观察高亮的数字,它等于左边和上方两数之和。

把 n 个元素编号为 1…n,在 n≤8 且 C(n,r)≤56 时,可列出所有 r 元子集(字典序),帮助建立「组合」的直观。

共 C(5,2)=10 种

        
C(n, r) = C(n−1, r−1) + C(n−1, r)

边界:C(n,0)=C(n,n)=1。含义:固定某个元素「选」或「不选」,拆成两类计数相加——这是组合计数里最常见的递推思路。

C(6,3) = C(5,2)+C(5,3) = 10+10 = 20
用户登录
微信客服

返回顶部