2023-03-28 18:14:47
浏览数 (5)
文章目录 一、多重集 二、多重集全排列 三、多重集全排列示例 三、多重集非全排列 1 所有元素重复度大于排列数 ( n_i geq r )
四、多重集非全排列 2 某些元素重复度小于排列数 ( n_i leq r )
排列组合参考博客 :
【组合数学】基本计数原则 ( 加法原则 | 乘法原则 ) 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 ) 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 ) 【组合数学】排列组合 ( 排列组合示例 ) 一、多重集 多重集表示 :
S = { n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k } , 0 leq n_i leq infty k 种不同的元素 ,
a_1 , a_2 , cdots , a_k ,
n_1, n_2, cdots , n_k ,
n_i 的取值要求是 大于
0 , 小于正无穷
infty ;
二、多重集全排列 多重集 :
S = { n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k } , 0 leq n_i leq infty ★ 全排列 :
r = n_1 n_2 cdots n_k = n N = cfrac{n!}{n_1! n_2! cdots n_k!} ★ 多重集的全排列数是 元素总数阶乘 , 除以 所有重复度的阶乘 ;
下面是推导过程
有
k 种元素 ,
放置元素
a_1 : 在排列中先放第一种元素
a_1 , 该元素有
n_1 个 ,
n 个位置中选出
n_1 个 位置 , 有
C(n, n_1) 种方法 ;
C(n, n_1) = cfrac{n!}{(n-n_1) ! n_1!} 放置元素
a_2 : 放置好
n_1 之后放置第二种元素
a_2 , 该元素有
n_2 个 , 此时还有
n-n_1 个空位 , 从
n-1 个位置中选择
n_2 个位置有
C(n-n_1 , n_2) 种方法 ;
C(n - n_1, n_2) = cfrac{(n-n_1)!}{(n-n_1 - n_2) ! n_2!} vdots 放置元素
a_k : 放置最后一个元素
a_k , 该元素有
n_k 个 , 此时还有
n-n_1- cdots -n_{k-1} 个空位 , 从
n-n_1- cdots -n_{k-1} 个位置中选择
n_k 个位置有
C(n-n_1- cdots -n_{k-1} , n_k) 种方法 ;
C(n-n_1- cdots -n_{k-1} , n_k) = cfrac{(n-n_1- cdots -n_{k-1})!}{(n-n_1- cdots -n_{k-1} - n_k) ! n_k!} 乘法法则 : 最后根据乘法法则 , 将上述每个放置方法乘起来 , 就得到最终的结果 , 阶乘看起来很复杂 , 但是 阶乘选项如
(n-n_1- cdots -n_{k-1})! 都可以约掉 , 最终结果如下 :
begin{array}{lcl} N & = & C(n, n_1) C(n - n_1, n_2) C(n-n_1- cdots -n_{k-1} , n_k) \\ & = & cfrac{n!}{(n-n_1) ! n_1!} times cfrac{(n-n_1)!} {(n-n_1 - n_2) ! n_2!} times cfrac{(n-n_1- cdots -n_{k-1})!}{(n-n_1- cdots -n_{k-1} - n_k) ! n_k!} 约掉部分阶乘 \\ &=& cfrac{n!}{n_1! n_2! cdots n_k!} end{array} 三、多重集全排列示例 求多重集
S={ 3 cdot a , 2 cdot b , 1 cdot c } 的全排列 ?
上述多重集元素总个数是
n = 3 2 1 = 6 ;
全排列个数是 :
N = cfrac{6!}{3! times 2! times 1!} = cfrac{6 times 5 times 4 times 3 times 2 times 1}{( 3 times 2 times 1 ) times ( 2 times 1 ) times (1 times 1)} = 60 三、多重集非全排列 1 所有元素重复度大于排列数 ( n_i geq r )
多重集 :
S = { n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k } , 0 leq n_i leq infty ★ 非全排列情况
1 :
r leq n_i , 注意这里的
r 要 小于等于 最小的
n_i ;
N = k^r 推导过程 :
在上述条件下 ,
r 个位置 ,
每个位置的元素都有
k 种选择 ,
根据乘法法则 , 总的选择个数是
begin{matrix} underbrace{ k times k times cdots times k } \ r 个 k end{matrix} ,
即
r^k ;
四、多重集非全排列 2 某些元素重复度小于排列数 ( n_i leq r )
上述情况只适用于重复度足够大的情况 , 即 每个元素的重复度都大于选取个数 ,
r leq n_i 如果 有一个元素的重复度小于选取个数 ,
r geq n_i ,
如
S={ 3 cdot a , 2 cdot b , 1 cdot c } 多重集的三排列 , 就无法使用公式计算了 ,
没有公式可以计算 , 但是可以 使用 包含排斥原理 , 生成函数 进行计算 ;
