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

2023-03-28 18:16:07 浏览数 (1)

文章目录

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

排列组合参考博客 :

  • 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
  • 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
  • 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
  • 【组合数学】排列组合 ( 排列组合示例 )
  • 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )
  • 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )
  • 【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题 | 不定方程非负整数解问题 )
  • 【组合数学】排列组合 ( 两个计数原则、集合排列示例 | 集合排列、圆排列示例 )

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

将

2n

个人分成

n

组 , 每组

2

人 , 有多少种分法 ?

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

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

个人 , 人肯定是不重复的 , 分成

n

组 , 这里的分组是没有区别的 , 相当于集合的划分 ;

另外还有限制条件 , 每组只能放

2

个元素 ;

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

不是简单的选取问题 ;

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

分组有区别的话 , 分成

n

组 , 先放第

1

组 , 选

2

个人 , 再放第

2

组 , 选

2

个人 ,

cdots

这种方案是 可以计算出来的 ;

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

分组没有区别 , 得到一种方法 , 然后对

n

个分组进行全排列 , 有

n!

种排列方法 , 就得到了分组有区别的方案个数 ;

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

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

分组有区别方案数 是可以计算出来的 , 然后 除以

n!

, 即可得到 分组没有区别的方案数 ;

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

① 第

1

步 : 从

2n

个元素中 , 选取

2

个元素 , 有

C(2n , 2)

种方案 ;

② 第

2

步 : 从

2n - 2

个元素中 , 选取

2

个元素 , 有

C(2n - 2 , 2)

种方案 ;

③ 第

3

步 : 从

2n - 4

个元素中 , 选取

2

个元素 , 有

C(2n - 4 , 2)

种方案 ;

vdots

④ 第

n

步 : 从

2n - ( 2n - 2 )

个元素中 , 选取

2

个元素 , 有

C(2n - ( 2n - 2 ) , 2)

种方案 ; 也就是

1

种方案 ;

排列组合公式

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

分步处理 需要使用乘法原则 , 将

n

步的方案数相乘 :

begin{array}{lcl} N &=& C(2n , 2) C(2n - 2 , 2) C(2n - 4 , 2) cdots C(2n - ( 2n - 2 ) , 2) \\ &=& begin{matrix} underbrace{ cfrac{2n!}{2! times (2n-2)!} times cfrac{(2n-2)!}{2! times (2n-4)!} cdots cfrac{(2n - ( 2n - 2 ))!}{2! times (2n - ( 2n - 2 ) - 2)!} } \ n 个分步相乘 end{matrix} 前后可以约掉很多阶乘\\ &=& cfrac{(2n)!}{(2!)^n} end{array}

分组有区别的方案个数是

cfrac{(2n)!}{(2!)^n}

个 ;

根据

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

公式 ;

分组有区别方案数 是可以计算出来的 , 然后 除以

n!

, 即可得到 分组没有区别的方案数 ;

最终结果是

cfrac{(2n)!}{(2!)^n n!}

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

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

博客 集合 模型 数学

0 人点赞