【组合数学】不定方程解个数问题 ( 多重集r组合数 | 不定方程非负整数解个数 | 生成函数展开式中 r 次幂系数

文章目录

- - - 多重集 r 组合数生成函数计算方法
    - 多重集 r 组合数题目
    - 不定方程解个数 x 取值范围为 ( 0 ~ n )
    - 不定方程解个数 x 取值范围为自然数 ( 0 ~ ∞ ) 符合多重集组合公式计算情况
    - 不定方程解个数 x 取值范围 ( 给定一个范围 )
    - 不定方程解个数 x 取值范围 ( 给定一个范围并带系数 )
    - 不定方程解的题目带限制的情况

多重集 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 = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$ 的

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)

$x_{1} + x_{2} + \dots + x_{k} = r (x_{i} \leq n_{i})$ 的非负整数解个数 ;

③ 生成函数

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 + y^{2} + \dots + y^{n_{1}}) (1 + y + y^{2} + \dots + y^{n_{2}}) \dots (1 + y + y^{2} + \dots + y^{n_{k}})$ 展开后

y

r

y^r

$y^{r}$ 的系数 ;

生成函数中

y

y

$y$ 的幂从

0

0

$0$ 到

n

i

n_i

$n_{i}$ ,

1

1

$1$ 是

y

0

y^0

$y^{0}$ ;

x

i

x_i

$x_{i}$ 对应的是多重集中的 , 指定某元素

a

i

a_i

$a_{i}$ 的个数 ;

多重集 r 组合数题目

题目 : 计算

S

=

{

3

⋅

a

,

4

⋅

b

,

5

⋅

c

}

S=\{3 \cdot a , 4 \cdot b , 5 \cdot c\}

$S = {3 \cdot a, 4 \cdot b, 5 \cdot c}$ 的 10-组合数 ;

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

1>多重集 $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 $ , $\leq x_1 \leq 3, 0 \leq x_2 \leq 4, 0 \leq x_3 \leq 5$
$0 \leq x_{1} \leq 3, 0 \leq x_{2} \leq 4, 0 \leq x_{3} \leq 5$ 的非负整数解个数 ;
3>生成函数 $(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}$
$y^{10}$ 的系数 ;

解 :

① 展开上述生成函数 :

(

)

(

)

(

)

(

)

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})$

② 其中

y

0

=

1

y^0 = 1

$y^{0} = 1$ ,

y

1

=

y

y^1 =y

$y^{1} = 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

+

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 + 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 + y^{2} + 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 + 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+2y + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7

$= 1 + 2 y + 3 y^{2} + 4 y^{3} + 4 y^{4} + 3 y^{5} + 2 y^{6} + y^{7}$

④ 将 ③ 结果代入到 ② 中 :

(

)

(

)

(

)

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 + 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})$

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

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

⑥ 最终结果相加 :

y

10

y^{10}

$y^{10}$ 前的系数为 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)

$x_{1} + x_{2} + \dots + x_{k} = r (x_{i} \leq n_{i})$ 的解个数 ;

② 多重集

$r -$ 组合数

③ 生成函数

$y^{r}$ 的系数 ;

生成函数中

y

y

$y$ 的幂从

0

0

$0$ 到

n

i

n_i

$n_{i}$ ,

1

1

$1$ 是

y

0

y^0

$y^{0}$ ;

x

i

x_i

$x_{i}$ 对应的是多重集中的 , 指定某元素

a

i

a_i

$a_{i}$ 的个数 ;

不定方程解个数 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)

$x_{1} + x_{2} + \dots + x_{k} = r (0 \leq x_{i})$ 的解个数 ;

② 多重集

S

=

{

∞

⋅

a

1

,

∞

⋅

a

2

,

⋯
 

,

∞

⋅

a

k

}

S = \{\infty \cdot a_1 , \infty \cdot a_2 , \cdots , \infty \cdot a_k \}

$S = {\infty \cdot a_{1}, \infty \cdot a_{2}, \dots, \infty \cdot a_{k}}$ 的

r

−

r-

$r -$ 组合数

③ 生成函数

G

(

y

)

=

(

1

+

y

+

y

2

+

⋯
 

)

k

G(y) = (1+y+y^2 + \cdots )^k

$G (y) = (1 + y + y^{2} + \dots)^{k}$ 展开后

y

r

y^r

$y^{r}$ 的系数 ;

生成函数中

y

y

$y$ 的幂从

0

0

$0$ 到

n

i

n_i

$n_{i}$ ,

1

1

$1$ 是

y

0

y^0

$y^{0}$ ;

x

i

x_i

$x_{i}$ 对应的是多重集中的 , 指定某元素

a

i

a_i

$a_{i}$ 的个数 ;

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

该情况下多重集的组合问题就该退出舞台了 , 只剩下不定方程解和生成函数的系数了 ,

x

i

x_i

$x_{i}$ 的取值有可能是负的 ;

以下两个值是等价的 :

① 不定方程

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)

$x_{1} + x_{2} + \dots + x_{k} = r (l_{i} \leq x_{i} \leq n_{j})$ 的解个数 ;

② 生成函数

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) = (y^{l_{1}} + \dots + y^{n_{1}}) (y^{l_{2}} + \dots + y^{n_{2}}) \dots (y^{l_{k}} + \dots + y^{n_{k}})$ 展开后

y

r

y^r

$y^{r}$ 的系数 ;

③ 多重集问题在这里就不太适用了 ,

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)

$p_{1} x_{1} + p_{2} x_{2} + \dots + p_{k} x_{k} = r (l_{i} \leq x_{i} \leq n_{j})$ 的解个数 ;

② 生成函数

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) = ((y_{1}^{p})^{l_{1}} + \dots + (y_{1}^{p})^{n_{1}}) ((y_{2}^{p})^{l_{2}} + \dots + (y_{2}^{p})^{n_{2}}) \dots ((y_{k}^{p})^{l_{k}} + \dots + (y_{k}^{p})^{n_{k}})$ 展开后

y

r

y^r

$y^{r}$ 的系数 ;

③ 多重集问题在这里就不太适用了 ,

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

$x_{1} + x_{2} + x_{3} + x_{4} = 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

$x_{1} \geq 1, x_{2} \geq 2, x_{3} \geq 4, x_{4} \geq 4$ ;

分析 :

1>不要直接求解 : 直接列出生成函数 , 就将问题复杂化了 ;
2> 换元转化 : 这里可以将其转为非负整数解的个数来计算 ;
3> 多重集组合数 : 此时就等价于多重集 $\{\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 y1=x1−1 , 此时 y 1 y_1 y1 的取值范围是 N N N ( 自然数 ) ;$
2> 令 $y_2 = x_2 - 2 y2=x2−2 , 此时 y 2 y_2 y2 的取值范围是 N N N ( 自然数 ) ;$
3> 令 $y_3 = x_3 - 4 y3=x3−4 , 此时 y 3 y_3 y3 的取值范围是 N N N ( 自然数 ) ;$
4> 令 $y_4 = x_4 - 4 y4=x4−4 , 此时 y 4 y_4 y4 的取值范围是 N N N ( 自然数 ) ;$

② 换元过程 :

1> 使用 $y_1 + 1 y1+1 替换 x 1 x_1 x1 ;$
2> 使用 $y_2 + 2 y2+2 替换 x 2 x_2 x2 ;$
3> 使用 $y_3 + 4 y3+4 替换 x 3 x_3 x3 ;$
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$

(

)

(

)

(

)

(

)

(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$

y_1 + y_2 + y_3+y_4 + 11 = 15

$y_{1} + y_{2} + y_{3} + y_{4} + 11 = 15$

y_1 + y_2 + y_3+y_4 = 4

$y_{1} + y_{2} + y_{3} + y_{4} = 4$

③ 求

y

1

+

y

2

+

y

3

+

y

4

=

4

y_1 + y_2 + y_3+y_4 = 4

$y_{1} + y_{2} + y_{3} + y_{4} = 4$ (

y

i

y_i

$y_{i}$ 是自然数 ) , 非负整数解个数 ;
相当于求

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 = {\infty \cdot a_{1}, \infty \cdot a_{2}, \infty \cdot a_{3}, \infty \cdot a_{4}}$ 的

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) = \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) = (4 7) = \frac{7 !}{( 7 - 4 ) ! 4 !} = \frac{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$

解这整数解个数的问题 :
① 如果

x

i

x_i

$x_{i}$ 的取值范围是自然数或可以转化成自然数的 , 那就用多重集组合公式计算 ;
② 如果

x

i

x_i

$x_{i}$ 的取值范围是一个闭区间 , 直接生成函数展开 , 计算

y

r

y^r

$y^{r}$ 的系数是多少 , 该系数就是整数解个数 ;

【组合数学】不定方程解个数问题 ( 多重集r组合数 | 不定方程非负整数解个数 | 生成函数展开式中 r 次幂系数 | 给定范围/系数情况下不定方程整数解个数 )

文章目录

多重集 r 组合数生成函数计算方法

多重集 r 组合数题目

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

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

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

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

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

相关推荐

一个分享Java & Python知识的社区

文章目录

多重集 r 组合数 生成函数计算方法

多重集 r 组合数题目

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

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

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

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

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

相关推荐

一个分享Java & Python知识的社区

多重集 r 组合数生成函数计算方法

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

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

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