{1,2,...,n}的和能被 m 整除的 m 元子集

mathe

对于n是M倍数时，C(u,n,h)会比较特殊，特别M是素数时会比较好计算。
设n=kM, 于是1~n中模M的不同余数都是k个。这k个同余的数相互替换对于这种和关于模M都是相同。
于是对于C(u,n,h)中某个实例，我们将其中每个数都加x（结果超过n的减去n),那么就可以得到一个C(u,n,(h+xu)(mod M))的结果。
由此，我们知道，如果(u,M)=1,那么对于所有不同的h都有C(u,kM,h)相等，等于$\frac{C_{kM}^u}M$.
如果(u,M)=d>1,我们可以得出对于部分h, C(u,n,h)相等，但是计算最终结果会有些复杂。
而我们现在比较关心u=M情况，这种情况对于一般的M分析起来比较困难，下面我们可以仅查看M为素数的情况:
这时,选择任意和n=kM互素的数字g,将x替换为xg(mod n)，我们可以得出C(M,kM,1)=C(M,kM,2)=...=C(M,kM,M-1)=a_k, C(M,kM,0)=b_k,
由于总数已知，我们有约束条件$C_{kM}^M=(M-1)a_k+b_k$

另外我们可以根据递推式得出
C(M,kM+1,h)=C(M,kM,h)+C(M-1,kM,h)=C(M,kM,h)+$\frac{C_{kM}^{M-1}}M$
由此C(M,kM+1,1)=C(M,kM+1,2)=...=C(M,kM+1,M-1),而且C(M,kM+1,1)-C(M,kM+1,0)=C(M,kM,1)-C(M,kM,0)

mathe

我们已经有公式
C(u,n,h)=C(u,n-1,h-u)+C(u-1,n-1,h-u)
如果再考虑C(u,n,h)的所有实例中，不包含数字n的有C(u,n-1,h)个，而包含n的有C(u-1,n-1,h-n)个，
我们还可以得出
C(u,n,h)=C(u,n-1,h)+C(u-1,n-1,h-n)
取u=M,两者比较得出C(M-1,n-1,h)=C(M-1,n-1,h-n),于是我们得出，如果n不是素数M的倍数，必然有C(M-1,n-1,h)全部相等，都等于$\frac{C_{n-1}^{M-1}}M$
于是$n\ne 0(\mod M)$时，$C(M,n,h)=C(M,n-1,h)+\frac{C_{n-1}^{M-1}}M$
C(M,kM+1,h)=C(M,kM,h)+$\frac{C_{kM}^{M-1}}M$
C(M,kM+2,h)=C(M,kM+1,h)+$\frac{C_{kM+1}^{M-1}}M$
C(M,kM+3,h)=C(M,kM+2,h)+$\frac{C_{kM+2}^{M-1}}M$
C(M,kM+4,h)=C(M,kM+3,h)+$\frac{C_{kM+3}^{M-1}}M$
...
C(M,(k+1)M-1,h)=C(M,(k+1)M-2,h)+$\frac{C_{(k+1)M-2}^{M-1}}M$
上面表达式可以得知所有C(M,kM+x,h)和C(M,kM,h)一样，只有h=0时不同

mathe

1楼的公式是错误的，把我代码简单修改M改为7就可以发现n>=28时是不对的:

1. #include <stdio.h>
   
2. 
   
3. #define M 7
   
4. #define N 300
   
5. long C[2][N][M];
   
6. 
   
7. long cnM(long n)
   
8. {
   
9.     long p=1;
   
10.     int i;
    
11.     for(i=1;i<=M;i++){
    
12.         p*=(n+1-i);
    
13.         p/=i;
    
14.     }
    
15.     return p;
    
16. }
    
17. 
    
18. int main()
    
19. {
    
20.     long i,h,n;
    
21.     long u=1,s=1;
    
22.     for(h=0;h<M;h++){
    
23.         for(n=1;n<N;n++){
    
24.             C[u&1][n][h]=n/M;
    
25.             if(h>=1&&h<=n%M)C[u&1][n][h]++;
    
26.         }
    
27.     }
    
28.     for(u=2;u<=M;u++){
    
29.         s+=u;s%=M;
    
30.         for(n=1;n<u;n++)for(h=0;h<M;h++)C[u&1][n][h]=0;
    
31.         for(n=u;n<N;n++){
    
32.             for(h=0;h<M;h++){
    
33.                 long v=h-u;if(v<0)v+=M;
    
34.                 C[u&1][n][h]=C[u&1][n-1][v]+C[(u-1)&1][n-1][v];
    
35.             }
    
36.         }
    
37.     }
    
38.     printf("n\tF(n,m)\tceil((C(n,m)+4floor(n/m))/m)\n");
    
39.     for(n=1;n<N;n++){
    
40.         long r=cnM(n);
    
41.         r+=4*(n/M);
    
42.         r+=M-1;
    
43.         r/=M;
    
44.         printf("%ld(%c)\t%ld\t%ld\n",n,C[M&1][n][0]==r?'T':'F', C[M&1][n][0], r);
    
45.     }
    
46.     return 0;
    
47. }

复制代码

输出:
n       F(n,m)  ceil((C(n,m)+4floor(n/m))/m)
1(T)    0       0
2(T)    0       0
3(T)    0       0
4(T)    0       0
5(T)    0       0
6(T)    0       0
7(T)    1       1
8(T)    2       2
9(T)    6       6
10(T)   18      18
11(T)   48      48
12(T)   114     114
13(T)   246     246
14(T)   492     492
15(T)   921     921
16(T)   1636    1636
17(T)   2780    2780
18(T)   4548    4548
19(T)   7200    7200
20(T)   11076   11076
21(T)   16614   16614
22(T)   24366   24366
23(T)   35025   35025
24(T)   49446   49446
25(T)   68674   68674
26(T)   93974   93974
27(T)   126864  126864
28(F)   169152  169151
29(F)   222972  222971
30(F)   290832  290831
31(F)   375657  375656
32(F)   480840  480839
33(F)   610296  610295
34(F)   768520  768519
35(F)   960650  960649
36(F)   1192530 1192529
37(F)   1470786 1470785
38(F)   1802898 1802897
39(F)   2197281 2197280
40(F)   2663370 2663369
41(F)   3211710 3211709
42(F)   3854052 3854051
43(F)   4603450 4603449
44(F)   5474372 5474371
....
296(F)  5253804881276   5253804881264
297(F)  5380620861168   5380620861156
298(F)  5510051603532   5510051603520
299(F)  5642141881698   5642141881686

mathe

由于对于M是素数时，C(M, n, h)在h不是0的都相等，所以我们可以先将总数$C_n^M$M份平均分，余数留给C(M,n,0),得到一种潜在的参考解。
而这时如果每个C(M,n,h) (h!=0)加1，那么C(M,n,0)需要再添加M-1, 由此我们得到
$C(M,n,0)-\lfloor\frac{C_n^M}M\rfloor-(C_n^M%M)$是M-1的倍数，于是可以使用程序验证上面性质并且计算$r(M,n)=\frac{C(M,n,0)-\lfloor\frac{C_n^M}M\rfloor-(C_n^M%M)}{M-1}$
比如M=7时，得出
r(7,0..48)=0
r(7,49..97)=1
r(7,98:146)=2
r(7,147:195)=3
r(7,196:244)=4
r(7,245:293)=5
r(7,294:342)=6
r(7,343:391)=7
r(7,392:440)=8
...
r(7,931:979)=19
由此合理的猜测是$r(M,n)=\lfloor\frac{n}{M^2}\rfloor$
所以可以合理猜测M是素数时，$F(n,M)=\lfloor\frac{C_n^M}M\rfloor+C_n^M %M+(M-1)\lfloor\frac{n}{M^2}\rfloor$
根据Lucas定理，可以有$C_n^M%M=\lfloor\frac{n}{M}\rfloor %M$
所以$F(n,M)=\lfloor\frac{C_n^M}M\rfloor +\lfloor\frac{n}{M}\rfloor %M+ M\lfloor\frac{n}{M^2}\rfloor -\lfloor\frac{n}{M^2}\rfloor=\lfloor\frac{C_n^M}M\rfloor+\lfloor\frac{n}{M}\rfloor -\lfloor\frac{n}{M^2}\rfloor$和三楼的猜测匹配

王守恩

chyanog 发表于 2021-8-14 14:21
可以自己改代码运行

79 s

在 1～n 中任意取 12 个不同整数，使得这 12 个数之和能被 12 整除，有几种不同取法？

Table[Count[Total/@Subsets[Range@n, {12}]/12, _Integer], {n, 12, 31}]

{0, 1, 8, 39, 154, 518, 1556, 4208, 10516, 24516, 53930, 112716, 225432, 433444,
804960, 1448816, 2535412, 4324927, 7208216, 11760491}}

这里是n=31(32怎么鼓捣，就是出不来)，如果要搞个通项，需要n=12——83，各位网友：能来几项？

mathe

22#的递推式表明，如果我们能够证明上面表达式在F(kM,M)（M是素数）的情况成立，那么就可以证明一切的F(n,M)。
而对于F(kM,M), 由于需要处理的数字为1~kM,本质上就是模M为0~M-1的数均k个。
如果我们发现$0\times a_0+1\times a_1+ 2\times a_2+...+(M-1)\times a_{M-1} -= 0 (mod M)$而且$a_0+a_1+...+a_{M-1} = M$
那么这种模式可以对应F(kM,M)中的$C_k^{a_0}C_k^{a_1}...C_k^{a_{M-1}}$个解，这个表达式是k的一个M次多项式。所以所有合法的模式累加以后得到F(kM,M)的结果也是k的一个M次多项式，即F(kM,M)是k的一个次数不超过M次的多项式。
根据Lucas定理有$C_{kM}^M -= k (mod M)$, 我们知道F(kM,M)应该会比较接近$\frac{C_{kM}^M-k}M$, 这个表达式也是k的M次多项式，所以
$G_M(k)=F(kM,M)-\frac{C_{kM}^M-k}M$是k的一个次数不超过M的多项式。而根据上面的数据结果，我们需要证明$G_M(k)=k$。
如果我们能够对k=0,1,2...,M都能够验算通过，那么就可以证明$G_M(k)=k$,比如上面对于M=7我们已经验算通过了，也就是M=7情况的结果已经可以严格证明了。
另外我们容易证明C(M,kM,1)也是kM的倍数。如果相信它和C(M,kM,0)不会有特别大的差值，那么显然这只能是唯一的选择了。

王守恩

chyanog 发表于 2021-8-14 14:21
可以自己改代码运行

79 s

在 1～n 中任意取 12 个不同整数，使得这 12 个数之和能被 12 整除，有几种不同取法？

Table[Count[Total/@Subsets[Range@n,{12}]/12,_Integer],{n,12,31}]

Table[Total[1-Unitize[Mod[Total/@Subsets[Range@n,{12}],12]]],{n,12,31}]

Table[\(\sum_{k=1}^n\)Total[1-Unitize[Mod[Total/@Subsets[Range@k,{11}],12]]],{n,12,31}]

{0, 1, 8, 39, 154, 518, 1556, 4208, 10516, 24516, 53930, 112716, 225432, 433444,
804960, 1448816, 2535412, 4324927, 7208216, 11760491, 18816764, 29568824, ...}}

这里是n=33(原来是n=31，32怎么鼓捣，就是出不来)，结合21楼,22楼的算法:增加了32,33
如果要搞个通项，需要n=12——83，各位网友：能来几项？

说明一下：我们已经有2,4,6,8,9,10的规律，可还是找不到12的规律。
找到2的规律需要3(2*1+1)
找到3的规律需要5(3*1+2)
找到4的规律需要11(4*2+3)
找到5的规律需要14(5*2+4)
找到6的规律需要23(6*3+5)
找到7的规律需要27(7*3+6)
找到8的规律需要39(8*4+7)
找到9的规律需要44(9*4+8)
找到10的规律需要59(10*5+9)
找到11的规律需要65(11*5+10)
找到12的规律需要83(12*6+11)
......
帖子是论坛共同的财富，各位网友：可有好的想法？

mathe

M=12

1. R[1]=0
   
2. R[2]=0
   
3. R[3]=0
   
4. R[4]=0
   
5. R[5]=0
   
6. R[6]=0
   
7. R[7]=0
   
8. R[8]=0
   
9. R[9]=0
   
10. R[10]=0
    
11. R[11]=0
    
12. R[12]=0
    
13. R[13]=1
    
14. R[14]=8
    
15. R[15]=39
    
16. R[16]=154
    
17. R[17]=518
    
18. R[18]=1556
    
19. R[19]=4208
    
20. R[20]=10516
    
21. R[21]=24516
    
22. R[22]=53930
    
23. R[23]=112716
    
24. R[24]=225432
    
25. R[25]=433444
    
26. R[26]=804960
    
27. R[27]=1448816
    
28. R[28]=2535412
    
29. R[29]=4324927
    
30. R[30]=7208216
    
31. R[31]=11760491
    
32. R[32]=18816764
    
33. R[33]=29568824
    
34. R[34]=45697248
    
35. R[35]=69538728
    
36. R[36]=104308092
    
37. R[37]=154375200
    
38. R[38]=225625260
    
39. R[39]=325902154
    
40. R[40]=465574454
    
41. R[41]=658224574
    
42. R[42]=921514412
    
43. R[43]=1278227860
    
44. R[44]=1757563244
    
45. R[45]=2396674899
    
46. R[46]=3242560086
    
47. R[47]=4354292019
    
48. R[48]=5805722692
    
49. R[49]=7688656056
    
50. R[50]=10116652620
    
51. R[51]=13229464280
    
52. R[52]=17198303444
    
53. R[53]=22231947514
    
54. R[54]=28583932532
    
55. R[55]=36560836922
    
56. R[56]=46531974124
    
57. R[57]=58940492200
    
58. R[58]=74316272620
    
59. R[59]=93290629840
    
60. R[60]=116613287300
    
61. R[61]=145171631075
    
62. R[62]=180012822356
    
63. R[63]=222368766137
    
64. R[64]=273684635014
    
65. R[65]=335650950166
    
66. R[66]=410240050224
    
67. R[67]=499746949888
    
68. R[68]=606835581744
    
69. R[69]=734590417486
    
70. R[70]=886574641510
    
71. R[71]=1066894879790
    
72. R[72]=1280273855748
    
73. R[73]=1532130975444
    
74. R[74]=1828672454244
    
75. R[75]=2176990980080
    
76. R[76]=2585176788448
    
77. R[77]=3062440152713
    
78. R[78]=3619247453236
    
79. R[79]=4267470828581
    
80. R[80]=5020553915536
    
81. R[81]=5893693671336
    
82. R[82]=6904041157380
    
83. R[83]=8070921289200
    
84. R[84]=9416074837400
    
85. R[85]=10963922683490
    
86. R[86]=12741856091104
    
87. R[87]=14780552984428
    
88. R[88]=17114324507658
    
89. R[89]=19781491871142
    
90. R[90]=22824798312896
    
91. R[91]=26291856180716
    
92. R[92]=30235634607136
    
93. R[93]=34714987766669
    
94. R[94]=39795229878138
    
95. R[95]=45548756959349
    
96. R[96]=52055722239256
    
97. R[97]=59404765233744
    
98. R[98]=67693802242312
    
99. R[99]=77030878252976
    
100. R[100]=87535088922904
     
101. R[101]=99337572643204
     
102. R[102]=112582582329016
     
103. R[103]=127428636942756
     
104. R[104]=144049763499496
     
105. R[105]=162636829538640
     
106. R[106]=183398977989320
     
107. R[107]=206565164440000
     
108. R[108]=232385809995000
     
109. R[109]=261134569726965
     
110. R[110]=293110231325040
     
111. R[111]=328638743920155
     
112. R[112]=368075393189250
     
113. R[113]=411807122750406
     
114. R[114]=460255019544636
     
115. R[115]=513876963215568
     
116. R[116]=573170458969788
     
117. R[117]=638675653895208
     
118. R[118]=710978558108274
     
119. R[119]=790714470744576
     
120. R[120]=878571634160640
     
121. R[121]=975295116359620
     
122. R[122]=1081690947233624
     
123. R[123]=1198630508596560
     
124. R[124]=1327055205944380
     
125. R[125]=1467981421959107
     
126. R[126]=1622505782165408
     
127. R[127]=1791810732755183
     
128. R[128]=1977170463727924
     
129. R[129]=2179957177315704
     
130. R[130]=2401647737718680
     
131. R[131]=2643830702170680
     
132. R[132]=2908213772387748
     
133. R[133]=3196631666416948
     
134. R[134]=3511054453275492
     
135. R[135]=3853596350344766
     
136. R[136]=4226525029407982
     
137. R[137]=4632271431353230
     
138. R[138]=5073440139101252
     
139. R[139]=5552820308778596
     
140. R[140]=6073397212724036
     
141. R[141]=6638364394286711
     
142. R[142]=7251136492218222
     
143. R[143]=7915362734684295
     
144. R[144]=8634941165110140
     
145. R[145]=9414033599882376
     
146. R[146]=10257081384943668
     
147. R[147]=11168821951233352
     
148. R[148]=12154306241044940
     
149. R[149]=13218917005328734
     
150. R[150]=14368388049270476
     
151. R[151]=15608824426172926
     
152. R[152]=16946723662698740
     
153. R[153]=18388998015420600
     
154. R[154]=19942997847706260
     
155. R[155]=21616536126971280
     
156. R[156]=23417914137552220
     
157. R[157]=25355948409229815
     
158. R[158]=27439998963409500
     
159. R[159]=29679998876899085
     
160. R[160]=32086485272319374
     
161. R[161]=34670631735183574
     
162. R[162]=37444282273998392
     
163. R[163]=40419986823421088
     
164. R[164]=43611038414739640
     
165. R[165]=47031512013607186
     
166. R[166]=50696305157520334
     
167. R[167]=54621180393082498
     
168. R[168]=58822809654088844
     
169. R[169]=63318820580470196
     
170. R[170]=68127844928349500
     
171. R[171]=73269569071134800
     
172. R[172]=78764786751464968
     
173. R[173]=84635454084052909
     
174. R[174]=90904746979168092
     
175. R[175]=97597120986801289
     
176. R[176]=104738373741927912
     
177. R[177]=112355710010783848
     
178. R[178]=120477809529630364
     
179. R[179]=129134897636058944
     
180. R[180]=138358818895777440
     
181. R[181]=148183113724923990
     
182. R[182]=158643098223148344
     
183. R[183]=169775947217366144
     
184. R[184]=181620780744153058
     
185. R[185]=194218753970833718
     
186. R[186]=207613150796408632
     
187. R[187]=221849481132371900
     
188. R[188]=236975582118663640
     
189. R[189]=253041723274651089
     
190. R[190]=270100715854958130
     
191. R[191]=288208026410205225
     
192. R[192]=307421894837552240
     
193. R[193]=327803456921101088
     
194. R[194]=349416871663144912
     
195. R[195]=372329453406148192
     
196. R[196]=396611809063063536
     
197. R[197]=422337980456051784
     
198. R[198]=449585592098377904
     
199. R[199]=478436004419546888
     
200. R[200]=508974472786744336
     
201. R[201]=541290312322452896
     
202. R[202]=575477068890178896
     
203. R[203]=611632696248363776
     
204. R[204]=649859739763886512
     
205. R[205]=690265526685225897
     
206. R[206]=732962363387396632
     
207. R[207]=778067739588519503
     
208. R[208]=825704539971481258
     
209. R[209]=876001263210764038
     
210. R[210]=929092248859901476
     
211. R[211]=985117912099638576
     
212. R[212]=1044224986825607716
     
213. R[213]=1106566777075366092
     
214. R[214]=1172303417297655674
     
215. R[215]=1241602141463974516
     
216. R[216]=1314637561550090664
     
217. R[217]=1391591955387581028
     
218. R[218]=1472655564439275024
     
219. R[219]=1558026901498436016
     
220. R[220]=1647913068892566084
     
221. R[221]=1742530087191928839
     
222. R[222]=1842103235031467880
     
223. R[223]=1946867400046212531
     
224. R[224]=2057067441558251436
     
225. R[225]=2172958565015090232
     
226. R[226]=2294806708847701008
     
227. R[227]=2422888943748368328
     
228. R[228]=2557493885067722124
     
229. R[229]=2698922118331054984
     
230. R[230]=2847486638606147420
     
231. R[231]=3003513303722403570
     
232. R[232]=3167341302107249638
     
233. R[233]=3339323635239906398
     
234. R[234]=3519827615523144860
     
235. R[235]=3709235379573132980
     
236. R[236]=3907944417764538076
     
237. R[237]=4116368120030668635
     
238. R[238]=4334936338793345990
     
239. R[239]=4564095969022628379
     
240. R[240]=4804311546339608820
     
241. R[241]=5056065863162401240
     
242. R[242]=5319860603849121756
     
243. R[243]=5596216998837633464
     
244. R[244]=5885676498777496708
     
245. R[245]=6188801468654254594
     
246. R[246]=6506175902944216676
     
247. R[247]=6838406161799866754
     
248. R[248]=7186121729348997692
     
249. R[249]=7549975994107320776
     
250. R[250]=7930647052633725180
     
251. R[251]=8328838536428329680
     
252. R[252]=8745280463249746164
     
253. R[253]=9180730112851688139
     
254. R[254]=9635972928364979364
     
255. R[255]=10111823443324693153
     
256. R[256]=10609126235619333590
     
257. R[257]=11128756908362208790
     
258. R[258]=11671623099014024192
     
259. R[259]=12238665516756841792
     
260. R[260]=12830859009503123456
     
261. R[261]=13449213660539565846
     
262. R[262]=14094775916245447542
     
263. R[263]=14768629744885652118
     
264. R[264]=15471897827975445076
     
265. R[265]=16205742784217158548
     
266. R[266]=16971368427565982676
     
267. R[267]=17770021059424552496
     
268. R[268]=18602990796585059312
     
269. R[269]=19471612934919059089
     
270. R[270]=20377269350496690116
     
271. R[271]=21321389938135467821
     
272. R[272]=22305454089126315904
     
273. R[273]=23330992208136497320
     
274. R[274]=24399587271104561140
     
275. R[275]=25512876424127492752
     
276. R[276]=26672552625224196968
     
277. R[277]=27880366328975490698
     
278. R[278]=29138127215996920784
     
279. R[279]=30447705967244050004
     
280. R[280]=31811036085180328954
     
281. R[281]=33230115761807750854
     
282. R[282]=34707009795665873520
     
283. R[283]=36243851557799400460
     
284. R[284]=37842845008878763344
     
285. R[285]=39506266767473321173
     
286. R[286]=41236468231742202922
     
287. R[287]=43035877754543007005
     
288. R[288]=44907002874305746440
     
289. R[289]=46852432601672241264
     
290. R[290]=48874839764334328920
     
291. R[291]=50976983410070485520
     
292. R[292]=53161711270502053000
     
293. R[293]=55431962285569295948
     
294. R[294]=57790769191338202600
     
295. R[295]=60241261171138248236
     
296. R[296]=62786666572735613560
     
297. R[297]=65430315691541420784
     
298. R[298]=68175643622655020952
     
299. R[299]=71026193181742574016
     
300. R[300]=73985617897648514600
     
301. R[301]=77057685076740132125
     
302. R[302]=80246278941984524800
     
303. R[303]=83555403846757465795
     
304. R[304]=86989187566487196690
     
305. R[305]=90551884668133401030
     
306. R[306]=94247879960710275020
     
307. R[307]=98081692026853942160
     
308. R[308]=102057976838753397580
     
309. R[309]=106181531458444487600
     
310. R[310]=110457297825898598850
     
311. R[311]=114890366634906329000
     
312. R[312]=119485981300302582160
     
313. R[313]=124249542016533347076
     
314. R[314]=129186609911230006408
     
315. R[315]=134302911293790656144
     
316. R[316]=139604342002756045324
     
317. R[317]=145096971851980420363
     
318. R[318]=150787049179509064816
     
319. R[319]=156681005499162812343
     
320. R[320]=162785460258870422116
     
321. R[321]=169107225705748260216
     
322. R[322]=175653311862099773000
     
323. R[323]=182430931612335057496
     
324. R[324]=189447505905117175092
     
325. R[325]=196710669070735498524
     
326. R[326]=204228274258152108180
     
327. R[327]=212008398991720652646
     
328. R[328]=220059350852165705502
     
329. R[329]=228389673281822936622
     
330. R[330]=237008151518872859316
     
331. R[331]=245923818660568464516
     
332. R[332]=255145961860339745844
     
333. R[333]=264684128658774492159
     
334. R[334]=274548133453511393118
     
335. R[335]=284748064108045798383
     
336. R[336]=295294288704640087212
     
337. R[337]=306197462441338972840
     
338. R[338]=317468534678443437380
     
339. R[339]=329118756134442642984
     
340. R[340]=341159686236922212604
     
341. R[341]=353603200628449235174
     
342. R[342]=366461498833120117052
     
343. R[343]=379747112083771626950
     
344. R[344]=393472911315715139524
     
345. R[345]=407652115326993382104
     
346. R[346]=422298299111196696356
     
347. R[347]=437425402362839193744
     
348. R[348]=453047738161512022092
     
349. R[349]=469180001834814104671
     
350. R[350]=485837280006464267820
     
351. R[351]=503035059829594028405
     
352. R[352]=520789238411814950494
     
353. R[353]=539116132432060965334
     
354. R[354]=558032487955992929672
     
355. R[355]=577555490449965808352
     
356. R[356]=597702775000545966344
     
357. R[357]=618492436739577797210
     
358. R[358]=639943041481990854750
     
359. R[359]=662073636576347907690
     
360. R[360]=684903761975532318300
     
361. R[361]=708453461527575146100
     
362. R[362]=732743294494234819116
     
363. R[363]=757794347297328564112
     
364. R[364]=783628245500646535064
     
365. R[365]=810267166027449076021
     
366. R[366]=837733849621599892844
     
367. R[367]=866051613552335561233
     
368. R[368]=895244364570953564504
     
369. R[369]=925336612119418005096
     
370. R[370]=956353481799398446860
     
371. R[371]=988320729101742351840
     
372. R[372]=1021264753405133763568
     
373. R[373]=1055212612243938680574
     
374. R[374]=1090192035854234939304
     
375. R[375]=1126231441998025712360
     
376. R[376]=1163359951074883649618
     
377. R[377]=1201607401521026143318
     
378. R[378]=1241004365505322083176
     
379. R[379]=1281582164922230573276
     
380. R[380]=1323372887691433689736
     
381. R[381]=1366409404364162334361
     
382. R[382]=1410725385046243219810
     
383. R[383]=1456355316637867496785
     
384. R[384]=1503334520400379351520
     
385. R[385]=1551699169850085062720
     
386. R[386]=1601486308989659928224
     
387. R[387]=1652733870877152075968
     
388. R[388]=1705480696543444104928
     
389. R[389]=1759766554258173085072
     
390. R[390]=1815632159155257945696
     
391. R[391]=1873119193218034771216
     
392. R[392]=1932270325635446335776
     
393. R[393]=1993129233529284837184
     
394. R[394]=2055740623064236132768
     
395. R[395]=2120150250940726037504
     
396. R[396]=2186404946282623726176
     
397. R[397]=2254552632919802777169
     
398. R[398]=2324642352077931299112
     
399. R[399]=2396724285475490057591
     
400. R[400]=2470849778840711335354
     
401. R[401]=2547071365848439106054
     
402. R[402]=2625442792489929540916
     
403. R[403]=2706019041875592417776
     
404. R[404]=2788856359484028854836
     
405. R[405]=2874012278857364228820
     
406. R[406]=2961545647756573225290
     
407. R[407]=3051516654776797634460
     
408. R[408]=3143986856436700593080
     
409. R[409]=3239019204741857861540
     
410. R[410]=3336678075236587176640
     
411. R[411]=3437029295544214493680
     
412. R[412]=3540140174410540858260
     
413. R[413]=3646079531250510542031
     
414. R[414]=3754917726213212350136
     
415. R[415]=3866726690765214723323
     
416. R[416]=3981579958807745782108
     
417. R[417]=4099552698327717065528
     
418. R[418]=4220721743598486955584
     
419. R[419]=4345165627930364456936
     
420. R[420]=4472964616987139882140
     
421. R[421]=4604200742668643086320
     
422. R[422]=4738957837576017932044
     
423. R[423]=4877321570059711688090
     
424. R[424]=5019379479867276029590
     
425. R[425]=5165221014390980331262
     
426. R[426]=5314937565532747878028
     
427. R[427]=5468622507186415672788
     
428. R[428]=5626371233355254508364
     
429. R[429]=5788281196904747942499
     
430. R[430]=5954451948968999000630
     
431. R[431]=6124985179010765335555
     
432. R[432]=6299984755553930059428
     
433. R[433]=6479556767588408950008
     
434. R[434]=6663809566666752252012
     
435. R[435]=6852853809692439660696
     
436. R[436]=7046802502419584096052
     
437. R[437]=7245771043664045020170
     
438. R[438]=7449877270246130796372
     
439. R[439]=7659241502664890830026
     
440. R[440]=7873986591524654039436
     
441. R[441]=8094237964713812175336
     
442. R[442]=8320123675356988243212
     
443. R[443]=8551774450540590820560
     
444. R[444]=8789323740833385010020
     
445. R[445]=9032907770602080791731
     
446. R[446]=9282665589144073721588
     
447. R[447]=9538739122637336439177
     
448. R[448]=9801273226930107076390
     
449. R[449]=10070415741170375383574
     
450. R[450]=10346317542298330874576
     
451. R[451]=10629132600401773794176
     
452. R[452]=10919018034958185714640
     
453. R[453]=11216134171963458152670
     
454. R[454]=11520644601971515746950
     
455. R[455]=11832716239044834854910
     
456. R[456]=12152519380640641202340
     
457. R[457]=12480227768432787414100
     
458. R[458]=12816018650094656038980
     
459. R[459]=13160072842043086402160
     
460. R[460]=13512574793169240404224
     
461. R[461]=13873712649556408151449
     
462. R[462]=14243678320211245703252
     
463. R[463]=14622667543808445807413
     
464. R[464]=15010879956475926569840
     
465. R[465]=15408519160620536315816
     
466. R[466]=15815792794821960082404
     
467. R[467]=16232912604794828670768
     
468. R[468]=16660094515447324162104
     
469. R[469]=17097558704036282793906
     
470. R[470]=17545529674447713681600
     
471. R[471]=18004236332602731581500
     
472. R[472]=18473912063018454908138
     
473. R[473]=18954794806523869962214
     
474. R[474]=19447127139160853598752
     
475. R[475]=19951156352270355276844
     
476. R[476]=20467134533794588495232
     
477. R[477]=20995318650795229729053
     
478. R[478]=21535970633219141115354
     
479. R[479]=22089357458911617889989
     
480. R[480]=22655751239909351682040
     
481. R[481]=23235429310013110634640
     
482. R[482]=23828674313673019731624
     
483. R[483]=24435774296186439381104
     
484. R[484]=25057022795242026708728
     
485. R[485]=25692718933809980592148
     
486. R[486]=26343167514412764912152
     
487. R[487]=27008679114776311036340
     
488. R[488]=27689570184896722122760
     
489. R[489]=28386163145522477209744
     
490. R[490]=29098786488087894930280
     
491. R[491]=29827774876097857931200
     
492. R[492]=30573469248000304379480
     
493. R[493]=31336216921546487600453
     
494. R[494]=32116371699676275554192
     
495. R[495]=32914293977928488048747
     
496. R[496]=33730350853414318207906
     
497. R[497]=34564916235353839304134
     
498. R[498]=35418370957214427930204
     
499. R[499]=36291102890451104603728
     
500. R[500]=37183507059888426723036

复制代码

对应的Pari/gp代码:

1. getC(N,m)={
   
2.    local(C,D,v,R);
   
3.    C=matrix(N,m);
   
4.    D=matrix(N,m);
   
5.    R=vector(N);
   
6.    for(h=1,m,
   
7.      for(n=1,N,
   
8.        C[n,h]=floor(n/m);
   
9.        if(h<=n%m, C[n,h]=C[n,h]+1)
   
10.      )
    
11.    );
    
12.    for(u=2, m,
    
13.       for(n=1, u-1,
    
14.          for(h=1,m,D[n,h]=0)
    
15.       );
    
16.       for(n=u,N,
    
17.          for(h=1,m,
    
18.              v=h-u;if(v<=0,v+=m);
    
19.              D[n,h]=D[n-1,v]+C[n-1,v]
    
20.          )
    
21.       );
    
22.       C=D
    
23.    );
    
24.    for(n=1,N,
    
25.       R[n]=C[n, m]
    
26.    );
    
27.    R
    
28. }

复制代码

另外对于M是素数而且不超过47，前2500项我都已经验证过和公式匹配，所以证明了对于这些素数公式都是严格成立的。

mathe

另外F(n,m)定义为1~n中m个和为m倍数的数的组合数目。
如果我们扩展定义$F_h(n,m)$定义为1~n中m个和除以m余数为h的数的组合数目。而原定义的F(n,m)=$F_0(n,m)=F_m(n,m)$
可以证明$F_h(n,m)=F_{(h,m)}(n,m)$
于是在m为素数时，$U(m,k)=F_m(km,m)-F_{m-1}(km,m)=k$
但是m不是素数时，$U(m,k)=F_m(km,m)-F_{m-1}(km,m)$规律性没有那么强
比如
U(3,.)={1,2,3,4,5,6,...}
U(4,.)={0, 2, 6, 12, 20, 30, 42, 56, 72, 90,...}
   1*0,2*1,3*2,4*3,5*4,6*5,7*6,8*7,
U(6,.)={0, -4, -21, -60, -130, -240, -399, -616, -900, -1260, -1705, -2244, -2886, -3640, -4515, -5520,...}
U(8,.)={0, 18, 126, 460, 1220, 2670, 5138, 9016, 14760, 22890, 33990, 48708, 67756,...}
U(9,.)={1, 8, 30, 76, 155, 276, 448, 680, 981, 1360, 1826, 2388, 3055, 3836, 4740, 5776, 6953,...}
     1*1, 2*4,3*10,4*19,5*31,6*46,7*64,8*85,9*109,10*136,11*166,
U(10,.)={0, -48, -594, -3088, -10605, -28470, -64883, -131544, -244278, -423660, -695640, -1092168, -1651819, -2420418,...}
U(12,.)={0, 168, 3204, 22852, 100100, 327156, 879200, 2053912, 4318776, 8366160, 15176172, 26087292, 42874780,...}
U(14,.)={0, -488, -16605, -169136, -960625, -3854016, -12271469, -33131000, -79038594, -171253440, -343543937, -647052120,...}
U(15,.)={1, 58, 630, 3176, 10780, 28776, 65373, 132280, 245331, 425110, 697576, 1094688, 1655030,...}
U(16,.)={0, 1618, 91998, 1315020, 9613700, 47169966, 177564338, 553275192, 1496134440, 3623453610, 8034631462, 16575151428,...}

王守恩

mathe 发表于 2021-8-16 13:16
M=12

在 1～n 中任意取12 个不同整数，使得这 12 个数之和能被 12 整除，有几种不同取法？

\(a(n)=\frac{27\lfloor n/12\rfloor^6}{5}-(\frac{2916\lfloor n/12\rfloor^5-1990\lfloor n/12\rfloor^4+1365\lfloor n/12\rfloor^3-791\lfloor n/12\rfloor^2+294\lfloor n/12\rfloor\ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+9)_{12}+1}{12}\rfloor)\)
\(-(\frac{2916\lfloor n/12\rfloor^5-1990\lfloor n/12\rfloor^4+725\lfloor n/12\rfloor^3-311\lfloor n/12\rfloor^2+214\lfloor n/12\rfloor\ \ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+8)_{12}+1\ \ }{12}\rfloor)\ +\ \frac{n!/12}{12!(n-12)!}\)
\(-(\frac{4860\lfloor n/12\rfloor^5-5230\lfloor n/12\rfloor^4+3255\lfloor n/12\rfloor^3-1241\lfloor n/12\rfloor^2+330\lfloor n/12\rfloor\ \ \ \ \ }{360})(\lfloor\frac{(n+11)_{12}+1}{12}\rfloor+\lfloor\frac{(n+10)_{12}+1}{12}\rfloor)\)
\(-(\frac{972\lfloor n/12\rfloor^5-370\lfloor n/12\rfloor^4+455\lfloor n/12\rfloor^3-86\lfloor n/12\rfloor^2+133\lfloor n/12\rfloor\ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+7)_{12}+1}{12}\rfloor+\lfloor\frac{(n+6)_{12}+1}{12}\rfloor)\)
\(+(\frac{972\lfloor n/12\rfloor^5+370\lfloor n/12\rfloor^4-85\lfloor n/12\rfloor^3+86\lfloor n/12\rfloor^2-47\lfloor n/12\rfloor\ \ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+5)_{12}+1\ }{12}\rfloor+\lfloor\frac{(n+4)_{12}+1\ }{12}\rfloor)\)
\(+(\frac{4860\lfloor n/12\rfloor^5+5230\lfloor n/12\rfloor^4+2715\lfloor n/12\rfloor^3+701\lfloor n/12\rfloor^2-30\lfloor n/12\rfloor\ \ \ \ \ }{360})(\lfloor\frac{(n+1)_{12}+1}{12}\rfloor+\lfloor\frac{(n)_{12}+1}{12}\rfloor)\)
\(+(\frac{2916\lfloor n/12\rfloor^5+1990\lfloor n/12\rfloor^4+185\lfloor n/12\rfloor^3-229\lfloor n/12\rfloor^2-146\lfloor n/12\rfloor\ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+3)_{12}+1}{12}\rfloor)\)
\(+(\frac{2916\lfloor n/12\rfloor^5+1990\lfloor n/12\rfloor^4+825\lfloor n/12\rfloor^3+251\lfloor n/12\rfloor^2-66\lfloor n/12\rfloor\ \ \ \ \ \ \ }{360})(\lfloor\frac{(n+2)_{12}+1}{12}\rfloor)\)

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 39, 154, 518, 1556,  4208,  10516, 24516,  53930, 112716, 225432, 433444,
804960, 1448816, 2535412, 4324927,7208216, 11760491,18816764, 29568824, 45697248,69538728, 104308092,
154375200, 225625260, 325902154, 465574454, 658224574, 921514412, 1278227860, 1757563244, 2396674899,
3242560086, 4354292019, 5805722692,7688656056, 10116652620,13229464280,17198303444, 22231947514,...}
注：《整数序列在线百科全书(OEIS)》没有收录。