【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )

2023-03-28 18:13:31 浏览数 (1)

文章目录

  • 一、排列组合内容概要
  • 二、选取问题
  • 三、集合排列
  • 四、环排列
  • 五、集合组合

参考博客 :

  • 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
  • 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )

一、排列组合内容概要

排列组合内容概要 :

  • 选取问题
  • 集合的排列与组合问题
  • 基本计数公式应用
  • 多重集的排列与组合问题

二、选取问题

n

元集

S

, 从

S

集合中选取

r

个元素 ;

根据 元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :

元素不重复

元素可以重复

有序选取

集合排列 P ( n , r ) P(n,r) P(n,r)

多重集排列

无序选取

集合组合 C ( n , r ) C(n,r) C(n,r)

多重集组合

P(n,r)

多重集排列无序选取集合组合

C(n,r)

多重集组合

选取问题中 :

  • 不可重复的元素 , 有序的选取 , 对应 集合的排列
  • 不可重复的元素 , 无序的选取 , 对应 集合的组合
  • 可重复的元素 , 有序的选取 , 对应 多重集的排列
  • 可重复的元素 , 无序的选取 , 对应 多重集的组合

三、集合排列

n

元集

S

, 从

S

集合中 有序 , 不重复 选取

r

个元素 ,

该操作称为

S

集合的一个

r-

排列 ,

S

集合的

r-

排列记作

P(n, r)
P(n,r)=begin{cases} dfrac{n!}{(n-r)!} & n geq r \\ 0 & n < r end{cases}

该排列公式使用乘法法则得到 : 将整个排列看做

r

个位置

  • 第
1

个位置有

n

种放置方法 , 即从当前的

n

个元素中任选一个 , 剩下

n-1

个元素 ;

  • 第
2

个位置有

n-1

种放置方法 , 即从当前的

n-1

个元素中任选一个 , 剩下

n-2

个元素 ;

  • 第
3

个位置有

n-2

种放置方法 , 即从当前的

n-2

个元素中任选一个 , 剩下

n-3

个元素 ;

vdots
  • 第
r

个位置有

n-(r-1) = n - r 1

种放置方法 , 即从当前的

n - r 1

个元素中任选一个 , 剩下

n-r

个元素 ;

0! = 1

四、环排列

n

元集

S

, 从

S

集合中 有序 , 不重复 选取

r

个元素 ,

S

集合的

r-

环排列数

= dfrac{P(n,r)}{r} = dfrac{n!}{r (n-r)!}
r

个不同的线性排列 , 相当于同一个环排列 ;

一个环排列 , 从任意位置剪开 , 可以构成

r

种不同的线性排列 ;

五、集合组合

n

元集

S

, 从

S

集合中 无序 , 不重复 选取

r

个元素 ,

该操作称为

S

集合的一个

r-

组合 ,

S

集合的

r-

组合记作

C(n, r)
C(n,r)=begin{cases} dfrac{P(n,r)}{r!} = dfrac{n!}{r!(n-r)!} & n geq r \\ 0 & n < r end{cases}
r-

排列也可以这样理解 ( 先组合后排列 ) : 选出

r

个有序的排列

C(n,r)

, 可以先将其

r

个无序的选择做出来 , 然后再对选择好的元素进行全排列

C(n,r) r! = P(n,r)

;

组合恒等式 :

C(n,r) = C(n, n-r)
博客 集合 数学

0 人点赞