【组合数学】排列组合 ( 集合组合、一一对应模型分析示例 )

举报
韩曙亮 发表于 2022/01/10 23:51:04 2022/01/10
【摘要】 文章目录 一、集合组合、一一对应模型分析示例 排列组合参考博客 : 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 ...



排列组合参考博客 :





一、集合组合、一一对应模型分析示例



2 n 2n 2n 个人分成 n n n 组 , 每组 2 2 2 人 , 有多少种分法 ?


先确定该问题是否是选取问题 , 元素是否重复 , 选取是否有序 ,

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

2 n 2n 2n 个人 , 人肯定是不重复的 , 分成 n n n 组 , 这里的分组是没有区别的 , 相当于集合的划分 ;

另外还有限制条件 , 每组只能放 2 2 2 个元素 ;

原始的简单模型 , 如 分类 ( 加法 ) , 分步 ( 乘法 ) , 集合排列 , 集合组合 , 多重集排列 , 多重集组合 , 没有对应的模型 , 无法直接使用 ;

不是简单的选取问题 ;



这里需要考虑 组有区别 , 组没有区别 两种情况 ;

分组有区别的话 , 分成 n n n 组 , 先放第 1 1 1 组 , 选 2 2 2 个人 , 再放第 2 2 2 组 , 选 2 2 2 个人 , ⋯ \cdots 这种方案是 可以计算出来的 ;

分组没有区别 , 此时需要观察 分组有区别没有区别 的差别 :

分组没有区别 , 得到一种方法 , 然后对 n n n 个分组进行全排列 , 有 n ! n! n! 种排列方法 , 就得到了分组有区别的方案个数 ;

这里将 分组有区别方案数 与 分组没有区别方案数 建立对应关系 :

分 组 没 有 区 别 方 案 数 × n ! = 分 组 有 区 别 方 案 数 分组没有区别方案数 \times n! = 分组有区别方案数 ×n!=


分组有区别方案数 是可以计算出来的 , 然后 除以 n ! n! n! , 即可得到 分组没有区别的方案数 ;



分组有区别 , 按照 分步处理 的方案 :

① 第 1 1 1 步 : 2 n 2n 2n 个元素中 , 选取 2 2 2 个元素 , C ( 2 n , 2 ) C(2n , 2) C(2n,2) 种方案 ;

② 第 2 2 2 步 : 2 n − 2 2n - 2 2n2 个元素中 , 选取 2 2 2 个元素 , C ( 2 n − 2 , 2 ) C(2n - 2 , 2) C(2n2,2) 种方案 ;

③ 第 3 3 3 步 : 2 n − 4 2n - 4 2n4 个元素中 , 选取 2 2 2 个元素 , C ( 2 n − 4 , 2 ) C(2n - 4 , 2) C(2n4,2) 种方案 ;

⋮ \vdots

④ 第 n n n 步 : 2 n − ( 2 n − 2 ) 2n - ( 2n - 2 ) 2n(2n2) 个元素中 , 选取 2 2 2 个元素 , C ( 2 n − ( 2 n − 2 ) , 2 ) C(2n - ( 2n - 2 ) , 2) C(2n(2n2),2) 种方案 ; 也就是 1 1 1 种方案 ;


排列组合公式

  • 排列 : P ( n , r ) = n ! ( n − r ) ! P(n,r) = \dfrac{n!}{(n-r)!} P(n,r)=(nr)!n!
  • 组合 : C ( n , r ) = P ( n , r ) r ! = n ! r ! ( n − r ) ! C(n, r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!} C(n,r)=r!P(n,r)=r!(nr)!n!

分步处理 需要使用乘法原则 , 将 n n n 步的方案数相乘 :

N = C ( 2 n , 2 ) C ( 2 n − 2 , 2 ) C ( 2 n − 4 , 2 ) ⋯ C ( 2 n − ( 2 n − 2 ) , 2 ) = 2 n ! 2 ! × ( 2 n − 2 ) ! × ( 2 n − 2 ) ! 2 ! × ( 2 n − 4 ) ! ⋯ ( 2 n − ( 2 n − 2 ) ) ! 2 ! × ( 2 n − ( 2 n − 2 ) − 2 ) ! ⏟ n 个 分 步 相 乘 前 后 可 以 约 掉 很 多 阶 乘 = ( 2 n ) ! ( 2 ! ) n

N===C(2n,2)C(2n2,2)C(2n4,2)C(2n(2n2),2)2n!2!×(2n2)!×(2n2)!2!×(2n4)!(2n(2n2))!2!×(2n(2n2)2)!n(2n)!(2!)n N = C ( 2 n , 2 ) C ( 2 n 2 , 2 ) C ( 2 n 4 , 2 ) C ( 2 n ( 2 n 2 ) , 2 ) = 2 n ! 2 ! × ( 2 n 2 ) ! × ( 2 n 2 ) ! 2 ! × ( 2 n 4 ) ! ( 2 n ( 2 n 2 ) ) ! 2 ! × ( 2 n ( 2 n 2 ) 2 ) ! n = ( 2 n ) ! ( 2 ! ) n
N===C(2n,2)C(2n2,2)C(2n4,2)C(2n(2n2),2) 2!×(2n2)!2n!×2!×(2n4)!(2n2)!2!×(2n(2n2)2)!(2n(2n2))!n(2!)n(2n)!

分组有区别的方案个数是 ( 2 n ) ! ( 2 ! ) n \cfrac{(2n)!}{(2!)^n} (2!)n(2n)! 个 ;


根据 分 组 没 有 区 别 方 案 数 × n ! = 分 组 有 区 别 方 案 数 分组没有区别方案数 \times n! = 分组有区别方案数 ×n!=

公式 ;

分组有区别方案数 是可以计算出来的 , 然后 除以 n ! n! n! , 即可得到 分组没有区别的方案数 ;

最终结果是 ( 2 n ) ! ( 2 ! ) n n ! \cfrac{(2n)!}{(2!)^n n!} (2!)nn!(2n)!



该问题不是简单的使用 原始的简单模型 , 如 分类 ( 加法 ) , 分步 ( 乘法 ) , 集合排列 , 集合组合 , 多重集排列 , 多重集组合 ;

而是将不可计算的模型 , 对应到一个可计算的模型中 , 然后计算出该模型 的重复度

文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。

原文链接:hanshuliang.blog.csdn.net/article/details/109152870

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。