文章目录
- 一、两个计数原则、集合排列示例
- 二、集合排列、圆排列示例
排列组合参考博客 :
- 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
- 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
- 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
- 【组合数学】排列组合 ( 排列组合示例 )
- 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )
- 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )
- 【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题 | 不定方程非负整数解问题 )
一、两个计数原则、集合排列示例
排列
26
26
26 个字母 , 使得
a
,
b
a,b
a,b 之间有
7
7
7 个字母 , 求排列方法数 ;
需要使用 分类计数原理 ( 加法原则 ) , 分步计数原理 ( 乘法原则 ) ;
-
分类计数 ( 加法原则 ) : 有
3
3
3 类方案 , 第一类有
2
2
2 个方案 , 第二类有
4
4
4 个方案 , 第三类有
1
1
1 个方案 , 总共有
2
+
4
+
1
=
7
2 + 4 + 1 = 7
2+4+1=7 个方案 ;
-
分步计数原理 ( 乘法原则 ) : 有
3
3
3 类方案 , 第一步有
2
2
2 个方案 , 第二步有
4
4
4 个方案 , 第三步有
1
1
1 个方案 , 总共有
2
×
4
×
1
=
8
2 \times 4 \times 1 = 8
2×4×1=8 个方案 ;
1. 首先使用分步计数原理 ,
-
第一步 : 先构造出以
a
,
b
a,b
a,b 为边界 , 中间含有
7
7
7 个字母的子结构 ;
-
第二步 : 将
a
,
b
a,b
a,b 子结构作为元素 , 与其它
26
−
9
=
17
26-9 = 17
26−9=17 个子元素一起 , 总共
18
18
18 个元素进行全排列 ;
分步计数原理对应乘法法则 , 最终结果是 第一步的方案个数 乘以 第二步的方案个数 ;
2. 第一步计算 : 先构造出以
a
,
b
a,b
a,b 为边界 , 中间含有
7
7
7 个字母的子结构 ;
该子结构中的
7
7
7 个字母 , 相当于从除
a
,
b
a,b
a,b 之外的其它
24
24
24 个字母中选取
7
7
7 个字母进行排列 ,
一一对应 : 相当于元素不重复的集合中 , 进行有序选取 , 对应着集合的排列问题 , 使用集合排列公式进行计算 ;
24
24
24 个字母中选取
7
7
7 个字母进行排列 , 选取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 种 ;
这里涉及到分类计数原理 ,
-
第一类是
a
a
a 在前 ,
b
b
b 在后的情况 , 选取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 种 ;
-
第二类是
b
b
b 在前 ,
a
a
a 在后的情况 , 选取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 种 ;
分类计数原理对应加法法则 , 总的方法数是 第一类 与 第二类 相加之和 , 选取方法有
2
P
(
24
,
7
)
2\ P(24, 7)
2 P(24,7) 种 ;
3. 第二步计算 : 将
a
,
b
a,b
a,b 子结构作为元素 , 与其它
26
−
9
=
17
26-9 = 17
26−9=17 个子元素一起 , 总共
18
18
18 个元素进行全排列 ;
18
18
18 个元素进行全排列 , 结果是
18
!
18!
18! ;
4. 第一步方案 乘以 第二步方案 ( 分步计算原理 加法法则 ) :
第一步的方案个数 乘以 第二步的方案个数 ;
N
=
2
P
(
24
,
7
)
18
!
N = 2\ P(24, 7) \ 18!
N=2 P(24,7) 18!
二、集合排列、圆排列示例
10
10
10 个男生 ,
5
5
5 个女生, 站成一排 , 如果没有女生相邻 , 有多少种方法 ? 如果站成一圈 , 有多少种方法 ?
需要使用 分类计数原理 ( 加法原则 ) , 分步计数原理 ( 乘法原则 ) ;
-
分类计数 ( 加法原则 ) : 有
3
3
3 类方案 , 第一类有
2
2
2 个方案 , 第二类有
4
4
4 个方案 , 第三类有
1
1
1 个方案 , 总共有
2
+
4
+
1
=
7
2 + 4 + 1 = 7
2+4+1=7 个方案 ;
-
分步计数原理 ( 乘法原则 ) : 有
3
3
3 类方案 , 第一步有
2
2
2 个方案 , 第二步有
4
4
4 个方案 , 第三步有
1
1
1 个方案 , 总共有
2
×
4
×
1
=
8
2 \times 4 \times 1 = 8
2×4×1=8 个方案 ;
1.
10
10
10 个男生 ,
5
5
5 个女生, 站成一排 , 如果没有女生相邻 , 有多少种方法 :
需要使用分步处理 : 先把男生放好 , 然后将女生插空放进去 ;
① 第一步 : 先把男生放好 , 男生
10
10
10 个 , 站好以后有
11
11
11 个格子 ;
10
10
10 个男生的放置位置 , 元素不重复的有序选取 , 这是集合排列问题 , 排列方案有
P
(
10
,
10
)
=
10
!
P(10,10) = 10!
P(10,10)=10! 个方案 ;
② 第二步 : 然后将女生插空放进去 ,
5
5
5 个女生只能放在这
11
11
11 个格子中 ;
11
11
11 个格子中放
5
5
5 个女生 , 元素不重复的有序选取 , 这是集合的排列问题 , 排列方案有
P
(
11
,
5
)
P(11, 5)
P(11,5)
③ 分步计数原理 ( 乘法原则 ) : 将 第一步方案数 与 第二步方案数 相乘 , 方案个数是 :
P
(
10
,
10
)
P
(
11
,
5
)
P(10,10) \ P(11, 5)
P(10,10) P(11,5)
2.
10
10
10 个男生 ,
5
5
5 个女生, 站成一圈 , 如果没有女生相邻 , 有多少种方法 :
需要使用分步处理 : 先把男生放好 , 然后将女生插空放进去 ;
① 第一步 : 先把男生放好排成一圈 , 男生
10
10
10 个 , 因为是排成一圈 , 因此站好以后只有
10
10
10 个格子 ;
10
10
10 个男生的放置位置 , 元素不重复的有序选取 , 这是集合圆排列问题 , 需要使用圆排列公式 , 排列方案有
P
(
10
,
10
)
10
\cfrac{P(10,10)}{10}
10P(10,10) 个方案 ;
参考 : 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 ) 四、环排列
n
n
n 元集
S
S
S , 从
S
S
S 集合中 有序 , 不重复 选取
r
r
r 个元素 ,
S
S
S 集合的
r
−
r-
r− 环排列数
=
P
(
n
,
r
)
r
= \dfrac{P(n,r)}{r}
=rP(n,r)
r
r
r 个不同的线性排列 , 相当于同一个环排列 ;
一个环排列 , 从任意位置剪开 , 可以构成
r
r
r 种不同的线性排列 ;
② 第二步 : 然后将女生插空放进去 ,
5
5
5 个女生只能放在这
10
10
10 个格子中 ;
![动态规划与排列组合二项式的关系[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)