x+y+2z=14 有几组非负整数解？求正整数 n，使得方程 x+y+2z=n 恰有 1260 组非负整数解

wintex

luyuanhong

luyuanhong

本题问的是：有几组非负整数解，不是有几组正整数解。

上面第 3 楼中的解答，漏掉了 x,y,z 可以取值为 0 的解。

补充了可以取值为 0 的解以后，得到数列是：

a(1)=2 ,  {0,1,0} ,{1,0,0}

a(2)=4 ,  {0,0,1},{0,2,0},{1,1,0},{2,0,0}

a(3)=6 ,  {0,1,1},{1,0,1},{0,3,0},{1,2,0},{2,1,0},{3,0,0}

a(4)=9 , {0,0,2},{0,2,1},{1,1,1},{2,0,1},{0,4,0},{1,3,0},{2,2,0},{3,1,0},{4,0,0}

…………

通项公式是  a(n)=[(n+2)/2] [(n+3)/2] ，其中 [ ] 表示向下取整。

王守恩

luyuanhong 发表于 2023-11-14 10:11
本题问的是：有几组非负整数解，不是有几组正整数解。

上面第 3 楼中的解答，漏掉了 x,y,z 可以取值为 0 ...

谢谢陆老师！
a(0)=01, {x,y,z}={0,0,0}
a(1)=02, {x,y,z}={0,1,0},{1,0,0},
a(2)=04, {x,y,z}={0,0,1},{0,2,1},{1,1,0},{2,0,0},
a(3)=06, {x,y,z}={0,1,1},{0,3,0},{1,0,1},{1,2,0},{2,1,0},{3,0,0},
a(4)=09, {x,y,z}={0,0,2},{0,2,1},{0,4,0},{1,1,1},{1,3,0},{2,0,1},{2,2,0},{3,1,0},{4,0,0},
a(5)=12, {x,y,z}={0,1,2},{0,3,1},{0,5,0},{1,0,2},{1,2,1},{1,4,0},{2,1,1},{2,3,0},{3,0,1},{3,2,0},{4,1,0},{5,0,0},
a(6)=16, {x,y,z}={0,0,3},{0,2,2},{0,4,1},{0,6,0},{1,1,2},{1,2,1},{1,5,0},{2,0,2},{2,2,1},{2,4,0},
                          {3,1,1},{3,3,0},{4,0,1},{4,2,0},{5,1,0},{6,0,0},

得到这样一串数:  {1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110,
121, 132, 144, 156, 169, 182, 196, 210, 225, 240, 256, 272, 289, 306, 324, 342, 361, 380,
400, 420, 441, 462, 484, 506, 529, 552, 576, 600, 625, 650, 676, 702, 729, 756, 784, 812,
841, 870, 900, 930, 961, 992, 1024, 1056, 1089, 1122, 1156, 1190, 1225, 1260}

1. Table[Floor[(n+2)^2/4], {n, 0, 69}]

复制代码

n是正偶数,  a(n)=(n+2)(n+2)/4
n是正奇数,  a(n)=(n+1)(n+3)/4

王守恩

1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121, 132, 144,
156, 169, 182, 196, 210, 225, 240, 256, 272, 289, 306, 324, 342, 361, 380, 400, 420,
441, 462, 484, 506, 529, 552, 576, 600, 625, 650, 676, 702, 729, 756, 784, 812, 841,
870, 900, 930, 961, 992, 1024, 1056, 1089, 1122, 1156, 1190, 1225, 1260，......

1. CoefficientList[Series[1/((1 - x) (1 - x) (1 - x^2)), {x, 0, 69}], x]

复制代码

1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 17, 18, 20, 22, 23, 25, 27, 29, 31,
33, 35, 37, 40, 42, 44, 47, 49, 52, 55, 57, 60, 63, 66, 69, 72, 75, 78, 82, 85, 88, 92, 95,
99, 103, 106, 110, 114, 118, 122, 126, 130, 134, 139, 143, 147, 152, 156, ......

1. CoefficientList[Series[1/((1 - x) (1 - x^3) (1 - x^5)), {x, 0, 64}],x]

复制代码

1, 1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54, 64, 72, 84, 94, 108, 120, 136, 150, 169,
185, 206, 225, 249, 270, 297, 321, 351, 378, 411, 441, 478, 511, 551, 588, 632, 672, 720,
764, 816, 864, 920, 972, 1033, 1089, 1154, 1215, 1285, 1350, 1425, 1495, 1575, ......

1. CoefficientList[Series[1/((1 - x)(1 - x^2)(1 - x^3)(1 - x^4)),{x,0,69}],x]

复制代码

谢谢 elim ！！！
很多数学思想(不是数学公式) 美得不得了!
把组合问题归结为多项式系数的思想了不起！

王守恩

谢谢陆老师！
x+y+2z=n 有几组非负整数解？
答案是这样一串数:  1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121, ...
循着答案找思路, 请看:
a(00)=01,
a(01)=02=01+1
a(02)=04=02+2=01+3
a(03)=06=04+2=02+4
a(04)=09=06+3=04+5
a(05)=12=09+3=06+6
a(06)=16=12+4=09+7
a(07)=20=16+4=12+8
a(08)=25=20+5=16+9
a(09)=30=25+5=20+10
a(10)=36=30+6=25+11
a(11)=42=36+6=30+12
a(12)=49=42+7=36+13
a(13)=56=49+7=42+14
a(14)=64=56+8=49+15
a(15)=72=64+8=56+16
a(16)=81=72+9=64+17
a(17)=90=81+9=72+18
通项公式是这样(OEIS可没有这样精炼的)。

1. Table[Floor[(n+2)^2/4], {n, 0, 69}]

复制代码

luyuanhong

楼上王守恩总结得很好！

这个数列的初始值和递推关系式是

a(0)=1 ， a(1)=2 ，a(n)=a(n-2)+n+1（n=2,3,4,…）。

如果分奇偶，这个数列的通项公式为

当 n 为偶数时，a(n)=(n+2)^2/4 ；当 n 为奇数时， a(n)=(n+1)(n+3)/4 。

如果不分奇偶，这个数列的通项公式可以写成：

a(n)=[(n+2)^2/4] 。其中 [ ] 表示向下取整。

lihp2020

有点同理的题  这是我昨天给的 让时间复杂度和空间复杂度降低的方法

王守恩

x+y+2z=n 有几组非负整数解？
答案是这样一串数:  1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121, ...
a(0)=01,                       {x,y,z}={0,0,0}
a(1)=02=01+1,            {x,y,z}={0,1,0},{1,0,0},
a(2)=04=02+2=01+3, {x,y,z}={0,0,1},{0,2,0},{1,1,0},{2,0,0},
a(3)=06=04+2=02+4, {x,y,z}={0,1,1},{0,3,0},{1,0,1},{1,2,0},{2,1,0},{3,0,0},
a(4)=09=06+3=04+5, {x,y,z}={0,0,2},{0,2,1},{0,4,0},{1,1,1},{1,3,0},{2,0,1},{2,2,0},{3,1,0},{4,0,0},
a(5)=12=09+3=06+6
a(6)=16=12+4=09+7
a(7)=20=16+4=12+8
a(8)=25=20+5=16+9
......
a(n)=a(n-1)+[(n+2)/2]=a(n-2)+(n+1)

循着答案可以有2条思路。

1,  a(n)=a(n-1)+[(n+2)/2]
a(n-1):  对a(n-1)中的 x, 进行+1即可。
[(n+2)/2]:  x=0时，z 可以有0,1,2,3,...共[(n+2)/2]种选择。

2,  a(n)=a(n-2)+(n+1)
a(n-2):  对a(n-2)中的 z, 进行+1即可。
(n+1):  z=0时，x 可以有0,1,2,3,...共(n+1)种选择。