【组合数学】排列组合 ( 多重集组合数示例

排列组合参考博客 :

将 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 0∼r 之间的值 ;

该问题可以等价于多重集 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​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤r≤ni​≤+∞ 的 r r r 组合数 ;

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

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

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

三个计数模型 :

1. 选取问题 :

n n n 元集 S S S , 从 S S S 集合中选取 r r 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​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞

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

N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,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+r−1,r)