不定方程整数解

发布时间 2023-08-22 22:11:32作者: jimhfz

1.一次不定方程 $x_1+x_2+...+x_n=m$ 的正整数解个数

考虑隔板法,将m看成m个小球,在中间放上n-1个隔板,每一个区域的小球个数作为一个x的解,很明显,有m-1个位置可以放上隔板,一共需放上n-1个,所以答案即为 $C^{n-1}_{m-1}$

可以理解为向n个盒子里放m个球(不能为空)

 

2.一次不定方程 $x_1+x_2+...+x_n=m$ 的非负整数解个数

这次盒子可以为空了,将方程转化一下
$$
(x_1+1)+(x_2+1)+...+(x_n+1)=m+n
$$
这样每个数都为正整数,由(1),答案即为 $C^{n-1}_{n+m-1}$

 

3.一次不定方程 $x_1+x_2+...+x_n=m$ ,满足 $x_i≥a_i$ 的正整数解个数

再次将方程转化一下
$$
(x_1-a_1+1)+(x_2-a_2+1)+...+(x_n-a_n+1)=m-\sum a_i+n
$$
相当于每次往特定的箱子里预先装入一些球,现在每个数都为正整数,由(1),答案即为 $C^{n-1}_{m+n-\sum a_i-1}$

 

4.一次不定方程 $x_1+x_2+...+x_n=m$ ,满足 $x_i≤a_i$ 的正整数解个数 (n<=20)

由于这个n很小,而且于反方向比较好思考(3),考虑容斥,把条件转化为不满足 $x_i≥a_i+1$ ,答案即为全部-其中一个不满足的+其中二个不满足的-... 枚举其中有哪些x不满足的二进制状态,根据多少x不满足的数量奇偶判断加减即可