【组合数学】排列组合 ( 多重集组合数示例 | 三个计数模型 | 选取问题 | 多重集组合问题

文章目录

一、多重集组合示例
二、三个计数模型

排列组合参考博客 :

【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
【组合数学】排列组合 ( 排列组合示例 )
【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列所有元素重复度大于排列数 | 多重集非全排列某些元素重复度小于排列数 )
【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数推导 1 分割线推导 | 多重集组合数推导 2 不定方程非负整数解个数推导 )

一、多重集组合示例

将

个相同的球 , 放到

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

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

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

假设

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

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

的

组合数 ;

N= C(k r - 1, r)

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

上述

个相同的球 , 放在

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

N = C(k r - 1, r)

二、三个计数模型

三个计数模型 :

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

1. 选取问题 :

元集

, 从

集合中选取

个元素 ;

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

	元素不重复	元素可以重复
有序选取	集合排列 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

元素种类 : 多重集中含有

种不同的元素 ,

元素表示 : 每个元素表示为

a_1 , a_2 , cdots , a_k

元素个数 : 每个元素出现的次数是

n_1, n_2, cdots , n_k

元素个数取值 :

n_i

的取值要求是大于

, 小于正无穷

infty

;

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

n_i

组大于组合数

时 ,

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)

博客集合模型数学

0 人点赞

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

文章目录

一、多重集组合示例

二、三个计数模型