重复组合数怎么推导的_重复组合数怎么推导的

重复组合数怎么推导的_重复组合数怎么推导的一、多重集组合示例、二、三个计数模型、_方程非负整数解组合数学

重复组合数怎么推导的_重复组合数怎么推导的

排列组合参考博客 :

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

一、多重集组合示例


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={
n1
a1,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={
n1
a1,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)

今天的文章重复组合数怎么推导的_重复组合数怎么推导的分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/85095.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注