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

举报
韩曙亮 发表于 2022/01/10 23:28:31 2022/01/10
【摘要】 文章目录 一、多重集组合示例二、三个计数模型 排列组合参考博客 : 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 ...



排列组合参考博客 :





一、多重集组合示例



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


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

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



假设 n n n 个盒子 , 每个盒子的球数为 x 1 , x 2 , ⋯   , x k x_1 , x_2 , \cdots , x_k x1,x2,,xk ;

存在不定方程 : x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = r x1+x2++xk=r

取值 : x 1 , x 2 , ⋯   , x k x_1 , x_2 , \cdots , x_k x1,x2,,xk 的取值为非负整数 , 可以取值 0 ∼ r 0 \sim r 0r 之间的值 ;



该问题可以等价于多重集 S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ r ≤ n i ≤ + ∞ 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 S={n1a1,n2a2,,nkak},   0rni+ r r r 组合数 ;

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

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



上述 r r r 个相同的球 , 放在 k k k 个不同盒子中 , 放球方法数是
N = C ( k + r − 1 , r ) N = C(k + r - 1, r) N=C(k+r1,r)





二、三个计数模型



三个计数模型 :

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

1. 选取问题 :

n n n 元集 S S S , S S S 集合中选取 r r r 个元素 ;

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

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

选取问题中 :

  • 不可重复的元素 , 有序的选取 , 对应 集合的排列
  • 不可重复的元素 , 无序的选取 , 对应 集合的组合
  • 可重复的元素 , 有序的选取 , 对应 多重集的排列
  • 可重复的元素 , 无序的选取 , 对应 多重集的组合


2. 多重集组合问题 :

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ n i ≤ + ∞ S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty S={n1a1,n2a2,,nkak},   0ni+

  • 元素种类 : 多重集中含有 k k k 种不同的元素 ,
  • 元素表示 : 每个元素表示为 a 1 , a 2 , ⋯   , a k a_1 , a_2 , \cdots , a_k a1,a2,,ak ,
  • 元素个数 : 每个元素出现的次数是 n 1 , n 2 , ⋯   , n k n_1, n_2, \cdots , n_k n1,n2,,nk ,
  • 元素个数取值 : n i n_i ni 的取值要求是 大于 0 0 0 , 小于正无穷 + ∞ + \infty + ;

上述多重集的组合 , 当 所有元素的重复度 n i n_i ni 组大于组合数 r r r , r ≤ n i r \leq n_i rni 时 , 多重集的组合数为

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



3. 不定方程非负整数解问题 : x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = r x1+x2++xk=r

非负整数解个数为 : N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r1,r)

文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。

原文链接:hanshuliang.blog.csdn.net/article/details/109145188

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。