【组合数学】不定方程解个数问题 ( 多重集r组合数 | 不定方程非负整数解个数 | 生成函数展开式中 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​} 的 r − r- r− 组合数

② 不定方程 x 1 + x 2 + ⋯ + x k = r ( x i ≤ n i ) x_1 + x_2 + \cdots + x_k = r (x_i \leq n_i) x1​+x2​+⋯+xk​=r(xi​≤ni​) 的非负整数解个数 ;

③ 生成函数 G ( y ) = ( 1 + y + y 2 + ⋯ + y n 1 ) ( 1 + y + y 2 + ⋯ + y n 2 ) ⋯ ( 1 + y + y 2 + ⋯ + y n k ) G(y) = (1+y+y^2 + \cdots + y^{n_1}) (1+y+y^2 + \cdots + y^{n_2})\cdots (1+y+y^2 + \cdots + y^{n_k}) G(y)=(1+y+y2+⋯+yn1​)(1+y+y2+⋯+yn2​)⋯(1+y+y2+⋯+ynk​) 展开后 y r y^r yr 的系数 ;

生成函数中 y y y 的幂从 0 0 0 到 n i n_i ni​ , 1 1 1 是 y 0 y^0 y0 ;

x i x_i xi​ 对应的是多重集中的 , 指定某元素 a i a_i ai​ 的个数 ;

多重集 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-组合数 ;

分析 : 以下 三个 数 是等价的 ;

• 1>多重集 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−组合数 ;
• 2>$x_1 + x_2 + x_3 = 10 $ , 0 ≤ x 1 ≤ 3 , 0 ≤ x 2 ≤ 4 , 0 ≤ x 3 ≤ 5 0 \leq x_1 \leq 3, 0 \leq x_2 \leq 4, 0 \leq x_3 \leq 5 0≤x1​≤3,0≤x2​≤4,0≤x3​≤5 的非负整数解个数 ;
• 3>生成函数 G ( y ) = ( 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(y) = (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(y)=(y0+y1+y2+y3)(y0+y1+y2+y3+y4)(y0+y1+y2+y3+y4+y5) 展开式中的 y 10 y^{10} y10 的系数 ;

解 :

① 展开上述生成函数 : G ( y ) = ( 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(y) = (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(y)=(y0+y1+y2+y3)(y0+y1+y2+y3+y4)(y0+y1+y2+y3+y4+y5)

② 其中 y 0 = 1 y^0 = 1 y0=1 , y 1 = y y^1 =y y1=y , 替换 : = ( 1 + y + y 2 + y 3 ) ( 1 + y + y 2 + y 3 + y 4 ) ( 1 + y + y 2 + y 3 + y 4 + y 5 ) = (1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4) (1 + y + y^2 + y^3 + y^4 + y^5) =(1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5)

③ 先将前两项 ( 1 + y + y 2 + y 3 ) ( 1 + y + y 2 + y 3 + y 4 ) (1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4) (1+y+y2+y3)(1+y+y2+y3+y4) 计算出来 : ( 1 + y + y 2 + y 3 ) ( 1 + y + y 2 + y 3 + y 4 ) (1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4) (1+y+y2+y3)(1+y+y2+y3+y4) = 1 + y + y 2 + y 3 + y 4 + y ( 1 + y + y 2 + y 3 + y 4 ) + y 2 ( 1 + y + y 2 + y 3 + y 4 ) + y 3 ( 1 + y + y 2 + y 3 + y 4 ) =1 + y + y^2 + y^3 + y^4 + y(1 + y + y^2 + y^3 + y^4) + y^2(1 + y + y^2 + y^3 + y^4) + y^3(1 + y + y^2 + y^3 + y^4) =1+y+y2+y3+y4+y(1+y+y2+y3+y4)+y2(1+y+y2+y3+y4)+y3(1+y+y2+y3+y4) = 1 + 2 y + 3 y 2 + 4 y 3 + 4 y 4 + 3 y 5 + 2 y 6 + y 7 =1+2y + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7 =1+2y+3y2+4y3+4y4+3y5+2y6+y7

④ 将 ③ 结果代入到 ② 中 : G ( y ) = ( 1 + 2 y + 3 y 2 + 4 y 3 + 4 y 4 + 3 y 5 + 2 y 6 + y 7 ) ( 1 + y + y 2 + y 3 + y 4 + y 5 ) G(y) = (1+2y + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7) (1 + y + y^2 + y^3 + y^4 + y^5) G(y)=(1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5)

⑤ 上式全部展开没有意义 , 这里我们只统计 y^10 的组合 :

• 1> 其中 3 y 5 3y^5 3y5 与 y 5 y^5 y5 可以乘出一个 3 y 10 3y^{10} 3y10
• 2> 其中 2 y 6 2y^6 2y6 与 y 4 y^4 y4 可以乘出一个 2 y 10 2y^{10} 2y10
• 3> 其中 y 7 y^7 y7 与 y 4 y^4 y4 可以乘出一个 y 10 y^{10} y10

⑥ 最终结果相加 : y 10 y^{10} y10 前的系数为 6 ;

不定方程解个数 x 取值范围为 ( 0 ~ n )

该情况下 值 与 多重集 的组 r − r- r− 组合数是等价的 ; 此时的多重集中每个元素的个数 是限定在 0 0 0 到 某个数 n n n 之间的 ;

这是是之前的多重集排列公式无法计算的情况 , 此处使用生成函数可以统计 多重集 的 r − r- r− 组合数 ;

以下三个值是等价的 :

① 不定方程 x 1 + x 2 + ⋯ + x k = r ( x i ≤ n i ) x_1 + x_2 + \cdots + x_k = r (x_i \leq n_i) x1​+x2​+⋯+xk​=r(xi​≤ni​) 的解个数 ;

② 多重集 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​} 的 r − r- r− 组合数

③ 生成函数 G ( y ) = ( 1 + y + y 2 + ⋯ + y n 1 ) ( 1 + y + y 2 + ⋯ + y n 2 ) ⋯ ( 1 + y + y 2 + ⋯ + y n k ) G(y) = (1+y+y^2 + \cdots + y^{n_1}) (1+y+y^2 + \cdots + y^{n_2})\cdots (1+y+y^2 + \cdots + y^{n_k}) G(y)=(1+y+y2+⋯+yn1​)(1+y+y2+⋯+yn2​)⋯(1+y+y2+⋯+ynk​) 展开后 y r y^r yr 的系数 ;

生成函数中 y y y 的幂从 0 0 0 到 n i n_i ni​ , 1 1 1 是 y 0 y^0 y0 ;

x i x_i xi​ 对应的是多重集中的 , 指定某元素 a i a_i ai​ 的个数 ;

不定方程解个数 x 取值范围为 自然数 ( 0 ~ ∞ ) 符合多重集组合公式计算情况

该情况下 值 与 多重集 的组 r − r- r− 组合数是等价的 ; 此时的多重集中每个元素的个数 是无限的 或者 大于 等于 r r r ;

该情况下的多重集组合问题 , 可以使用组合公式 , 多重集 的 r − r- r− 组合 , 其有 k k k 种元素 每种个数大于等于 r r r 或 无限 ; 使用公式 C ( r + k − 1 , r ) C(r + k - 1, r) C(r+k−1,r)

以下三个值是等价的 :

① 不定方程 x 1 + x 2 + ⋯ + x k = r ( 0 ≤ x i ) x_1 + x_2 + \cdots + x_k = r ( 0 \leq x_i) x1​+x2​+⋯+xk​=r(0≤xi​) 的解个数 ;

② 多重集 S = { ∞ ⋅ a 1 , ∞ ⋅ a 2 , ⋯   , ∞ ⋅ a k } S = \{\infty \cdot a_1 , \infty \cdot a_2 , \cdots , \infty \cdot a_k \} S={∞⋅a1​,∞⋅a2​,⋯,∞⋅ak​} 的 r − r- r− 组合数

③ 生成函数 G ( y ) = ( 1 + y + y 2 + ⋯   ) k G(y) = (1+y+y^2 + \cdots )^k G(y)=(1+y+y2+⋯)k 展开后 y r y^r yr 的系数 ;

生成函数中 y y y 的幂从 0 0 0 到 n i n_i ni​ , 1 1 1 是 y 0 y^0 y0 ;

x i x_i xi​ 对应的是多重集中的 , 指定某元素 a i a_i ai​ 的个数 ;

不定方程解个数 x 取值范围 ( 给定一个范围 )

该情况下 多重集的组合 问题就该退出舞台了 , 只剩下 不定方程解 和 生成函数的系数 了 , x i x_i xi​ 的取值有可能是负的 ;

以下两个值是等价的 :

① 不定方程 x 1 + x 2 + ⋯ + x k = r ( l i ≤ x i ≤ n j ) x_1 + x_2 + \cdots + x_k = r ( l_i \leq x_i \leq n_j) x1​+x2​+⋯+xk​=r(li​≤xi​≤nj​) 的解个数 ;

② 生成函数 G ( y ) = ( y l 1 + ⋯ + y n 1 ) ( y l 2 + ⋯ + y n 2 ) ⋯ ( y l k + ⋯ + y n k ) G(y) = (y^{l_1} + \cdots + y^{n_1})(y^{l_2} + \cdots + y^{n_2})\cdots(y^{l_k} + \cdots + y^{n_k}) G(y)=(yl1​+⋯+yn1​)(yl2​+⋯+yn2​)⋯(ylk​+⋯+ynk​) 展开后 y r y^r yr 的系数 ;

③ 多重集问题在这里就不太适用了 , x x x 取值有可能是负数 ;

生成函数中 y y y 的幂从 i i i 到 j j j ;

不定方程解个数 x 取值范围 ( 给定一个范围 并带系数 )

以下两个值是等价的 :

① 不定方程 p 1 x 1 + p 2 x 2 + ⋯ + p k x k = r ( l i ≤ x i ≤ n j ) p_1x_1 + p_2x_2 + \cdots + p_kx_k = r ( l_i \leq x_i \leq n_j) p1​x1​+p2​x2​+⋯+pk​xk​=r(li​≤xi​≤nj​) 的解个数 ;

② 生成函数 G ( y ) = ( ( y 1 p ) l 1 + ⋯ + ( y 1 p ) n 1 ) ( ( y 2 p ) l 2 + ⋯ + ( y 2 p ) n 2 ) ⋯ ( ( y k p ) l k + ⋯ + ( y k p ) n k ) G(y) = ((y^p_1)^{l_1} + \cdots + (y^p_1)^{n_1})((y^p_2)^{l_2} + \cdots + (y^p_2)^{n_2})\cdots((y^p_k)^{l_k} + \cdots + (y^p_k)^{n_k}) G(y)=((y1p​)l1​+⋯+(y1p​)n1​)((y2p​)l2​+⋯+(y2p​)n2​)⋯((ykp​)lk​+⋯+(ykp​)nk​) 展开后 y r y^r yr 的系数 ;

③ 多重集问题在这里就不太适用了 , x x x 取值有可能是负数 ;

注意不定方程带系数的情况下 , 生成函数中需要使用 y 系 数 y^{系数} y系数 替代 y y y , 生成函数中 y 系 数 y^{系数} y系数 的幂从 i i i 到 j j j ;

不定方程解的题目 带限制的情况

题目 : 求方程 x 1 + x 2 + x 3 + x 4 = 15 x_1 + x_2 + x_3 + x_4 = 15 x1​+x2​+x3​+x4​=15 的整数解个数 , 其中 x 1 ≥ 1 , x 2 ≥ 2 , x 3 ≥ 4 , x 4 ≥ 4 x_1 \geq 1 , x_2 \geq 2 , x_3 \geq 4 , x_4 \geq 4 x1​≥1,x2​≥2,x3​≥4,x4​≥4 ;

分析 :

• 1>不要直接求解 : 直接列出生成函数 , 就将问题复杂化了 ;
• 2> 换元转化 : 这里可以将其转为 非负整数解的个数来计算 ;
• 3> 多重集组合数 : 此时就等价于 多重集 S = { ∞ ⋅ a 1 , ∞ ⋅ a 2 , ⋯   , ∞ ⋅ a k } S = \{\infty \cdot a_1 , \infty \cdot a_2 , \cdots , \infty \cdot a_k \} S={∞⋅a1​,∞⋅a2​,⋯,∞⋅ak​} 的 r − r- r− 组合数 , 使用 多重集组合数公式 C ( r + k − 1 , r ) C(r + k - 1, r) C(r+k−1,r) 计算 ;

解 :

① 换元准备 :

• 1> 令 y 1 = x 1 − 1 y_1 = x_1 - 1 y1​=x1​−1 , 此时 y 1 y_1 y1​ 的取值范围是 N N N ( 自然数 ) ;
• 2> 令 y 2 = x 2 − 2 y_2 = x_2 - 2 y2​=x2​−2 , 此时 y 2 y_2 y2​ 的取值范围是 N N N ( 自然数 ) ;
• 3> 令 y 3 = x 3 − 4 y_3 = x_3 - 4 y3​=x3​−4 , 此时 y 3 y_3 y3​ 的取值范围是 N N N ( 自然数 ) ;
• 4> 令 y 4 = x 4 − 4 y_4 = x_4 - 4 y4​=x4​−4 , 此时 y 4 y_4 y4​ 的取值范围是 N N N ( 自然数 ) ;

② 换元过程 :

• 1> 使用 y 1 + 1 y_1 + 1 y1​+1 替换 x 1 x_1 x1​ ;
• 2> 使用 y 2 + 2 y_2 + 2 y2​+2 替换 x 2 x_2 x2​ ;
• 3> 使用 y 3 + 4 y_3 + 4 y3​+4 替换 x 3 x_3 x3​ ;
• 4> 使用 y 4 + 4 y_4 + 4 y4​+4 替换 x 4 x_4 x4​ ;

x 1 + x 2 + x 3 + x 4 = 15 x_1 + x_2 + x_3 + x_4 = 15 x1​+x2​+x3​+x4​=15 ( y 1 + 1 ) + ( y 2 + 2 ) + ( y 3 + 4 ) + ( y 4 + 4 ) = 15 (y_1 + 1) + (y_2 + 2) + (y_3 + 4) + (y_4 + 4) = 15 (y1​+1)+(y2​+2)+(y3​+4)+(y4​+4)=15 y 1 + y 2 + y 3 + y 4 + 11 = 15 y_1 + y_2 + y_3+y_4 + 11 = 15 y1​+y2​+y3​+y4​+11=15 y 1 + y 2 + y 3 + y 4 = 4 y_1 + y_2 + y_3+y_4 = 4 y1​+y2​+y3​+y4​=4

③ 求 y 1 + y 2 + y 3 + y 4 = 4 y_1 + y_2 + y_3+y_4 = 4 y1​+y2​+y3​+y4​=4 ( y i y_i yi​ 是自然数 ) , 非负整数解个数 ; 相当于求 S = { ∞ ⋅ a 1 , ∞ ⋅ a 2 , ∞ ⋅ a 3 , ∞ ⋅ a 4 } S = \{\infty \cdot a_1 , \infty \cdot a_2 , \infty \cdot a_3, \infty \cdot a_4 \} S={∞⋅a1​,∞⋅a2​,∞⋅a3​,∞⋅a4​} 的 4 − 4- 4−组合数 , 根据公式 C ( r + k − 1 , r ) C(r + k - 1 , r) C(r+k−1,r) 计算 :

C ( 4 + 4 − 1 , 4 ) = C ( 7 , 4 ) = ( 7 4 ) = 7 ! ( 7 − 4 ) ! 4 ! = 7 × 6 × 5 × 4 × 3 × 2 × 1 4 × 3 × 2 × 1 × 3 × 2 × 1 = 35 C(4 + 4 - 1 , 4) = C(7,4) = \dbinom{7}{4} = \cfrac{7!}{(7-4)!4!} = \cfrac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1 \times 3 \times 2 \times 1} = 35 C(4+4−1,4)=C(7,4)=(47​)=(7−4)!4!7!​=4×3×2×1×3×2×17×6×5×4×3×2×1​=35

解这 整数解 个数的问题 : ① 如果 x i x_i xi​ 的取值范围是 自然数 或 可以转化成 自然数的 , 那就用 多重集 组合公式计算 ; ② 如果 x i x_i xi​ 的取值范围是一个闭区间 , 直接生成函数 展开 , 计算 y r y^r yr 的系数是多少 , 该系数就是整数解个数 ;