整数の可能な分割数 p(n) は漸化式で求められます。p(n)はｎマスのヤング図（フェラーズ盤）の可能な数に対応しています。
アンドリュース＆エリクソンの『整数の分割』という本に漸化式が導出されています（第五章四節）。結果だけ書くと、
これより (p(0)=1として）
- p(0)=1
- p(1)=p(0)=1
- p(2)=p(1)+p(0)=2
- p(3)=p(2)+p(1)=3
- p(4)=p(3)+p(2)=5
- p(5)=p(4)+p(3)-p(0)=7
- p(6)=p(5)+p(4)-p(1)=11
- p(7)=p(6)+p(5)-p(2)-p(0)=15
等々と、求まります。
また漸近的な近似式として、
というものがあります。
また、n が大きい極限では
となることが知られております。
『整数の分割』（六章四節）には、いくつかの n に対する値が与えられています。
| n | p(n)^(1/n) |
| 5 | 1.475 |
| 10 | 1.453 |
| 100 | 1.210 |
| 250 | 1.141 |
（『整数の分割』より）
ソース・プログラム
Fortranでは数論的な大きな整数を扱うのは苦手なのですが、ここでは64bit整数を使って少し頑張ることにしました。でも400程度の分割数が限界となります。結果の確認のため上述の漸近式等の値も計算しています。
program partition2 implicit none integer, parameter :: ki = 8, kd = 8 integer, parameter :: np = 400 integer(ki) :: i, j, k, m, mp(0:np) mp = 0 mp(0) = 1 do i = 1, np m = 0 do j = 1, i k = i - j * ( 3 * j - 1) / 2 if ( k < 0 ) exit m = m - (-1)**j * mp(k) end do do j = 1, i k = i - j * ( 3 * j + 1) / 2 if ( k < 0 ) exit m = m - (-1)**j * mp(k) end do mp(i) = m print '(3i20, g20.10)', i, m, p(i), m / real(p(i)) end do print *, 'p( 5)^1/5 ', mp( 5)**(1.0/ 5.0) print *, 'p( 10)^1/10 ', mp(10)**(1.0/ 10.0) print *, 'p(100)^1/100', mp(100)**(1.0/100.0) print *, 'p(250)^1/250', mp(250)**(1.0/250.0) stop contains integer(ki) pure elemental function p(n) integer(ki), intent(in) :: n real(kd), parameter :: pi = 4.0_kd * atan(1.0_kd) real(kd) :: pp pp = 1.0_kd / (4 * n * sqrt(3.0_kd)) * exp(pi * sqrt( 2 * n / 3.0_kd )) p = nint(pp, ki) return end function p end program partition2
実行結果
n, p(n), 漸近式, p(n)/漸近式
1 1 2 0.5000000000
2 2 3 0.6666666865
3 3 4 0.7500000000
4 5 6 0.8333333135
5 7 9 0.7777777910
6 11 13 0.8461538553
7 15 18 0.8333333135
8 22 26 0.8461538553
9 30 35 0.8571428657
10 42 48 0.8750000000
11 56 65 0.8615384698
12 77 87 0.8850574493
13 101 115 0.8782608509
14 135 152 0.8881579041
15 176 199 0.8844221234
16 231 258 0.8953488469
17 297 333 0.8918918967
18 385 427 0.9016393423
19 490 545 0.8990825415
20 627 692 0.9060693383
21 792 875 0.9051428437
22 1002 1102 0.9092559218
23 1255 1381 0.9087617397
24 1575 1725 0.9130434990
25 1958 2145 0.9128205180
26 2436 2659 0.9161338806
27 3010 3285 0.9162861705
28 3718 4046 0.9189322591
29 4565 4967 0.9190658331
30 5604 6080 0.9217105508
31 6842 7423 0.9217297435
32 8349 9037 0.9238685369
33 10143 10974 0.9242755771
34 12310 13293 0.9260513186
35 14883 16065 0.9264239073
36 17977 19370 0.9280846715
37 21637 23304 0.9284672141
38 26015 27977 0.9298709631
39 31185 33519 0.9303678274
40 37338 40080 0.9315868020
41 44583 47833 0.9320552945
42 53174 56981 0.9331882596
43 63261 67757 0.9336452484
44 75175 80431 0.9346520901
45 89134 95316 0.9351420403
46 105558 112771 0.9360384941
47 124754 133211 0.9365142584
48 147273 157115 0.9373579621
49 173525 185031 0.9378158450
50 204226 217590 0.9385817647
51 239943 255518 0.9390453696
52 281589 299645 0.9397420287
53 329931 350921 0.9401859641
54 386155 410434 0.9408455491
55 451276 479431 0.9412741065
56 526823 559331 0.9418805838
57 614154 651756 0.9423066378
58 715220 758557 0.9428691864
59 831820 881840 0.9432777166
60 966467 1024004 0.9438117146
61 1121505 1187777 0.9442049861
62 1300156 1376260 0.9447023273
63 1505499 1592972 0.9450881481
64 1741630 1841910 0.9455565214
65 2012558 2127604 0.9459269643
66 2323520 2455186 0.9463722706
67 2679689 2830468 0.9467300177
68 3087735 3260025 0.9471507072
69 3554345 3751293 0.9474986196
70 4087968 4312670 0.9478972554
71 4697205 4953642 0.9482326508
72 5392783 5684909 0.9486137629
73 6185689 6518541 0.9489376545
74 7089500 7468136 0.9492998123
75 8118264 8549010 0.9496145248
76 9289091 9778401 0.9499601126
77 10619863 11175699 0.9502638578
78 12132164 12762701 0.9505953193
79 13848650 14563896 0.9508891106
80 15796476 16606782 0.9512063265
81 18004327 18922217 0.9514915347
82 20506255 21544812 0.9517955184
83 23338469 24513363 0.9520711899
84 26543660 27871338 0.9523640275
85 30167357 31667409 0.9526310563
86 34262962 35956048 0.9529122710
87 38887673 40798188 0.9531715512
88 44108109 46261953 0.9534424543
89 49995925 52423469 0.9536935687
90 56634173 59367760 0.9539549947
91 64112359 67189746 0.9541985989
92 72533807 75995337 0.9544507861
93 82010177 85902655 0.9546872973
94 92669720 97043377 0.9549309015
95 104651419 109564225 0.9551604986
96 118114304 123628608 0.9553962350
97 133230930 139418439 0.9556191564
98 150198136 157136139 0.9558472037
99 169229875 177006854 0.9560639858
100 190569292 199280893 0.9562848210
101 214481126 224236425 0.9564954042
102 241265379 252182444 0.9567096233
103 271248950 283462051 0.9569145441
104 304801365 318456052 0.9571222067
105 342325709 357586938 0.9573215842
106 384276336 401323253 0.9575232267
107 431149389 450184414 0.9577172399
108 483502844 504746003 0.9579131603
109 541946240 565645600 0.9581021667
110 607163746 633589186 0.9582925439
111 679903203 709358186 0.9584766030
112 761002156 793817212 0.9586617351
113 851376628 887922559 0.9588410854
114 952050665 992731551 0.9590213299
115 1064144451 1109412780 0.9591961503
116 1188908248 1239257366 0.9593715668
117 1327710076 1383691294 0.9595421553
118 1482074143 1544288955 0.9597129822
119 1653668665 1722787992 0.9598793387
120 1844349560 1921105572 0.9600459337
121 2056148051 2141356219 0.9602083564
122 2291320912 2385871356 0.9603706598
123 2552338241 2657220702 0.9605292678
124 2841940500 2958235701 0.9606876373
125 3163127352 3292035176 0.9608425498
126 3519222692 3662053392 0.9609971046
127 3913864295 4072070769 0.9611483812
128 4351078600 4526247462 0.9612993002
129 4835271870 5029160094 0.9614471793
130 5371315400 5585841896 0.9615945816
131 5964539504 6201826583 0.9617391229
132 6620830889 6883196294 0.9618831873
133 7346629512 7636633950 0.9620245695
134 8149040695 8469480435 0.9621653557
135 9035836076 9389797022 0.9623036385
136 10015581680 10406433509 0.9624412656
137 11097645016 11529102570 0.9625766873
138 12292341831 12768460866 0.9627113342
139 13610949895 14136197505 0.9628437757
140 15065878135 15645130511 0.9629755616
141 16670689208 17309311977 0.9631053209
142 18440293320 19144142670 0.9632341862
143 20390982757 21166496917 0.9633612633
144 22540654445 23394858638 0.9634875059
145 24908858009 25849469513 0.9636119604
146 27517052599 28552490306 0.9637356400
147 30388671978 31528176495 0.9638576508
148 33549419497 34803069414 0.9639787674
149 37027355200 38406204240 0.9640982747
150 40853235313 42369336269 0.9642170072
151 45060624582 46727187010 0.9643341899
152 49686288421 51517711799 0.9644506574
153 54770336324 56782390739 0.9645655155
154 60356673280 62566544932 0.9646796584
155 66493182097 68919680135 0.9647923708
156 73232243759 75895860130 0.9649043679
157 80630964769 83554112302 0.9650148749
158 88751778802 91958868100 0.9651246667
159 97662728555 101180441299 0.9652333260
160 107438159466 111295547185 0.9653410912
161 118159068427 122387866053 0.9654475451
162 129913904637 134548654696 0.9655534029
163 142798995930 147877409806 0.9656579494
164 156919475295 162482587580 0.9657618403
165 172389800255 178482384132 0.9658644795
166 189334822579 196005581672 0.9659664631
167 207890420102 215192465835 0.9660673141
168 228204732751 236195819934 0.9661675692
169 250438925115 259182002401 0.9662666321
170 274768617130 284332114132 0.9663649797
171 301384802048 311843263024 0.9664624333
172 330495499613 341929933528 0.9665591717
173 362326859895 374825469657 0.9666547775
174 397125074750 410783680579 0.9667498469
175 435157697830 450080578578 0.9668439627
176 476715857290 493016259983 0.9669373631
177 522115831195 539916940446 0.9670299292
178 571701605655 591137156840 0.9671217799
179 625846753120 647062149005 0.9672127366
180 684957390936 708110435576 0.9673029780
181 749474411781 774736599217 0.9673925638
182 819876908323 847434297763 0.9674814343
183 896684817527 926739519045 0.9675693512
184 980462880430 1013234098502 0.9676567912
185 1071823774337 1107549520159 0.9677434564
186 1171432692373 1210371023109 0.9678294063
187 1280011042268 1322442037302 0.9679146409
188 1398341745571 1444568974260 0.9679992795
189 1527273599625 1577626400266 0.9680832028
190 1667727404093 1722562621633 0.9681664705
191 1820701100652 1880405713911 0.9682490826
192 1987276856363 2052270029258 0.9683310390
193 2168627105469 2239363218768 0.9684123993
194 2366022741845 2442993809301 0.9684930444
195 2580840212973 2664579377303 0.9685731530
196 2814570987591 2905655365266 0.9686526656
197 3068829878530 3167884589864 0.9687315822
198 3345365983698 3453067494432 0.9688099027
199 3646072432125 3763153202372 0.9688876271
200 3972999029388 4100251432188 0.9689647555
201 4328363658647 4466645339407 0.9690412283
202 4714566886083 4864805355353 0.9691172838
203 5134205287973 5297404097928 0.9691926837
204 5590088317495 5767332435049 0.9692674875
205 6085253859260 6277716787260 0.9693418741
206 6622987708040 6831937762364 0.9694157243
207 7206841706490 7433650221690 0.9694889188
208 7840656226137 8086804884817 0.9695616961
209 8528581302375 8795671587339 0.9696339369
210 9275102575355 9564864314565 0.9697056413
211 10085065885767 10399368142885 0.9697768092
212 10963707205259 11304568230064 0.9698475599
213 11916681236278 12286281005885 0.9699176550
214 12950095925895 13350787725418 0.9699874520
215 14070545699287 14504870558863 0.9700565934
216 15285151248481 15755851404324 0.9701253772
217 16601598107914 17111633623211 0.9701936841
218 18028182516671 18580746912198 0.9702613950
219 19573856161145 20172395540871 0.9703287482
220 21248279009367 21896510200516 0.9703956842
221 23061871173849 23763803726856 0.9704620838
222 25025873760111 25785830978194 0.9705281854
223 27152408925615 27975053170255 0.9705936909
224 29454549941750 30344906990322 0.9706587791
225 31946390696157 32909878835929 0.9707234502
226 34643126322519 35685584547657 0.9707877636
227 37561133582570 38688855031509 0.9708514810
228 40718063627362 41937828194008 0.9709149599
229 44132934884255 45452047642771 0.9709779024
230 47826239745920 49252568636891 0.9710405469
231 51820051838712 53362071805189 0.9711027145
232 56138148670947 57804985186436 0.9711645246
233 60806135438329 62607615184110 0.9712257981
234 65851585970275 67798287069297 0.9712868929
235 71304185514919 73407495709204 0.9713475108
236 77195892663512 79468067245509 0.9714077115
237 83561103925871 86015332496721 0.9714675546
238 90436839668817 93087312912000 0.9715270400
239 97862933703585 100724919960735 0.9715861678
240 105882246722733 108972168902833 0.9716448188
241 114540884553038 117876407949376 0.9717031717
242 123888443077259 127488563892340 0.9717612267
243 133978259344888 137863405355658 0.9718188643
244 144867692496445 149059824898439 0.9718761444
245 156618412527946 161141141284870 0.9719331861
246 169296722391554 174175423324584 0.9719897509
247 182973889854026 188235836782470 0.9720460176
248 197726516681672 203401015958318 0.9721019268
249 213636919820625 219755461644884 0.9721575379
250 230793554364681 237389967288174 0.9722127318
251 249291451168559 256402075296662 0.9722676277
252 269232701252579 276896565576938 0.9723223448
253 290726957916112 298985978512926 0.9723765850
254 313891991306665 322791174754257 0.9724304676
255 338854264248680 348441934337795 0.9724841714
256 365749566870782 376077597834926 0.9725375175
257 394723676655357 405847752396823 0.9725904465
258 425933084409356 437912965761214 0.9726432562
259 459545750448675 472445571487887 0.9726957083
260 495741934760846 509630508907071 0.9727477431
261 534715062908609 549666221495857 0.9727995992
262 576672674947168 592765617643607 0.9728510380
263 621837416509615 639157098029103 0.9729023576
264 670448123060170 689085654110834 0.9729533195
265 722760953690372 742814042528290 0.9730038047
266 779050629562167 800624040527758 0.9730542302
267 839611730366814 862817787861847 0.9731043577
268 904760108316360 929719220969565 0.9731541276
269 974834369944625 1001675605623532 0.9732036591
270 1050197489931117 1079059174635750 0.9732528925
271 1131238503938606 1162268877643416 0.9733019471
272 1218374349844333 1251732250453931 0.9733505845
273 1312051800816215 1347907411914864 0.9733990431
274 1412749565173450 1451285196792630 0.9734472036
275 1520980492851175 1562391433693528 0.9734951854
276 1637293969337171 1681789377646526 0.9735428691
277 1762278433057269 1810082307589215 0.9735901952
278 1896564103591584 1947916299659916 0.9736374021
279 2040825852575075 2095983187902076 0.9736841917
280 2195786311682516 2255023724735016 0.9737309217
281 2362219145337711 2425830954338576 0.9737772346
282 2540952590045698 2609253812944707 0.9738234282
283 2732873183547535 2806200970925423 0.9738693833
284 2938929793929555 3017644932519941 0.9739151001
285 3160137867148997 3244626410057251 0.9739605188
286 3397584011986773 3488258990606121 0.9740056992
287 3652430836071053 3749734114127484 0.9740506411
288 3925922161489422 4030326383419016 0.9740953445
289 4219388528587095 4331399227431116 0.9741398096
290 4534253126900886 4654410940903300 0.9741841555
291 4872038056472084 5000921124724650 0.9742282033
292 5234371069753672 5372597552967077 0.9742719531
293 5622992691950605 5771223494179320 0.9743155837
294 6039763882095515 6198705516271974 0.9743589163
295 6486674127079088 6657081806172019 0.9744020700
296 6965850144195831 7148531037387221 0.9744449258
297 7479565078510584 7675381820704932 0.9744877219
298 8030248384943040 8240122775459515 0.9745301604
299 8620496275465025 8845413261149425 0.9745724797
300 9253082936723602 9494094811674990 0.9746145010
301 9930972392403501 10189203317110460 0.9746564627
302 10657331232548839 10933982000725688 0.9746980667
303 11435542077822104 11731895241949532 0.9747394919
304 12269218019229465 12586643299120200 0.9747807980
305 13162217895057704 13502177989216618 0.9748218656
306 14118662665280005 14482719385314408 0.9748626351
307 15142952738857194 15532769301309144 0.9749035835
308 16239786535829663 16657147402213588 0.9749440551
309 17414180133147295 17860985588258980 0.9749842882
310 18671488299600364 19149766629375304 0.9750242829
311 20017426762576945 20529342707534968 0.9750642180
312 21458096037352891 22005955428833992 0.9751040339
313 23000006655487337 23586278872545564 0.9751435518
314 24650106150830490 25277429940633676 0.9751824141
315 26415807633566326 27086967586650832 0.9752220511
316 28305020340996003 29023035653297300 0.9752604961
317 30326181989842964 31094224234096188 0.9752995372
318 32488293351466654 33309776748784280 0.9753380418
319 34800954869440830 35679515799158656 0.9753763080
320 37274405776748077 38213908852175176 0.9754146338
321 39919565526999991 40924132164908368 0.9754529595
322 42748078035954696 43822137403884520 0.9754905701
323 45772358543578028 46920596571850352 0.9755280614
324 49005643635237875 50233047541770672 0.9755658507
325 52462044228828641 53773952623211488 0.9756032825
326 56156602112874289 57558713310126376 0.9756403565
327 60105349839666544 61603714435853048 0.9756773710
328 64325374609114550 65926479563830296 0.9757137299
329 68834885946073850 70545559894523240 0.9757508039
330 73653287861850339 75480857020135632 0.9757876396
331 78801255302666615 80753563750380448 0.9758238196
332 84300815636225119 86386225803536704 0.9758595228
333 90175434980549623 92402752864131424 0.9758955240
334 96450110192202760 98828778757204976 0.9759314656
335 103151466321735325 105691520672608816 0.9759672880
336 110307860425292772 113020039739596944 0.9760026932
337 117949491546113972 120845194660497744 0.9760379195
338 126108517833796355 129199834265255360 0.9760733843
339 134819180623301520 138119070497839072 0.9761083722
340 144117936527873832 147640086823680768 0.9761436582
341 154043597379576030 157802736665318080 0.9761782289
342 164637479165761044 168649141369833280 0.9762130380
343 175943559810422753 180224388481957888 0.9762472510
344 188008647052292980 192576303664737216 0.9762813449
345 200882556287683159 205755735681707488 0.9763157368
346 214618299743286299 219817114557698880 0.9763493538
347 229272286871217150 234817892021580704 0.9763834476
348 244904537455382406 250819630902111232 0.9764169455
349 261578907351144125 267887488645857760 0.9764506221
350 279363328483702152 286091003448358624 0.9764841795
351 298330063062758076 305503980525526208 0.9765177965
352 318555973788329084 326205309075934016 0.9765505195
353 340122810048577428 348278279929538176 0.9765834808
354 363117512048110005 371811952527973952 0.9766160846
355 387632532919029223 396900608042416320 0.9766489267
356 413766180933342362 423644854574340352 0.9766817093
357 441622981929358437 452151894545994048 0.9767137766
358 471314064268398780 482534697839456896 0.9767464995
359 502957566506000020 514914767823417280 0.9767783284
360 536679070310691121 549419916035085952 0.9768103957
361 572612058898037559 586186483048774400 0.9768428206
362 610898403751884101 625360436533241088 0.9768741131
363 651688879997206959 667094599384189696 0.9769062400
364 695143713458946040 711553898163190656 0.9769374728
365 741433159884081684 758912063722399488 0.9769684076
366 790738119649411319 809353259298075776 0.9769999981
367 843250788562528427 863074849995672064 0.9770308733
368 899175348396088349 920284637195840128 0.9770621657
369 958728697912338045 981205277609839104 0.9770929217
370 1022141228367345362 1046071518487176448 0.9771236777
371 1089657644424399782 1115133492964525056 0.9771544933
372 1161537834849962850 1188656732460643840 0.9771852493
373 1238057794119125085 1266924370816654592 0.9772152305
374 1319510599727473500 1350234366368357376 0.9772455692
375 1406207446561484054 1438905579292669952 0.9772757292
376 1498478743590581081 1533275562156420864 0.9773055911
377 1596675274490756791 1633701659417136640 0.9773359299
378 1701169427975813525 1740566493457352192 0.9773654342
379 1812356499739472950 1854272486701421056 0.9773949385
380 1930656072350465812 1975248453716895744 0.9774244428
381 2056513475336633805 2103949584722496768 0.9774537683
382 2190401332423765131 2240858577704988160 0.9774830341
383 2332821198543892336 2386487791057361408 0.9775123000
384 2484305294265418180 2541380390560308736 0.9775416851
385 2645418340688763701 2706113623086658560 0.9775710702
386 2816759503217942792 2881301010352939520 0.9775998592
387 2998964447736452194 3067591265696513024 0.9776284099
388 3192707518433532826 3265672680785089536 0.9776569009
389 3398704041358160275 3476275339945451520 0.9776855111
390 3617712763867604423 3700175485968959488 0.9777138233
391 3850538434667429186 3938193365096566272 0.9777423143
392 4098034535626594791 4191204187453474304 0.9777702093
393 4361106170762284114 4460127138961550848 0.9777986407
394 4640713124699623515 4745945187557268480 0.9778269529
395 4937873096788191655 5049700666326290432 0.9778546095
396 5253665124416975163 5372490893215237120 0.9778825641
397 5589233202595404488 5715490140545918976 0.9779096842
398 5945790114707874597 6079929869075792896 0.9779372811
399 6324621482504294325 6467125087948774400 0.9779648781
400 6727090051741041926 6878469977672619008 0.9779922366
p( 5)^1/5 1.4757731
p( 10)^1/10 1.4531984
p(100)^1/100 1.2100422
p(250)^1/250 1.1414394
