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

韩曙亮

发布于 2023-03-28 18:13:31

2.4K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

参考博客 :

一、排列组合内容概要

排列组合内容概要 :

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

二、选取问题

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)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

集合

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

集合

数学

登录后参与评论

0 条评论

热度