组合数学 排列和组合 一

排列 permutation

或者

基本模型就是放球模型. 从 n 个取出 r 个不同的盒子里(盒子有顺序)

全排列

排列组合的递推关系 第一个关系:

第二个关系: 取第一个球 n种可能 乘以 n-1个球 * r-1个盒子 不取第一个球则是 n-1个球 * r个盒子

组合

就是全排列 除以 r的全排列

n 个球选出 r 个自然就等于剩下的 n - r 个方法

组合模型(分析的话结合选班委的案例)

举例: 由于

所以

分析: 4个球中取5个做组合的方案有0种

= 0

隔路模型

和组合相关 c(m+n, n) 就是(0,0) 移动到(m, n)点

组合恒等式

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

C(m+n, r) = C(m, 0)C(n, r) + C(m, 1)C(n, r-1) + ... + C(m, r)C(n, 0)

圆排列

从 n 个中取出 r 个, 排列数等于

相当于全排列中出去r个可以裁剪的位置

八卦图是圆排列, 它的个数为 8! / 8

项链排列

从 n 个中取出 r 个, 排列数等于

相当于在圆排列的基础上再考虑翻转这种情况.

多重排列

pingpang 8个字母能有多少种排列

无重排列 再去重. 我们有若干个元素, r1个1, r2个2, ... rt个t, 元素个数之和为t, 那么它的全排列被记为:

二项式定理:

多项式定理:

举例: 乒乓球入洞问题 编号1~9的球分别进入6个洞口, 有多少种入洞的方案.

可重组合

在

中取出 r 个元素

, 且允许