【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题 | 不定方程非负整数解问题 )

韩曙亮

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

4800

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

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

文章目录

排列组合参考博客 :

一、多重集组合示例

将

r

个相同的球 , 放到

k

个不同的盒子中 , 每个盒子中球的个数不限 , 求放球的总方法数 ?

球是没有区别的 , 球放到盒子里 , 球没有标号 , 盒子有标号 , 每个盒子放球的个数不同 ;

落入每个盒子中球个数不同 , 就是不同的方案 ;

假设

n

个盒子 , 每个盒子的球数为

x_1 , x_2 , \cdots , x_k

;

存在不定方程 :

x_1 + x_2 + \cdots + x_k = r

取值 :

x_1 , x_2 , \cdots , x_k

的取值为非负整数 , 可以取值

0 \sim r

之间的值 ;

该问题可以等价于多重集

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

的

r

组合数 ;

N= C(k + r - 1, r)

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

上述

r

个相同的球 , 放在

k

个不同盒子中 , 放球方法数是

N = C(k + r - 1, r)

二、三个计数模型

三个计数模型 :

① 选取问题 :
② 多重集组合问题 :
③ 方程非负整数解 :

1. 选取问题 :

n

元集

S

, 从

S

集合中选取

r

个元素 ;

根据元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :

	元素不重复	元素可以重复
有序选取	集合排列 P ( n , r ) P(n,r) P(n,r)	多重集排列
无序选取	集合组合 C ( n , r ) C(n,r) C(n,r)	多重集组合

P(n,r)

多重集排列无序选取集合组合

C(n,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

元素种类 : 多重集中含有

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)

3. 不定方程非负整数解问题 :

x_1 + x_2 + \cdots + x_k = r

非负整数解个数为 :

N= C(k + r - 1, r)

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

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

博客

集合

模型

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度