【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )

2023-03-28 18:15:13 浏览数 (1)

文章目录

  • 一、多重集组合 ( 所有元素重复度大于组合数 )
  • 二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )
  • 二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )

排列组合参考博客 :

  • 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
  • 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
  • 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
  • 【组合数学】排列组合 ( 排列组合示例 )
  • 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )

一、多重集组合 ( 所有元素重复度大于组合数 )

多重集 :

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

;

上述多重集的组合 , 当 所有元素的重复度

n_i

组大于组合数

r

时 ,

r leq n_i

时 , 多重集的组合数为

N= C(k r - 1, r)

二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )

多重集 :

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

取

r

种元素的组合 ,

r leq n_i

, 推导过程如下 :

在

k

种元素中 , 取

r

种元素 , 每种元素取

0 sim r

个不等的元素 ,

使用

k-1

个分割线分割

k

种元素的位置 ,

k - 1

个分割线相当于组成了

k

个盒子 , 在每个盒子中放

0 sim r

个不等的元素 ,

放置的总元素的个数是

r

个 , 分割线个数是

k-1

个 , 这里就产生了一个组合问题 , 在

k-1

个分割线 和

r

个元素之间 , 选取

r

个元素 , 就是 多重集的

r leq n_i

情况下的 组合个数 ;

结果是 :

N= C(k r - 1, r)

二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )

多重集 :

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

取

r

种元素的组合 ,

r leq n_i

, 推导过程如下 :

多重集

S

每个元素取值 :

  • 第
1

种元素取值个数 : 元素

a_1

的取值个数是

x_1

,

  • 第
2

种元素取值个数 : 元素

a_2

的取值个数是

x_2

,

; ; , vdots
  • 第
k

种元素取值个数 :元素

a_k

的取值个数是

x_k

;

不定方程

x_1 x_2 cdots x_k = r

;

x_i

可以为

0

, 即某个元素取值个数可以是

0

;

则多重集

S

的

r

组合是 :

{ x_1 cdot a_1 , x_2 cdot a_2 , cdots , x_k cdot a_k }
x_i

的取值是非负整数

多重集组合与方程对应 : 只要有一个

r

组合 , 就可以写出一个对象的 方程

x_1 x_2 cdots x_k = r

出来 ;

非负整数解与多重集组合对应 :

x_1 x_2 cdots x_k = r

不定方程的一组非负整数解 , 就对应着 一个

S

多重集的

r

组合 ;

一一对应关系 : 上述

方程的非负整数解的个数

与

S

多重集的

r

组合个数 一一对应 ;

求

S

多重集的

r

组合数 , 就可以转化成 求

x_1 x_2 cdots x_k = r

方程非负整数解个数 ;

将上述解写成一个序列 , 序列中使用

k-1

个

0

, 分割

k

组

1

;

begin{matrix} underbrace{ 1 cdots 1 } \ x_1个1 end{matrix}
0
begin{matrix} underbrace{ 1 cdots 1 } \ x_2个1 end{matrix}
0
begin{matrix} underbrace{ 1 cdots 1 } \ x_3个1 end{matrix}
0
cdots
0
begin{matrix} underbrace{ 1 cdots 1 } \ x_k个1 end{matrix}

不定方程每个解 都对应着 上述

k-1

个

0

和

r

个

1

的一个排列 ;

相当于一个多重集

S' = { r cdot 1 , (k-1) cdot 0 }

的全排列 ;

这里就将 多重集的组合问题 , 转化成了 另外一个多重集的全排列问题 , 多重集全排列是有公式的 ;

多重集全排列的公式是 : ( 回顾知识点 ① )

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!}

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

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

( 回顾知识点完毕 ① )

可以根据上述公式 , 计算 多重集

S' = { r cdot 1 , (k-1) cdot 0 }

的全排列 , 结果是 :

N = cfrac{(r k - 1) !}{ r! (k-1)! }

★ 排列数与组合数回顾 : ( 回顾知识点 ② )

  • 排列数 :
n

元集

S

, 从

S

集合中 有序 , 不重复 选取

r

个元素 ,

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

元集

S

, 从

S

集合中 无序 , 不重复 选取

r

个元素 ,

C(n,r) = dfrac{P(n,r)}{r!} dfrac{n!}{(n-r)!r!}

参考 : 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )

( 回顾知识点完毕 ② )

由上述的组合数可以看出 ,

N = cfrac{(r k - 1) !}{ r! (k-1)! }

的值正好是从

r k - 1

个元素中取

r

个元素的组合数 ;

N = cfrac{(r k - 1) !}{ r! (k-1)! } = C(r k - 1 , r)
博客 对象 集合 数学

0 人点赞