不同正整数之和

fungarwai

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

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

sunwukong

问题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

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

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$

王守恩

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
基础资料，找不到规律吗？

王守恩

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
还有简单的吗？

只是呼吸

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

王守恩

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-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先生！
谢谢许多没有见过面的网友！

只是呼吸

题目：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-20 09:10
王守恩的这几个公式，算出来的结果是对的。厉害！
查阅王守恩的其他贴子，王守恩能紧紧抓住数字之间的若 ...

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