【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )

参考博客 :

• 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
• 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
• 【组合数学】生成函数 ( 移位性质 )
• 【组合数学】生成函数 ( 求和性质 )
• 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
• 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
• 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
• 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

一、使用生成函数求解多重集 r 组合数

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } S = \{ n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k \} S={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​} 是多重集 , 其含有 k k k 个种类的元素 , n 1 , n 2 , ⋯   , n k n_1, n_2, \cdots, n_k n1​,n2​,⋯,nk​ 是每种元素的重复度 ,

该 多重集的 r r r 组合数 , 是 不定方程 x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = r x1​+x2​+⋯+xk​=r 的非负整数解 , 前提是 x i ≤ n i x_i \leq n_i xi​≤ni​ , 每个元素所取的个数 x i x_i xi​ , 不能超过其重复度 n i n_i ni​ ;

相当于 a 1 a_1 a1​ 取 x 1 x_1 x1​ 个 , a 2 a_2 a2​ 取 x 2 x_2 x2​ 个 , ⋯ \cdots ⋯ , a k a_k ak​ 取 x k x_k xk​ 个 , 总共取 r r r 个 ;

n i n_i ni​ 是无穷个数时 , 多重集的 r r r 组合数是 C ( k + r − 1 , r ) C(k + r - 1, r) C(k+r−1,r)

回顾多重集排列组合 :

• 可重复的元素 , 有序的选取 , 对应 多重集的排列 ; 全 排 列 = n ! n 1 ! n 2 ! ⋯ n k ! 全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!} 全排列=n1​!n2​!⋯nk​!n!​ , 非全排列 k r ,    r ≤ n i k^r , \ \ r\leq n_i kr,  r≤ni​
• 可重复的元素 , 无序的选取 , 对应 多重集的组合 ; N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,r)

上述的 多重集 r r r 组合数 C ( k + r − 1 , r ) C(k + r - 1, r) C(k+r−1,r) 是在重复度不受限制的情况下的选取结果 , 如果重复度受限制 , 就需要使用生成函数进行计算 ;

如添加如下限制 : a 1 a_1 a1​ 最多能取 3 3 3 个 , a 2 a_2 a2​ 最少取 4 4 4 个 , 最多取 10 10 10 个 ;

生成函数 :

G ( y ) = G(y) = G(y)= ( 1 + y + ⋯ + y n 1 ) (1 + y + \cdots + y^{n_1}) (1+y+⋯+yn1​) ( 1 + y + ⋯ + y n 2 ) (1 + y + \cdots + y^{n_2}) (1+y+⋯+yn2​) ⋯ \cdots ⋯ ( 1 + y + ⋯ + y n k ) (1 + y + \cdots + y^{n_k}) (1+y+⋯+ynk​)

多重集中的每个元素的取值个数作为 y y y 的次幂 , 如 a 1 a_1 a1​ 元素的取值个数是 0 0 0 到 n 1 n_1 n1​ , 则该项对应的 生成函数项是 从 y y y 的 0 0 0 次幂 , 到 y y y 的 n 1 n_1 n1​ 次幂 相加 ; 构成项 ( 1 + y + ⋯ + y n 1 ) (1 + y + \cdots + y^{n_1}) (1+y+⋯+yn1​) ;

将所有元素的上述 生成函数项 乘到一起 , 就构成上述生成函数 ;

按照多项式乘法 , 多重集中取 r r r 个元素 ,

从第一个因式 ( 1 + y + ⋯ + y n 1 ) (1 + y + \cdots + y^{n_1}) (1+y+⋯+yn1​) 拿出 y x 1 y^{x_1} yx1​ ,

从第二个因式 ( 1 + y + ⋯ + y n 2 ) (1 + y + \cdots + y^{n_2}) (1+y+⋯+yn2​) 拿出 y x 2 y^{x_2} yx2​ ,

⋮ \vdots ⋮

从第 k k k 个因式 ( 1 + y + ⋯ + y n k ) (1 + y + \cdots + y^{n_k}) (1+y+⋯+ynk​) 拿出 y x k y^{x_k} yxk​ ,

如果上述乘积 y x 1 y x 2 ⋯ y x k y^{x_1}y^{x_2}\cdots y^{x_k} yx1​yx2​⋯yxk​ 的结果 是 y r y^{r} yr , 即 y x 1 y x 2 ⋯ y x k = y r y^{x_1}y^{x_2}\cdots y^{x_k} = y^{r} yx1​yx2​⋯yxk​=yr , 相当于指数 x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = r x1​+x2​+⋯+xk​=r , 也就是不定方程的非负整数解 ;

二、使用生成函数求解多重集 r 组合数 示例

多重集 S = { 3 ⋅ a , 4 ⋅ b , 5 ⋅ c } S = \{3\cdot a , 4 \cdot b , 5 \cdot c \} S={3⋅a,4⋅b,5⋅c} , 求该多重集的 10 10 10 组合数 ;

上述多重集元素的 重复度 3 , 4 , 5 3,4,5 3,4,5 都不超过 10 10 10 ;

对应 a a a 元素 , 其 重复度取值范围是 0 0 0 ~ 3 3 3 , 对应的生成函数项是 y 0 + y 1 + y 2 + y 3 y^0 +y^1 + y^2 + y^3 y0+y1+y2+y3

对应 b b b 元素 , 其 重复度取值范围是 0 0 0 ~ 4 4 4 , 对应的生成函数项是 y 0 + y 1 + y 2 + y 3 + y 4 y^0 +y^1 + y^2 + y^3 + y^4 y0+y1+y2+y3+y4

对应 c c c 元素 , 其重 复度取值范围是 0 0 0 ~ 5 5 5 , 对应的生成函数项是 y 0 + y 1 + y 2 + y 3 + y 4 + y 5 y^0 +y^1 + y^2 + y^3 + y^4 + y^5 y0+y1+y2+y3+y4+y5

将上述项相乘 , 得到完整的生成函数 ;

G ( x ) = ( y 0 + y 1 + y 2 + y 3 ) ( y 0 + y 1 + y 2 + y 3 + y 4 ) ( y 0 + y 1 + y 2 + y 3 + y 4 + y 5 ) G(x) = (y^0 +y^1 + y^2 + y^3)(y^0 +y^1 + y^2 + y^3 + y^4)(y^0 +y^1 + y^2 + y^3 + y^4 + y^5) G(x)=(y0+y1+y2+y3)(y0+y1+y2+y3+y4)(y0+y1+y2+y3+y4+y5)

           = ( 1 + y 1 + y 2 + y 3 ) ( 1 + y 1 + y 2 + y 3 + y 4 ) ( 1 + y 1 + y 2 + y 3 + y 4 + y 5 ) \ \ \ \ \ \ \ \ \ \ =(1 +y^1 + y^2 + y^3)(1 +y^1 + y^2 + y^3 + y^4)(1 +y^1 + y^2 + y^3 + y^4 + y^5)           =(1+y1+y2+y3)(1+y1+y2+y3+y4)(1+y1+y2+y3+y4+y5)

           = ( 1 + 2 y 1 + 3 y 2 + 4 y 3 + 4 y 4 + 3 y 5 + 2 y 6 + y 7 ) ( 1 + y 1 + y 2 + y 3 + y 4 + y 5 ) \ \ \ \ \ \ \ \ \ \ =(1 +2y^1 + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7 )(1 +y^1 + y^2 + y^3 + y^4 + y^5)           =(1+2y1+3y2+4y3+4y4+3y5+2y6+y7)(1+y1+y2+y3+y4+y5)

统计上述两项相乘 , y y y 的次幂值为 10 10 10 的项 :

第一个因式的 3 y 5 3y^5 3y5 与第二个因式的 y 5 y^5 y5 , 相乘为 3 y 10 3y^{10} 3y10

第一个因式的 2 y 6 2y^6 2y6 与第二个因式的 y 4 y^4 y4 , 相乘为 2 y 10 2y^{10} 2y10

第一个因式的 y 7 y^7 y7 与第二个因式的 y 3 y^3 y3 , 相乘为 y 10 y^{10} y10

y 10 y^{10} y10 项前的系数是 3 + 2 + 1 = 6 3 + 2+1 = 6 3+2+1=6

因此上述 多重集的 10 10 10 组合 ,选择方案有 6 6 6 种 ;