不同正整数之和

fungarwai · 发表于 2014-4-7 15:43:21

https://zh.wikipedia.org/wiki/%E ... 8%E5%88%86%E6%8B%86

这里有些方法我看不懂，如果大家觉得更好，可以拿出来让我学习

sunwukong · 发表于 2014-4-7 17:09:21

本帖最后由 sunwukong 于 2014-4-7 17:39 编辑

问题1：

4 个不同的正整数之和为 1000，这四个数要么全为偶数，要么全为奇数，这样的四元数组（不考虑顺序）有多少个？

转化为两个问题（郭大虾转的）：

问题 2：
4 个不同的正整数之和为 500，得到后各数*2；
问题 3：
4 个不同的正整数之和为 502，得到后各数*2-1。

先求问题 2：
\[a_1+a_2+a_3+a_4=500\]
\[1\leqslant a_1<a_2<a_3<a_4\]
设（注：“不同的正整数之和为定值”转化为“正整数之和为定值”的方法）
\[b_1=a_1-1\]
\[b_2=a_2-2\]
\[b_3=a_3-3\]
\[b_4=a_4-4\]
则
\[b_1+b_2+b_3+b_4=490\]
\[0\leqslant b_1\leqslant b_2\leqslant b_3\leqslant b_4\]

再代换

\[b_1=y_1\]
\[b_2=y_1+y_2\]
\[b_3=y_1+y_2+y_3\]
\[b_4=y_1+y_2+y_3+y_4\]

则
\[4y_1+3y_2+2y_3+y_4=490\]
$y_1$、$y_2$、$y_3$、$y_4$是整数，且$y_i \geqslant 0$
母函数为
$(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)(1+x^4+x^8+x^{12}+\cdots)=\frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)}$
化为部分分式和，或者泰勒展开求通项，然后找$x^{490}$的系数。

问题 3 与问题 2 类似，母函数也相同，不同的是找$x^{492}$的系数。

fungarwai · 发表于 2017-9-8 21:18:00

有人用群论算出了这类问题的结果

https://artofproblemsolving.com/ ... into_distinct_parts

$\frac{1}{24}(C_{495}^3+6(C_{248}^2+C_{247}^2)+8C_{165}^1+6\times 1+3C_{247}^1)=852514$

$\frac{1}{24}(C_{493}^3+6(C_{247}^2+C_{246}^2)+8C_{164}^1+6\times 0+3C_{246}^1)=842263$

王守恩 · 发表于 2017-9-11 08:47:51

fungarwai 发表于 2017-9-8 21:18
有人用群论算出了这类问题的结果

https://artofproblemsolving.com/community/c4h1509410_number_of_int ...

10 1
11 1
12 2
13 3
14 5
15 6
16 9
17 11
18 15
19 18
20 23
21 27
22 34
23 39
24 47
25 54
26 64
27 72
28 84
29 94
30 108
31 120
32 136
33 150
34 169
35 185
36 206
37 225
38 249
39 270
40 297
41 321
42 351
43 378
44 411
45 441
46 478
47 511
48 551
49 588
50 632
51 672
52 720
53 764
54 816
55 864
56 920
57 972
58 1033
59 1089
60 1154
61 1215
62 1285
63 1350
64 1425
65 1495
66 1575
67 1650
68 1735
69 1815
70 1906
71 1991
72 2087
73 2178
74 2280
75 2376
76 2484
77 2586
78 2700
79 2808
80 2928
81 3042
82 3169
83 3289
84 3422
85 3549
86 3689
87 3822
88 3969
89 4109
90 4263
91 4410
92 4571
93 4725
94 4894
95 5055
96 5231
97 5400
98 5584
99 5760
100 5952
101 6136
102 6336
103 6528
104 6736
105 6936
106 7153
107 7361
108 7586
109 7803
110 8037
111 8262
112 8505
113 8739
114 8991
115 9234
116 9495
117 9747
118 10018
119 10279
120 10559
121 10830
122 11120
123 11400
124 11700
125 11990
126 12300
127 12600
128 12920
129 13230
130 13561
131 13881
132 14222
133 14553
134 14905
135 15246
136 15609
137 15961
138 16335
139 16698
140 17083
141 17457
142 17854
143 18239
144 18647
145 19044
146 19464
147 19872
148 20304
149 20724
150 21168
151 21600
152 22056
153 22500
154 22969
155 23425
156 23906
157 24375
158 24869
159 25350
160 25857
161 26351
162 26871
163 27378
164 27911
165 28431
166 28978
167 29511
168 30071
169 30618
170 31192
171 31752
172 32340
173 32914
174 33516
175 34104
176 34720
177 35322
178 35953
179 36569
180 37214
181 37845
182 38505
183 39150
184 39825
185 40485
186 41175
187 41850
188 42555
189 43245
190 43966
191 44671
192 45407
193 46128
194 46880
195 47616
196 48384
197 49136
198 49920
199 50688
200 51488
201 52272
202 53089
203 53889
204 54722
205 55539
206 56389
207 57222
208 58089
209 58939
210 59823
211 60690
212 61591
213 62475
214 63394
215 64295
216 65231
217 66150
218 67104
219 68040
220 69012
221 69966
222 70956
223 71928
224 72936
225 73926
226 74953
227 75961
228 77006
229 78033
230 79097
231 80142
232 81225
233 82289
234 83391
235 84474
236 85595
237 86697
238 87838
239 88959
240 90119
241 91260
242 92440
243 93600
244 94800
245 95980
246 97200
247 98400
248 99640
249 100860
250 102121
251 103361
252 104642
253 105903
254 107205
255 108486
256 109809
257 111111
258 112455
259 113778
260 115143
261 116487
262 117874
263 119239
264 120647
265 122034
266 123464
267 124872
268 126324
269 127754
270 129228
271 130680
272 132176
273 133650
274 135169
275 136665
276 138206
277 139725
278 141289
279 142830
280 144417
281 145981
282 147591
283 149178
284 150811
285 152421
286 154078
287 155711
288 157391
289 159048
290 160752
291 162432
292 164160
293 165864
294 167616
295 169344
296 171120
297 172872
298 174673
299 176449
300 178274
301 180075
302 181925
303 183750
304 185625
305 187475
306 189375
307 191250
308 193175
309 195075
310 197026
311 198951
312 200927
313 202878
314 204880
315 206856
316 208884
317 210886
318 212940
319 214968
320 217048
321 219102
322 221209
323 223289
324 225422
325 227529
326 229689
327 231822
328 234009
329 236169
330 238383
331 240570
332 242811
333 245025
334 247294
335 249535
336 251831
337 254100
338 256424
339 258720
340 261072
341 263396
342 265776
343 268128
344 270536
345 272916
346 275353
347 277761
348 280226
349 282663
350 285157
351 287622
352 290145
353 292639
354 295191
355 297714
356 300295
357 302847
358 305458
359 308039
360 310679
361 313290
362 315960
363 318600
364 321300
365 323970
366 326700
367 329400
368 332160
369 334890
370 337681
371 340441
372 343262
373 346053
374 348905
375 351726
376 354609
377 357461
378 360375
379 363258
380 366203
381 369117
382 372094
383 375039
384 378047
385 381024
386 384064
387 387072
388 390144
389 393184
390 396288
391 399360
392 402496
393 405600
394 408769
395 411905
396 415106
397 418275
398 421509
399 424710
400 427977
401 431211
402 434511
403 437778
404 441111
405 444411
406 447778
407 451111
408 454511
409 457878
410 461312
411 464712
412 468180
413 471614
414 475116
415 478584
416 482120
417 485622
418 489193
419 492729
420 496334
421 499905
422 503545
423 507150
424 510825
425 514465
426 518175
427 521850
428 525595
429 529305
430 533086
431 536831
432 540647
433 544428
434 548280
435 552096
436 555984
437 559836
438 563760
439 567648
440 571608
441 575532
442 579529
443 583489
444 587522
445 591519
446 595589
447 599622
448 603729
449 607799
450 611943
451 616050
452 620231
453 624375
454 628594
455 632775
456 637031
457 641250
458 645544
459 649800
460 654132
461 658426
462 662796
463 667128
464 671536
465 675906
466 680353
467 684761
468 689246
469 693693
470 698217
471 702702
472 707265
473 711789
474 716391
475 720954
476 725595
477 730197
478 734878
479 739519
480 744239
481 748920
482 753680
483 758400
484 763200
485 767960
486 772800
487 777600
488 782480
489 787320
490 792241
491 797121
492 802082
493 807003
494 812005
495 816966
496 822009
497 827011
498 832095
499 837138
500 842263
501 847347
502 852514
基础资料，找不到规律吗？

王守恩 · 发表于 2017-9-12 08:16:00

本帖最后由王守恩于 2017-9-12 12:15 编辑

fungarwai 发表于 2017-9-8 21:18
有人用群论算出了这类问题的结果

https://artofproblemsolving.com/ ... 09410_number_of_int ...

谢谢fungarwai！出了道好题！
5+81×18+23C(81,2)+9C(81,3)-40×40=842263
1+82× 8 +17C(82,2)+9C(82,3)-40×41=852514
还有简单的吗？

只是呼吸 · 发表于 2017-9-12 20:11:01

本帖最后由只是呼吸于 2017-9-12 20:15 编辑

没有学过“母函数”，真的不懂。不过看起来“母函数”是一个强大的数学武器，我有了学习的冲动。
王守恩的那两个试子，看上去简单，但不知道那些数字是怎么来的，能解释一下吗？

王守恩 · 发表于 2017-9-12 21:49:20

fungarwai 发表于 2017-9-8 21:18
有人用群论算出了这类问题的结果

https://artofproblemsolving.com/community/c4h1509410_number_of_int ...

谢谢fungarwai！出了道好题！
如果我们把4个数合在一起，则更简单。
例：498+499+500+501=3358843
7+122×(40÷122÷3+24)+28C(122,2)+32C(122,3)/3
在这里：只要改动122,40，其他数不用改动。
有兴趣的网友，自己找些数试一试。
希望你找到更简单的！

王守恩 · 发表于 2017-9-19 11:20:24

本帖最后由王守恩于 2017-9-19 11:25 编辑

只是呼吸发表于 2017-9-12 20:11
没有学过“母函数”，真的不懂。不过看起来“母函数”是一个强大的数学武器，我有了学习的冲动。
王守恩的 ...

小结。
题目：4个不同正整数之和是n，求n不同取法的种数S(n)。

解法：根据余数不同把n分成6类，我们有以下公式。
S(6K+10)=1+ 8 K+17C(K,2)+9C(K,3)-A或B
S(6K+11)=1+10K+18C(K,2)+9C(K,3)
S(6K+12)=2+13K+19C(K,2)+9C(K,3)+A或B
S(6K+13)=3+15K+21C(K,2)+9C(K,3)
S(6K+14)=5+18K+23C(K,2)+9C(K,3)-A或B
S(6K+15)=6+21K+24C(K,2)+9C(K,3)
说明：
1，当K是奇数时，A=((K-1)/2)×((K-1)/2)
2，当K是偶数时，B=((K-2)/2)×((K-0)/2)
3，基础资料详见14#楼。

谢谢只是呼吸！
谢谢fungarwai！
谢谢hujunhua先生！
谢谢许多没有见过面的网友！

只是呼吸 · 发表于 2017-9-20 09:10:02

题目：4个不同正整数之和是n，求n不同取法的种数S(n)。

解法：根据余数不同把n分成6类，我们有以下公式。
S(6K+10)=1+ 8 K+17C(K,2)+9C(K,3)-A或B
S(6K+11)=1+10K+18C(K,2)+9C(K,3)
S(6K+12)=2+13K+19C(K,2)+9C(K,3)+A或B
S(6K+13)=3+15K+21C(K,2)+9C(K,3)
S(6K+14)=5+18K+23C(K,2)+9C(K,3)-A或B
S(6K+15)=6+21K+24C(K,2)+9C(K,3)

王守恩的这几个公式，算出来的结果是对的。厉害！
查阅王守恩的其他贴子，王守恩能紧紧抓住数字之间的若有若无的联系，让复杂的问题变得简单。

王守恩 · 发表于 2017-9-24 20:58:18

只是呼吸发表于 2017-9-20 09:10
王守恩的这几个公式，算出来的结果是对的。厉害！
查阅王守恩的其他贴子，王守恩能紧紧抓住数字之间的若 ...

题目改动一下：
4个不同正整数(最大正整数不超过n/2)之和是n，求n不同取法的种数S(n)。

账号		自动登录	找回密码
密码			欢迎注册

[提问] 不同正整数之和

点评