文章目录

一、多重集
二、多重集全排列
三、多重集全排列示例
三、多重集非全排列 1 所有元素重复度大于排列数 ( $n_i \geq r ni≥r )$
四、多重集非全排列 2 某些元素重复度小于排列数 ( $n_i \leq r ni≤r )$

排列组合参考博客 :

【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
【组合数学】排列组合 ( 排列组合示例 )

一、多重集

多重集表示 :

{

⋅

⋯

⋅

}

≤

∞

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty

$S = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}, 0 \leq n_{i} \leq + \infty$

元素种类 : 多重集中含有
$k$ 种不同的元素 ,
元素表示 : 每个元素表示为 $a_1 , a_2 , \cdots , a_k$
$a_{1}, a_{2}, \dots, a_{k}$ ,
元素个数 : 每个元素出现的次数是 $n_1, n_2, \cdots , n_k$
$n_{1}, n_{2}, \dots, n_{k}$ ,
元素个数取值 : $n_i ni 的取值要求是大于 0 0 0 , 小于正无穷 + ∞ + \infty$
$+ \infty$ ;

二、多重集全排列

多重集 :

{

⋅

⋯

⋅

}

≤

∞

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty

$S = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}, 0 \leq n_{i} \leq + \infty$

★ 全排列 :

⋯

r = n_1 + n_2 + \cdots + n_k = n

$r = n_{1} + n_{2} + \dots + n_{k} = n$

⋯

N = \cfrac{n!}{n_1! n_2! \cdots n_k!}

$N = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

★ 多重集的全排列数是元素总数阶乘 , 除以所有重复度的阶乘 ;

下面是推导过程

有

k

k

$k$ 种元素 ,

放置元素

a

1

a_1

$a_{1}$ : 在排列中先放第一种元素

a_1

$a_{1}$ , 该元素有

n_1

$n_{1}$ 个 ,

$n$ 个位置中选出

n_1

$n_{1}$ 个位置 , 有

(

)

C(n, n_1)

$C (n, n_{1})$ 种方法 ;

(

)

(

−

)

C(n, n_1) = \cfrac{n!}{(n-n_1) ! \ n_1!}

$C (n, n_{1}) = \frac{n !}{( n - n _{1} ) ! n _{1} !}$

放置元素

a

2

a_2

$a_{2}$ : 放置好

n_1

$n_{1}$ 之后放置第二种元素

a_2

$a_{2}$ , 该元素有

n_2

$n_{2}$ 个 , 此时还有

−

n-n_1

$n - n_{1}$ 个空位 , 从

−

n-1

$n - 1$ 个位置中选择

n_2

$n_{2}$ 个位置有

(

−

)

C(n-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!}

$C (n - n_{1}, n_{2}) = \frac{( n - n _{1} ) !}{( n - n _{1} - n _{2} ) ! n _{2} !}$

⋮

\vdots

$⋮$

放置元素

a

k

a_k

$a_{k}$ : 放置最后一个元素

a_k

$a_{k}$ , 该元素有

n_k

$n_{k}$ 个 , 此时还有

−

⋯

−

n-n_1- \cdots -n_{k-1}

$n - n_{1} - \dots - n_{k - 1}$ 个空位 , 从

−

⋯

−

n-n_1- \cdots -n_{k-1}

$n - n_{1} - \dots - n_{k - 1}$ 个位置中选择

n_k

$n_{k}$ 个位置有

(

−

⋯

−

)

C(n-n_1- \cdots -n_{k-1} , n_k)

$C (n - n_{1} - \dots - 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!}

$C (n - n_{1} - \dots - n_{k - 1}, n_{k}) = \frac{( n - n _{1} - \dots - n _{k - 1} ) !}{( n - n _{1} - \dots - n _{k - 1} - n _{k} ) ! n _{k} !}$

乘法法则 : 最后根据乘法法则 , 将上述每个放置方法乘起来 , 就得到最终的结果 , 阶乘看起来很复杂 , 但是阶乘选项如

(

−

⋯

−

)

(n-n_1- \cdots -n_{k-1})!

$(n - n_{1} - \dots - 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}

$N = = = C (n, n_{1}) C (n - n_{1}, n_{2}) C (n - n_{1} - \dots - n_{k - 1}, n_{k}) \frac{n !}{( n - n _{1} ) ! n _{1} !} \times \frac{( n - n _{1} ) !}{( n - n _{1} - n _{2} ) ! n _{2} !} \times \frac{( n - n _{1} - \dots - n _{k - 1} ) !}{( n - n _{1} - \dots - n _{k - 1} - n _{k} ) ! n _{k} !} 约掉部分阶乘 \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

三、多重集全排列示例

求多重集

S

=

{

3

⋅

a

,

2

⋅

b

,

1

⋅

c

}

S=\{ 3 \cdot a , 2 \cdot b , 1 \cdot c \}

$S = {3 \cdot a, 2 \cdot b, 1 \cdot c}$ 的全排列 ?

上述多重集元素总个数是

n = 3 + 2 + 1 = 6

$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

$N = \frac{6 !}{3 ! \times 2 ! \times 1 !} = \frac{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 ni≥r )$

多重集 :

{

⋅

⋯

⋅

}

≤

∞

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty

$S = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}, 0 \leq n_{i} \leq + \infty$

★ 非全排列情况

1

1

$1$ :

≤

r \leq n_i

$r \leq n_{i}$ , 注意这里的

r

r

$r$ 要小于等于最小的

n

i

n_i

$n_{i}$ ;

N = k^r

$N = k^{r}$

推导过程 :

在上述条件下 ,

$r$ 个位置 ,

每个位置的元素都有

$k$ 种选择 ,

根据乘法法则 , 总的选择个数是

⋯

⏟

个

\begin{matrix} \underbrace{ k \times k \times \cdots \times k } \\ r 个 k \end{matrix}

$k \times k \times \dots \times k r 个 k$ ,

即

r^k

$r^{k}$ ;

四、多重集非全排列 2 某些元素重复度小于排列数 ( $n_i \leq r ni≤r )$

上述情况只适用于重复度足够大的情况 , 即 每个元素的重复度都大于选取个数 ,

≤

r \leq n_i

$r \leq n_{i}$

如果有一个元素的重复度小于选取个数 ,

≥

r \geq n_i

$r \geq n_{i}$ ,

如

{

⋅

}

S=\{ 3 \cdot a , 2 \cdot b , 1 \cdot c \}

$S = {3 \cdot a, 2 \cdot b, 1 \cdot c}$ 多重集的三排列 , 就无法使用公式计算了 ,

没有公式可以计算 , 但是可以使用 包含排斥原理 , 生成函数 进行计算 ;

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

文章目录

一、多重集

二、多重集全排列

三、多重集全排列示例

三、多重集非全排列 1 所有元素重复度大于排列数 ( $n_i \geq r ni≥r )$

四、多重集非全排列 2 某些元素重复度小于排列数 ( $n_i \leq r ni≤r )$

相关推荐

一个分享Java & Python知识的社区

文章目录

一、多重集

二、多重集全排列

三、多重集全排列示例

三、多重集非全排列 1 所有元素重复度大于排列数 ( n i ≥ r n_i \geq r ni​≥r )

四、多重集非全排列 2 某些元素重复度小于排列数 ( n i ≤ r n_i \leq r ni​≤r )

相关推荐

一个分享Java & Python知识的社区

三、多重集非全排列 1 所有元素重复度大于排列数 ( $n_i \geq r ni≥r )$

四、多重集非全排列 2 某些元素重复度小于排列数 ( $n_i \leq r ni≤r )$