不定方程非负整数解的个数

青青子衿

Let \(N\left(a_1,a_2,a_3\,;b\right)\) denote the number of  non-negative integer solutions of the equation:
\[a_1x_1+a_2x_2+a_3x_3=b\]
where  \(a_1,a_2,a_3,b\in\mathbb{Z_+}\) and \(\gcd(a_1,a_2)=\gcd(a_2,a_3)=\gcd(a_1,a_3)=1\)
\begin{align*}
N\left(1,2,3\,;b\right)&=\frac{1}{12}b^2+\frac{1}{2}b+\frac{47}{72}+\frac{1}{8}\cos(\pi b)+\frac{2}{9}\cos\left(\frac{2\pi}{3}b\right)\\
\\
N\left(1,2,5\,;b\right)&=\frac{1}{20}b^2+\frac{2}{5}b+\frac{27}{40}+\frac{1}{8}\cos(\pi b)+\frac{2\sqrt{5}}{25}\cos\left[\frac{2\pi}{5}(b-1)\right]+\frac{2\sqrt{5}}{25}\cos\left[\frac{\pi}{5}(4b+1)\right]\\
\\
N\left(1,3,4\,;b\right)&=\frac{1}{24}b^2+\frac{1}{3}b+\frac{83}{144}+\frac{2}{9}\cos\left[\frac{\pi}{3}(2b-1)\right]+\frac{1}{4}\cos\left(\frac{\pi}{2}b\right)+\frac{1}{16}\cos(\pi b)\\
\\
N\left(1,3,5\,;b\right)&=\frac{1}{30}b^2+\frac{3}{10}b+\frac{26}{45}+\frac{2}{9}\cos\left(\frac{2\pi}{3}b\right)+\frac{2\sqrt{5}}{25}\cos\left[\frac{\pi}{5}(2b-1)\right]+\frac{2\sqrt{5}}{25}\cos\left[\frac{2\pi}{5}(2b-1)\right]\\
\\
N\left(1,4,5\,;b\right)&=\frac{1}{40}b^2+\frac{1}{4}b+\frac{43}{80}+\frac{1}{4}\cos\left[\frac{\pi}{2}(b-1)\right]+\frac{1}{16}\cos(\pi b)+\frac{8}{25}\sin^2\left(\frac{2\pi}{5}\right)\cos\left(\frac{2\pi}{5}b\right)+\frac{8}{25}\sin^2\left(\frac{\pi}{5}\right)\cos\left(\frac{4\pi}{5}b\right)\\
\\
N\left(2,3,5\,;b\right)&=\frac{1}{60}b^2+\frac{1}{6}b+\frac{131}{360}+\frac{1}{8}\cos(\pi b)+\frac{2}{9}\cos\left[\frac{\pi}{3}(2b+1)\right]+\frac{8}{25}\sin^2\left(\frac{\pi}{5}\right)\cos\left(\frac{2\pi}{5}b\right)+\frac{8}{25}\sin^2\left(\frac{2\pi}{5}\right)\cos\left(\frac{4\pi}{5}b\right)\\
\\
N\left(3,4,5\,;b\right)&=\frac{1}{120}b^2+\frac{1}{10}b+\frac{191}{720}+\frac{2}{9}\cos\left(\frac{2\pi}{3}b\right)+\frac{1}{4}\cos\left(\frac{\pi}{2}b\right)+\frac{1}{16}\cos(\pi b)+\frac{2\sqrt{5}}{25}\cos\left[\frac{2\pi}{5}(b+1)\right]+\frac{2\sqrt{5}}{25}\cos\left[\frac{\pi}{5}(4b-1)\right]
\end{align*}
Refence: On the number of solutions of the Diophantine equation of Frobenius – General case∗
Link: core.ac.uk/download/pdf/14375587.pdf

青青子衿

1. Subscript[N, 1, 2, 3][b_] := 1/12 b^2 + 1/2 b + 47/72 + 1/8 Cos[\[Pi] b] +  2/9 Cos[(2 \[Pi])/3 b];
2. Subscript[N, 1, 2, 5][b_] := 1/20 b^2 + 2/5 b + 27/40 + 1/8 Cos[\[Pi] b] + (2 Sqrt[5])/25 Cos[(2 \[Pi])/5 (b - 1)] + (2 Sqrt[5])/25 Cos[\[Pi]/5 (4 b + 1)];
3. Subscript[N, 1, 3, 4][b_] := 1/24 b^2 + 1/3 b + 83/144 + 2/9 Cos[\[Pi]/3 (2 b - 1)] + 1/4 Cos[\[Pi]/2 b] + 1/16 Cos[\[Pi] b];
4. Subscript[N, 1, 3, 5][b_] := 1/30 b^2 + 3/10 b + 26/45 + 2/9 Cos[(2 \[Pi])/3 b] + (2 Sqrt[5])/25 Cos[\[Pi]/5 (2 b - 1)] + (2 Sqrt[5])/25 Cos[(2 \[Pi])/5 (2 b - 1)];
5. Subscript[N, 1, 4, 5][b_] := 1/40 b^2 + 1/4 b + 43/80 + 1/4 Cos[\[Pi]/2 (b - 1)] + 1/16 Cos[\[Pi] b] + 8/25 (Sin[(2 \[Pi])/5])^2 Cos[(2 \[Pi])/5 b] + 8/25 (Sin[\[Pi]/5])^2 Cos[(4 \[Pi])/5 b];
6. Subscript[N, 2, 3, 5][b_] := 1/60 b^2 + 1/6 b + 131/360 + 1/8 Cos[\[Pi] b] + 2/9 Cos[\[Pi]/3 (2 b + 1)] + 8/25 (Sin[\[Pi]/5])^2 Cos[(2 \[Pi])/5 b] + 8/25 (Sin[(2 \[Pi])/5])^2 Cos[(4 \[Pi])/5 b];
7. Subscript[N, 3, 4, 5][b_] := 1/120 b^2 + 1/10 b + 191/720 + 2/9 Cos[(2 \[Pi])/3 b] + 1/4 Cos[\[Pi]/2 b] + 1/16 Cos[\[Pi] b] + (2 Sqrt[5])/25 Cos[(2 \[Pi])/5 (b + 1)] + (2 Sqrt[5])/25 Cos[\[Pi]/5 (4 b - 1)];

复制代码

1. FullSimplify[Subscript[N, 1, 2, 3][20]]
2. Solve[1 x + 2 y + 3 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
3. FullSimplify[Subscript[N, 1, 2, 5][20]]
4. Solve[1 x + 2 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
5. FullSimplify[Subscript[N, 1, 3, 4][20]]
6. Solve[1 x + 3 y + 4 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
7. FullSimplify[Subscript[N, 1, 3, 5][20]]
8. Solve[1 x + 3 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
9. FullSimplify[Subscript[N, 1, 4, 5][20]]
10. Solve[1 x + 4 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
11. FullSimplify[Subscript[N, 2, 3, 5][20]]
12. Solve[2 x + 3 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
13. FullSimplify[Subscript[N, 3, 4, 5][20]]
14. Solve[3 x + 4 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length

复制代码

kuing

太长，懒得看，估计也看不懂……

我目前用的方法也是母函数，只是后面的计算方法不同（好像是以前看tommywong用过，就学来了）。

设
\begin{align*}
F&=(1+x^{a_1}+x^{2a_1}+\cdots)(1+x^{a_2}+x^{2a_2}+\cdots)(1+x^{a_3}+x^{2a_3}+\cdots)\\
&=\frac1{(1-x^{a_1})(1-x^{a_2})(1-x^{a_3})},
\end{align*}
则所求的就是 `F` 中 `x^b` 的系数，记 `A=a_1a_2a_3`，因为
\[1-x^A=(1-x^{a_1})(1+x^{a_1}+x^{2a_1}+\cdots+x^{(a_2a_3-1)a_1}),\]
对 `a_2`, `a_3` 同理，所以
\[F=\frac{(1+x^{a_1}+\cdots+x^{(a_2a_3-1)a_1})(1+x^{a_2}+\cdots+x^{(a_3a_1-1)a_2})(1+x^{a_3}+\cdots+x^{(a_1a_2-1)a_3})}{(1-x^A)^3},\]
根据已知的展开公式有
\[\frac1{(1-x^A)^3}=C_2^2+C_3^2x^A+C_4^2x^{2A}+\cdots+C_{k+2}^2x^{kA}+\cdots,\]
那么，用和式写起来的话，就是
\[F=\sum_{k=0}^{a_2a_3-1}x^{ka_1}\sum_{k=0}^{a_3a_1-1}x^{ka_2}\sum_{k=0}^{a_1a_2-1}x^{ka_3}\sum_{k=0}^\infty C_{k+2}^2x^{kA},\]
然后对于具体的数字代入展开计算即可。

这种方法虽然不能得出一条统一的一般公式，但实际操作比较容易。

比如当 `(a_1,a_2,a_3)=(1,2,3)` 时
\[F=(1+x+\cdots+x^5)(1+x^2+x^4)(1+x^3)\sum_{k=0}^\infty C_{k+2}^2x^{6k},\]
如果 `b=100`，则由于 `100=16\times6+4=15\times6+10`，所以只需计算 `(1+x+\cdots+x^5)(1+x^2+x^4)(1+x^3)` 中 `x^4` 和 `x^{10}` 的系数，结果是 `4` 和 `2`，故此 `x^{100}` 的系数就是 `4C_{16+2}^2+2C_{15+2}^2=884`。

当然也可以将上式展开计算一下，过程就不写了，结果为
\begin{align*}
F={}&1+x+2x^2+3x^3+4x^4+5x^5+7x^6+8x^7+10x^8+12x^9+14x^{10}+16x^{11}\\
&+\sum_{k=2}^\infty x^{6k}\bigl[C_{k+2}^2+4C_{k+1}^2+C_k^2+(C_{k+2}^2+5C_{k+1}^2)x+(2C_{k+2}^2+4C_{k+1}^2)x^2\\
&+(3C_{k+2}^2+3C_{k+1}^2)x^3+(4C_{k+2}^2+2C_{k+1}^2)x^4+(5C_{k+2}^2+C_{k+1}^2)x^5\bigr].
\end{align*}

多元也是一样操作，总之对于实际情形来说，这种方法还算实用，而且比较容易理解。

isee

回复 3# kuing

具有一般性，多元不定方程非负整数解个数，mark，先

青青子衿

where  \(a_1,a_2,a_3,b\in\mathbb{Z_+}\) and \(\exists\gcd(a_i,a_j)\ne1\,(i,j=1,2,3)\)
\begin{align*}
N\left(1,2,4\,;b\right)&=\frac{1}{16}b^2+\frac{7}{16}b+\frac{21}{32}+\frac{1}{16}(b+1)\cos(\pi b)+\frac{5}{32}\cos(\pi b)+\frac{1}{8}\cos\left[\frac{\pi}{2}(b-1)\right]+\frac{1}{8}\cos\left(\frac{\pi}{2}b\right)\\
\\
N\left(2,3,4\,;b\right)&=\frac{1}{48}b^2+\frac{3}{16}b+\frac{107}{288}+\frac{1}{16}(b+1)\cos(\pi b)+\frac{7}{32}\cos(\pi b)+\frac{2}{9}\cos\left(\frac{2\pi}{3}b\right)+\frac{1}{8}\cos\left(\frac{\pi}{2}b\right)+\frac{1}{8}\cos\left[\frac{\pi}{2}(b+1)\right]\\
\\
N\left(2,4,5\,;b\right)&=\frac{1}{80}b^2+\frac{11}{80}b+\frac{53}{160}+\frac{1}{16}(b+1)\cos(\pi b)+\frac{9}{32}\cos(\pi b)+\frac{1}{8}\cos\left[\frac{\pi}{2}(b-1)\right]+\frac{1}{8}\cos\left(\frac{\pi}{2}b\right)+\frac{2\sqrt{5}}{25}\cos\left[\frac{\pi}{5}(2b+1)\right]+\frac{2\sqrt{5}}{25}\cos\left[\frac{2\pi}{5}(2b+1)\right]\\
\end{align*}

青青子衿

1. Subscript[N, 1, 2, 4][b_] := 1/16 b^2 + 7/16 b + 21/32 + 1/16 (b + 1) Cos[\[Pi] b] + 5/32 Cos[\[Pi] b] + 1/8 Cos[\[Pi]/2 (b - 1)] + 1/8 Cos[\[Pi]/2 b];
2. Subscript[N, 2, 3, 4][b_] := 1/48 b^2 + 3/16 b + 107/288 + 1/16 (b + 1) Cos[\[Pi] b] + 7/32 Cos[\[Pi] b] + 2/9 Cos[(2 \[Pi])/3 b] + 1/8 Cos[\[Pi]/2 b] + 1/8 Cos[\[Pi]/2 (b + 1)];
3. Subscript[N, 2, 4, 5][b_] := 1/80 b^2 + 11/80 b + 53/160 + 1/16 (b + 1) Cos[\[Pi] b] + 9/32 Cos[\[Pi] b] + 1/8 Cos[\[Pi]/2 (b - 1)] + 1/8 Cos[\[Pi]/2 b] + (2 Sqrt[5])/25 Cos[\[Pi]/5 (2 b + 1)] + (2 Sqrt[5])/25 Cos[(2 \[Pi])/5 (2 b + 1)];

复制代码

1. FullSimplify[Subscript[N, 1, 2, 4][20]]
2. Solve[1 x + 2 y + 4 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
3. FullSimplify[Subscript[N, 2, 3, 4][20]]
4. Solve[2 x + 3 y + 4 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length
5. FullSimplify[Subscript[N, 2, 4, 5][20]]
6. Solve[2 x + 4 y + 5 z == 20 && 0 <= x < 200 && 0 <= y < 200 && 0 <= z < 200, {x, y, z}, Integers] // Length

复制代码