IDEA激活码
文章目录
- 一、集合组合、一一对应模型分析示例
排列组合参考博客 :
- 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
- 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
- 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
- 【组合数学】排列组合 ( 排列组合示例 )
- 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )
- 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )
- 【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题 | 不定方程非负整数解问题 )
- 【组合数学】排列组合 ( 两个计数原则、集合排列示例 | 集合排列、圆排列示例 )
一、集合组合、一一对应模型分析示例
将
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
2n−2 个元素中 , 选取
2
2
2 个元素 , 有
C
(
2
n
−
2
,
2
)
C(2n - 2 , 2)
C(2n−2,2) 种方案 ;
③ 第
3
3
3 步 : 从
2
n
−
4
2n - 4
2n−4 个元素中 , 选取
2
2
2 个元素 , 有
C
(
2
n
−
4
,
2
)
C(2n - 4 , 2)
C(2n−4,2) 种方案 ;
⋮
\vdots
⋮
④ 第
n
n
n 步 : 从
2
n
−
(
2
n
−
2
)
2n - ( 2n - 2 )
2n−(2n−2) 个元素中 , 选取
2
2
2 个元素 , 有
C
(
2
n
−
(
2
n
−
2
)
,
2
)
C(2n - ( 2n - 2 ) , 2)
C(2n−(2n−2),2) 种方案 ; 也就是
1
1
1 种方案 ;
排列组合公式
- 排列 :
P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \dfrac{n!}{(n-r)!}
P(n,r)=(n−r)!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!(n−r)!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
\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}
N===C(2n,2)C(2n−2,2)C(2n−4,2)⋯C(2n−(2n−2),2)
2!×(2n−2)!2n!×2!×(2n−4)!(2n−2)!⋯2!×(2n−(2n−2)−2)!(2n−(2n−2))!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)!
该问题不是简单的使用 原始的简单模型 , 如 分类 ( 加法 ) , 分步 ( 乘法 ) , 集合排列 , 集合组合 , 多重集排列 , 多重集组合 ;
而是将不可计算的模型 , 对应到一个可计算的模型中 , 然后计算出该模型 的重复度
