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

韩曙亮

发布于 2023-03-28 18:15:13

1.7K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

排列组合参考博客 :

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

多重集 :

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)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

对象

集合

数学