【组合数学】排列组合 ( 两个计数原则、集合排列示例 | 集合排列、圆排列示例 )

韩曙亮

发布于 2023-03-28 18:15:52

1.1K0

发布于 2023-03-28 18:15:52

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

文章目录

排列组合参考博客 :

一、两个计数原则、集合排列示例

排列

26

个字母 , 使得

a,b

之间有

7

个字母 , 求排列方法数 ;

需要使用分类计数原理 ( 加法原则 ) , 分步计数原理 ( 乘法原则 ) ;

分类计数 ( 加法原则 ) : 有

3

类方案 , 第一类有

2

个方案 , 第二类有

4

个方案 , 第三类有

1

个方案 , 总共有

2 + 4 + 1 = 7

个方案 ;

分步计数原理 ( 乘法原则 ) : 有

3

类方案 , 第一步有

2

个方案 , 第二步有

4

个方案 , 第三步有

1

个方案 , 总共有

2 \times 4 \times 1 = 8

个方案 ;

1. 首先使用分步计数原理 ,

第一步 : 先构造出以

a,b

为边界 , 中间含有

7

个字母的子结构 ;

第二步 : 将

a,b

子结构作为元素 , 与其它

26-9 = 17

个子元素一起 , 总共

18

个元素进行全排列 ;

分步计数原理对应乘法法则 , 最终结果是第一步的方案个数乘以第二步的方案个数 ;

2. 第一步计算 : 先构造出以

a,b

为边界 , 中间含有

7

个字母的子结构 ;

该子结构中的

7

个字母 , 相当于从除

a,b

之外的其它

24

个字母中选取

7

个字母进行排列 ,

一一对应 : 相当于元素不重复的集合中 , 进行有序选取 , 对应着集合的排列问题 , 使用集合排列公式进行计算 ;

24

个字母中选取

7

个字母进行排列 , 选取方法有

P(24, 7)

种 ;

这里涉及到分类计数原理 ,

第一类是

a

在前 ,

b

在后的情况 , 选取方法有

P(24, 7)

种 ;

第二类是

b

在前 ,

a

在后的情况 , 选取方法有

P(24, 7)

种 ;

分类计数原理对应加法法则 , 总的方法数是第一类与第二类相加之和 , 选取方法有

2\ P(24, 7)

种 ;

3. 第二步计算 : 将

a,b

子结构作为元素 , 与其它

26-9 = 17

个子元素一起 , 总共

18

个元素进行全排列 ;

18

个元素进行全排列 , 结果是

18!

;

4. 第一步方案乘以第二步方案 ( 分步计算原理加法法则 ) :

第一步的方案个数乘以第二步的方案个数 ;

N = 2\ P(24, 7) \ 18!

二、集合排列、圆排列示例

10

个男生 ,

5

个女生, 站成一排 , 如果没有女生相邻 , 有多少种方法 ? 如果站成一圈 , 有多少种方法 ?

需要使用分类计数原理 ( 加法原则 ) , 分步计数原理 ( 乘法原则 ) ;

分类计数 ( 加法原则 ) : 有

3

类方案 , 第一类有

2

个方案 , 第二类有

4

个方案 , 第三类有

1

个方案 , 总共有

2 + 4 + 1 = 7

个方案 ;

分步计数原理 ( 乘法原则 ) : 有

3

类方案 , 第一步有

2

个方案 , 第二步有

4

个方案 , 第三步有

1

个方案 , 总共有

2 \times 4 \times 1 = 8

个方案 ;

1.

10

个男生 ,

5

个女生, 站成一排 , 如果没有女生相邻 , 有多少种方法 :

需要使用分步处理 : 先把男生放好 , 然后将女生插空放进去 ;

① 第一步 : 先把男生放好 , 男生

10

个 , 站好以后有

11

个格子 ;

10

个男生的放置位置 , 元素不重复的有序选取 , 这是集合排列问题 , 排列方案有

P(10,10) = 10!

个方案 ;

② 第二步 : 然后将女生插空放进去 ,

5

个女生只能放在这

11

个格子中 ;

11

个格子中放

5

个女生 , 元素不重复的有序选取 , 这是集合的排列问题 , 排列方案有

P(11, 5)

③ 分步计数原理 ( 乘法原则 ) : 将第一步方案数与第二步方案数相乘 , 方案个数是 :

P(10,10) \ P(11, 5)

2.

10

个男生 ,

5

个女生, 站成一圈 , 如果没有女生相邻 , 有多少种方法 :

需要使用分步处理 : 先把男生放好 , 然后将女生插空放进去 ;

① 第一步 : 先把男生放好排成一圈 , 男生

10

个 , 因为是排成一圈 , 因此站好以后只有

10

个格子 ;

10

个男生的放置位置 , 元素不重复的有序选取 , 这是集合圆排列问题 , 需要使用圆排列公式 , 排列方案有

\cfrac{P(10,10)}{10}

个方案 ;

参考 : 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 ) 四、环排列

n

元集

S

, 从

S

集合中有序 , 不重复选取

r

个元素 ,

S

集合的

r-

环排列数

= \dfrac{P(n,r)}{r}

r

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

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

r

种不同的线性排列 ;

② 第二步 : 然后将女生插空放进去 ,

5

个女生只能放在这

10

个格子中 ;

10

个格子中放

5

个女生 , 元素不重复的有序选取 , 这是集合的排列问题 , 排列方案有

P(10, 5)

③ 分步计数原理 ( 乘法原则 ) : 将第一步方案数与第二步方案数相乘 , 方案个数是 :

\cfrac{P(10,10)}{10} \ P(10, 5)

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

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

博客

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

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

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

登录后参与评论

0 条评论

热度