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

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

文章目录

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

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



排列组合参考博客 :


【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )

【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )

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

【组合数学】排列组合 ( 排列组合示例 )

【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )

【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )

【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题 | 不定方程非负整数解问题 )





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


排列 26 2626 个字母 , 使得 a , b a,ba,b 之间有 7 77 个字母 , 求排列方法数 ;



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


分类计数 ( 加法原则 ) : 有 3 33 类方案 , 第一类有 2 22 个方案 , 第二类有 4 44 个方案 , 第三类有 1 11 个方案 , 总共有 2 + 4 + 1 = 7 2 + 4 + 1 = 72+4+1=7 个方案 ;

分步计数原理 ( 乘法原则 ) : 有 3 33 类方案 , 第一步有 2 22 个方案 , 第二步有 4 44 个方案 , 第三步有 1 11 个方案 , 总共有 2 × 4 × 1 = 8 2 \times 4 \times 1 = 82×4×1=8 个方案 ;


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


第一步 : 先构造出以 a , b a,ba,b 为边界 , 中间含有 7 77 个字母的子结构 ;

第二步 : 将 a , b a,ba,b 子结构作为元素 , 与其它 26 − 9 = 17 26-9 = 1726−9=17 个子元素一起 , 总共 18 1818 个元素进行全排列 ;

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




2. 第一步计算 : 先构造出以 a , b a,ba,b 为边界 , 中间含有 7 77 个字母的子结构 ;


该子结构中的 7 77 个字母 , 相当于从除 a , b a,ba,b 之外的其它 24 2424 个字母中选取 7 77 个字母进行排列 ,


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


24 2424 个字母中选取 7 77 个字母进行排列 , 选取方法有 P ( 24 , 7 ) P(24, 7)P(24,7) 种 ;


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


第一类是 a aa 在前 , b bb 在后的情况 , 选取方法有 P ( 24 , 7 ) P(24, 7)P(24,7) 种 ;

第二类是 b bb 在前 , a aa 在后的情况 , 选取方法有 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,ba,b 子结构作为元素 , 与其它 26 − 9 = 17 26-9 = 1726−9=17 个子元素一起 , 总共 18 1818 个元素进行全排列 ;


18 1818 个元素进行全排列 , 结果是 18 ! 18!18! ;




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


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


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

N=2 P(24,7) 18!






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


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



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


分类计数 ( 加法原则 ) : 有 3 33 类方案 , 第一类有 2 22 个方案 , 第二类有 4 44 个方案 , 第三类有 1 11 个方案 , 总共有 2 + 4 + 1 = 7 2 + 4 + 1 = 72+4+1=7 个方案 ;

分步计数原理 ( 乘法原则 ) : 有 3 33 类方案 , 第一步有 2 22 个方案 , 第二步有 4 44 个方案 , 第三步有 1 11 个方案 , 总共有 2 × 4 × 1 = 8 2 \times 4 \times 1 = 82×4×1=8 个方案 ;


1. 10 1010 个男生 , 5 55 个女生, 站成一排 , 如果没有女生相邻 , 有多少种方法 :


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



① 第一步 : 先把男生放好 , 男生 10 1010 个 , 站好以后有 11 1111 个格子 ;


10 1010 个男生的放置位置 , 元素不重复的有序选取 , 这是集合排列问题 , 排列方案有 P ( 10 , 10 ) = 10 ! P(10,10) = 10!P(10,10)=10! 个方案 ;



② 第二步 : 然后将女生插空放进去 , 5 55 个女生只能放在这 11 1111 个格子中 ;


11 1111 个格子中放 5 55 个女生 , 元素不重复的有序选取 , 这是集合的排列问题 , 排列方案有 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 1010 个男生 , 5 55 个女生, 站成一圈 , 如果没有女生相邻 , 有多少种方法 :


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



① 第一步 : 先把男生放好排成一圈 , 男生 10 1010 个 , 因为是排成一圈 , 因此站好以后只有 10 1010 个格子 ;


10 1010 个男生的放置位置 , 元素不重复的有序选取 , 这是集合圆排列问题 , 需要使用圆排列公式 , 排列方案有 P ( 10 , 10 ) 10 \cfrac{P(10,10)}{10}

10

P(10,10)


 个方案 ;


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


n nn 元集 S SS , 从 S SS 集合中 有序 , 不重复 选取 r rr 个元素 ,

S SS 集合的 r − r-r− 环排列数 = P ( n , r ) r = \dfrac{P(n,r)}{r}=

r

P(n,r)


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

一个环排列 , 从任意位置剪开 , 可以构成 r rr 种不同的线性排列 ;



② 第二步 : 然后将女生插空放进去 , 5 55 个女生只能放在这 10 1010 个格子中 ;


10 1010 个格子中放 5 55 个女生 , 元素不重复的有序选取 , 这是集合的排列问题 , 排列方案有 P ( 10 , 5 ) P(10, 5)P(10,5)


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


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

10

P(10,10)


 P(10,5)


目录
相关文章
|
6月前
|
算法
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
60 1
|
7月前
|
人工智能 算法 数据可视化
【算法训练-数组 五】【数组组合】:下一个排列
【算法训练-数组 五】【数组组合】:下一个排列
46 0
|
存储 算法
回溯算法:排列与组合详解
回溯算法,本质上是一种穷举算法,属于暴力搜索算法的一种。它虽然可以使用剪枝进行优化,仍不高效,但却实用。它往往能够解决可以抽象成树形结构的问题,亦可以认为是使用 K 层 for循环实现搜索的问题。
160 0
回溯算法:排列与组合详解
|
C++
C++ leetcode之排列与组合专题
C++ leetcode之排列与组合专题
86 0
每日三题-寻找两个正序数组的中位数 、搜索旋转排序数组、 在排序数组中查找元素的第一个和最后一个位置
每日三题-寻找两个正序数组的中位数 、搜索旋转排序数组、 在排序数组中查找元素的第一个和最后一个位置
58 2
每日三题-寻找两个正序数组的中位数 、搜索旋转排序数组、 在排序数组中查找元素的第一个和最后一个位置
|
索引
每日三题-下一个排列、颜色分类、寻找重复数
每日三题-下一个排列、颜色分类、寻找重复数
82 0
每日三题-下一个排列、颜色分类、寻找重复数
|
算法
LeetCode 38外观数列&39组合总和
给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。
105 0
LeetCode 38外观数列&39组合总和
寻找旋转排序数组中的最小值 (重复与非重复代码)
寻找旋转排序数组中的最小值 (重复与非重复代码)
110 0
寻找旋转排序数组中的最小值 (重复与非重复代码)